Print Simple Binary Search Tree in C

Question

I just implement simple binary search tree in C.

struct node_struct {
    int data;
    struct node_struct *right, *left;
};

typedef struct node_struct Node;

With insert, delete and search function that already work find.

But i also need to implement print function that print the tree out this way

6
|-2
  |-1
  |-4
|-9

from above node 6 have 2 in the left and 9 in the right and in node 2 have 1 in the left and 4 in the right.

So i want to ask to how to implement this print function.

Answer 1

There are 4 ways to print the binary search tree :

1. Level order traversal
2. Pre-order traversal
3. In-order traversal
4. Post-order traversal

Level order traversal use STL Queue function. And pre-order, in-order and post-order traversal use the concept of recursion.

Level order traversal

#include<iostream>

#include<queue>

using namespace std;


struct Node {

    char data;

    Node *left;

    Node *right;

};


// Function to print Nodes in a binary tree in Level order

void LevelOrder(Node *root) {

    if(root == NULL) return;

    queue<Node*> Q;

    Q.push(root); 

    //while there is at least one discovered node

    while(!Q.empty()) {

        Node* current = Q.front();

        Q.pop(); // removing the element at front

        cout<<current->data<<" ";

        if(current->left != NULL) Q.push(current->left);

        if(current->right != NULL) Q.push(current->right);

    }

}

Preorder, Inorder, Postorder

#include<iostream>

using namespace std;

 

struct Node {

    char data;

    struct Node *left;

    struct Node *right;

};


//Function to visit nodes in Preorder

void Preorder(struct Node *root) {

    // base condition for recursion

    // if tree/sub-tree is empty, return and exit

    if(root == NULL) return;


    printf("%c ",root->data); // Print data

    Preorder(root->left); // Visit left subtree

    Preorder(root->right); // Visit right subtree

}


//Function to visit nodes in Inorder

void Inorder(Node *root) {

    if(root == NULL) return;


    Inorder(root->left); //Visit left subtree

    printf("%c ",root->data); //Print data

    Inorder(root->right); // Visit right subtree

}


//Function to visit nodes in Postorder

void Postorder(Node *root) {

    if(root == NULL) return;


    Postorder(root->left); // Visit left subtree

    Postorder(root->right); // Visit right subtree

    printf("%c ",root->data); // Print data

}

Answer 2

you can do a Tree traversal using the Pre-order technique

Pre-order (NLR)

1. Access the data part of the current node.

2. Traverse the left subtree by recursively calling the pre-order function.

3. Traverse the right subtree by recursively calling the pre-order function.

keeping count of the current level to print the indentation. for example:

#include <stdio.h>

struct node_struct
{
    int data;
    struct node_struct *right, *left;
};
typedef struct node_struct Node;

void treeprint(Node *root, int level)
{
        if (root == NULL)
                return;
        for (int i = 0; i < level; i++)
                printf(i == level - 1 ? "|-" : "  ");
        printf("%d\n", root->data);
        treeprint(root->left, level + 1);
        treeprint(root->right, level + 1);
}

int main(void)
{
        Node a, b, c, d, e, f;

        a.data = 6;
        a.left = &b;
        a.right = &c;

        b.data = 2;
        b.left = &d;
        b.right = &e;

        c.data = 9;
        c.left = NULL;
        c.right = NULL;

        d.data = 1;
        d.left = &f;
        d.right = NULL;

        e.data = 4;
        e.left = NULL;
        e.right = NULL;

        f.data = 8;
        f.left = NULL;
        f.right = NULL;

        treeprint(&a, 0);
}

---

$ cc tree.c
$ ./a.out
6
|-2
  |-1
    |-8
  |-4
|-9
$

Answer 3

Recursively. Try this.

    #include <stdio.h>
#include <stdlib.h>

struct node_struct 
{
    int data;
    struct node_struct *right, *left;
};

// Implementation method
void RecursivePrint(struct node_struct* cur, int depth)
{
    //Don't print a null tree
    if(cur== 0)
    {
        return;
    }

    //Print data value of current node
    for(int i = 0; i <= depth; i++)
    {
        if(depth - i > 1)
        {
            printf("  ");
        }
        else if (depth - i == 1)
        {
            printf("|-");
        }
        else if (depth - i == 0)
        {
            printf("%d", cur->data);
        }
    }
    printf("\n");

    //Print left
    RecursivePrint(cur->left, depth + 1);
    //Print right
    RecursivePrint(cur->right, depth + 1);
}

// Method to call
void PrintTree(struct node_struct* root)
{
    RecursivePrint(root, 0);
}   

int main()
{
    struct node_struct* one;
    struct node_struct* two;
    struct node_struct* four;
    struct node_struct* six;
    struct node_struct* nine;
    one = (struct node_struct*)malloc(sizeof(struct node_struct));
    two = (struct node_struct*)malloc(sizeof(struct node_struct));
    four = (struct node_struct*)malloc(sizeof(struct node_struct));
    six = (struct node_struct*)malloc(sizeof(struct node_struct));
    nine = (struct node_struct*)malloc(sizeof(struct node_struct));

    one->data = 1;
    two->data = 2;
    four->data = 4;
    six->data = 6;
    nine->data = 9;

    one->left = 0;
    one->right = 0;

    two->left = one;
    two->right = four;

    four->left = 0;
    four->right = 0;

    six->left = two;
    six->right = nine;

    nine->left = 0;
    nine->right = 0;

    PrintTree(six);

    return 0;
}