以特定格式图表打印二叉搜索树。在 c

Question

我需要打印一棵二叉搜索树，它应该看起来像一棵树，这意味着如果我有一棵 5,6,7 的树，打印函数将像 Example 1:

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

现在假设一棵树是 4,3,7 结果应该是 Example 2:

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

有 1 个限制：应该递归完成。

这是我用来解决这个问题的代码：

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);
}

我的 2 个主要问题是它总是向右滑动打印，所以我在两个递归调用之间移动了打印部分，这给了我一个糟糕的结果，但不知何故它有我寻找的树格式

Answer 1

对不起，我没有足够的代表。以 post 此作为评论。由于 BST 通常只以一种方式（向下）重复出现，因此我会以不同的方式处理这个问题。如果对于每个节点，您都知道它是向左还是向右移动，并且只跟踪节点中的那个位置会怎么样。前任。我向左走了两次，向右走了一次，所以我与 root 的区别是 -1（向左一次）。每次添加一个节点时，您可以复制父节点的位置，并为子节点添加 1 或 -1 即可。然后你可以很容易地使用这个数字和你的选项卡功能来遍历树并根据需要添加选项卡。

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

Answer 2

// 用于从根开始寻找最左边的节点（即还剩多少）。这是计算出来的，所以 root 打印在中心。

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));

}

// 这使用最左边的节点信息打印树。它根据节点的级别和左侧调整光标位置以直接打印。

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("3[%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("3[2J"); // clear screen
printTree (root, leftMost, 0);

以特定格式图表打印二叉搜索树。在 c

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

c

binary-tree

binary-search-tree