二分查找树排序

Question

我想在我已经创建的二叉树的帮助下对一些数据进行排序。我有以下可以工作的示例代码。但我不明白这是怎么回事..它启动，如果数据库中没有记录，则执行b=0并返回。这一点很清楚。如果b存在，则转到左侧节点并一次又一次地调用函数，直到b->left ==NULL。我的理解正确吗？但是它什么时候打印数据，因为当它运行函数时，它没有打印数据，而是从函数的顶部重新开始打印。

void display_ordered_email(struct BST_node *b)
{
    if (b==0)           
        return;            
    display_ordered_email(b->left);
    printf("Name    : %s\n", b->data->name);
    printf("Address : %s\n", b->data->address);
    printf("Email   : %s\n", b->data->email);
    printf("\n");
    display_ordered_email(b->right);
}

这是顺序遍历还是其他方法？

Answer 1

考虑一下这棵简单的树。

   b
  / \
 a   c

假设display_ordered_email应该按顺序递归地打印节点，那么您可以问问自己什么时候应该打印b。答案是，b应该在访问并打印a (左侧)之后，但在访问并打印c (右侧)之前打印。

void display_ordered_email(struct BST_node *b)
{
    if (b==0)           
        return;            
    display_ordered_email(b->left);
    /* ... print the node */
    display_ordered_email(b->right);
}

你的套路就是这样组织起来的。

Answer 2

这是您使用递归进行的预排序遍历。一旦您完成了左子树，它将打印该子树的根，然后打印右子树。您可能想要用一个大约有8个节点的树来尝试它。

Answer 3

它将一直遍历到左下角并命中0。然后，它向后移动一个节点，并在return语句之后继续该节点的代码。这意味着它将打印该代码，然后在正确的节点上尝试它。如果没有右侧节点，则只返回，否则将打印右侧节点。然后，如果这两个都完成了，它将备份一个级别，并打印那里的所有内容，然后检查右分支是否有任何分支。

它一开始很让人困惑，但如果你把它画出来，它就会变得容易理解得多。