c - BST 中的顺序后继者

Question

给定一个函数 getInorderSuccessor，它采用 BST(二叉搜索树)作为参数。每个节点都有一个额外的指针“next”，该指针被初始化为null，用代表Inorder Successor的节点指针填充next。我的以下代码没有给出正确的输出

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

    }

}

Answer 1

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

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

如果没有 left 分支，我们需要沿着树向上(向根)前进，直到下一个节点位于当前节点的左侧，即直到当前节点(如我们沿着树向上走)是其父分支的右分支。该 parent 将成为继承人。

无论如何，您需要某种方式来了解每个节点的父节点是什么，至少在到当前节点的路径上......因为您可能需要移向树的根部。这可能是每个节点中的父指针，或者是当前节点路径上的某种节点列表。

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

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

...看起来很奇怪。如果 current->left 是高分支，那么 current->left 的后继节点将至少是 current 向上的两个节点 --所以它不可能是current的直接后继者。如果left是低分支，它根本不能包含current的后继分支，所以它仍然没有意义。

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