CODEWITHSUNDEEP
cbinary-treebinary-search-tree
Daniel Hermon
Daniel Hermon

Reputation: 61

Printing a Binary search Tree in a certain format diagram. in c

I need to print a Binary search tree and it should look like a tree means if I have a tree which is 5,6,7 the printing function will print it like Example 1:

insert
5
insert
6
insert
7
Tree is:
    5
        6
            7

Now lets say a tree is 4,3,7 the result should be like Example 2:

insert
4
insert
3
insert
7
tree is:
    4
3       7

There is 1 restriction: it should be done recursively.

This is the code I tried to solve this problem with:

void PrintTabs(int n)
{
  if(n==0)
  {
      return;
  }
  else
  {
      printf("\t");
      PrintTabs(--n);
  }
}

void PrintTree(BST* root, int level)
{
     if (root==NULL)
     {
         return;
     }
     PrintTree(root->Right,++level);
     PrintTabs(level);
     printf("%d\n",*(int*)root->Value);
     PrintTree(root->Left,++level);
}

My 2 main issues are it always printed sliding right, so I moved the printing section between the two recursive calls it had given me a bad result but somehow it had a format of the tree I looked for

Upvotes: 1

Views: 451

Answers (2)

phoenix
phoenix

Reputation: 3159

// This is used to find the leftmost node from the root (i.e, how much left). This is computed so that root is printed in the center.

findAlignment (BST * root, int *leftMost, int leftness) {

    if (root == NULL) {
        return;
    }

    if (leftness > *leftMost) {
        *leftMost = leftness;
    }

    findAlignment (root->left, leftMost, (leftness + 1));
    findAlignment (root->right, leftMost, (leftness - 1));

}

// This prints the tree using the leftmost node info. It adjusts the cursor position based on level and the leftness of the node to directly print. 

void PrintTree(BST* root, int leftAlignment, int level)
{
     if (root==NULL)
     {
         return;
     }

     // the first printf aligns the position of cursor on the screen.
     // This code may not be portable on all machines.
     // see http://c-faq.com/osdep/termcap.html for details.
     // This particular print moves the cursor to row: 'level' and col: 'leftAlignment * 4'. 
     // You can change the multiplication factor from 4 based on
     // how many chars root->value will have and your other requirements to make it properly align.
     // You can also multiply level by some factor, if you want to align better.
     printf("\033[%d;%dH", level, leftAlignment * 4);
     printf("%d",root->Value);

     PrintTree(root->Left, leftAlignment - 1, level + 1);
     PrintTree(root->Right, leftAlignment + 1, level + 1);
}

int leftMost = 0;
findAlignment (root, &leftMost, 0);
printf("\033[2J"); // clear screen
printTree (root, leftMost, 0);

Upvotes: 1

Silvertail
Silvertail

Reputation: 169

Sry, I don't have enough rep. to post this as a comment. Since BST's are usually meant to only recurs one way (down), I would go about this a little differently. What if for each node, you figure out if it went left or right, and just keep track of that position in the node. Ex. I went left twice and right once, so my difference from root is -1 (to the left once). Each time you add a node, you can copy the parent's position and just add 1 or -1 for the child. Then you can easily use that number with your tabs function to step through the tree and add tabs as needed. 

                          root(0)
                     left(-1)       right(1)
                 left(-2)  right(0)

Upvotes: 0

Related Questions