c - BST的顺序后继者

给定一个函数getInorderSuccessor，该函数将BST（二进制搜索树）作为参数。每个节点都有一个额外的指针“ next”，该指针被初始化为null，然后用代表有序后继者的节点指针填充。我的以下代码未提供正确的输出

node * getInorderSuccessor(node * root){
struct node * current = root;
static int flag = 0;

if (root != NULL)
{
if (flag != 2)
{
    current->next = getInorderSuccessor(current->left);
}
    if(current ==root)
        flag = 1;
    if (flag == 1)
    {
        flag = 2;
        current->next = root;
        }
    if (flag!=2)
    {

        current->next = getInorderSuccessor(current->right);

    }

}

最佳答案

假设“左”为高，“右”为低：

如果有一个left分支，则下一个更高的节点将在其中。因此，后继节点将是left分支中的最低（最右侧）节点。

如果没有left分支，则需要将树向上（朝根方向）向上移动，直到下一个节点离开当前节点为止，即直到当前节点（沿树向上）成为其父级的right分支。那个父母将是继承人。

无论如何，至少在到当前节点的路径上，您都需要某种方式来知道每个节点的父节点是什么……因为您可能需要移至树的根。这可以是每个节点中的parent指针，也可以是当前节点路径上的某种类型的节点列表。

至于您拥有的代码，我不确定您是如何工作的，但是：

current->next = getInorderSuccessor(current->left);

看起来很奇怪如果current->left是高分支，则current->left的后继者至少要比current高两个节点-因此它不可能是current的直接后继者。如果left是低级分支，则它根本不能包含current的后继者，因此它仍然没有意义。

我也没有在任何地方看到return语句。

关于c - BST的顺序后继者，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7865222/