BST 中的顺序后继者
给定一个函数 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);
}
}
Given a function getInorderSuccessor which takes a BST (Binary Search Tree) as it's parameter. Every node has an extra pointer "next" , which is intialized to null, fill next with node pointers which represent Inorder Successor. my following code is not giving correct output
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);
}
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
假设“左”为高，“右”为低：
如果有
left分支，则下一个更高的节点将在其中。因此后继节点将是left分支中最低（最右边）的节点。如果没有
left分支，我们需要沿树向上（向根）向上移动，直到下一个节点位于当前节点的左侧，即直到当前节点（当我们向上移动时）树）是其父树的右分支。该父母将成为继承人。无论如何，您需要某种方式来了解每个节点的父节点是什么，至少在到当前节点的路径上......因为您可能需要移向树的根部。这可能是每个节点中的父指针，或者是当前节点路径上的某种节点列表。
至于你拥有的代码，我不确定你的意思是它如何工作，但是：
......看起来很奇怪。如果
current->left是高分支，则current->left的后继节点将至少是current向上的两个节点-- 所以它不可能是current的直接后继者。如果left是低分支，它根本不能包含current的后继分支，所以它仍然没有意义。我也没有在任何地方看到
return语句。Assuming "left" to be high and "right" to be low:
If there is a
leftbranch, the next higher node will be in it. So the successor will be the lowest (rightmost) node in theleftbranch.If there isn't a
leftbranch, we need to go up the tree (towards the root) until the next node up is left of the current node, i.e. until the current node (as we go up the tree) is therightbranch of its parent. That parent will be the successor.In any case, you need some way of knowing what each node's parent is, at least on the path to the current node... since you may need to move toward the root of the tree. This could be a
parentpointer in each node, or some sort of list of nodes on the path to the current one.As for the code you have, I'm not sure how you meant it to work, but:
...looks strange. If
current->leftis the high branch, thencurrent->left's successor would be at least two nodes up fromcurrent-- so it couldn't becurrent's immediate successor. Ifleftis the low branch, it can't containcurrent's successor at all, so it still doesn't make sense.I also don't see a
returnstatement anywhere.函数的所有（递归）调用都使用相同的静态变量。如果您想记住您离开的路径，您将需要更多（或其他）变量。
The same static variable is used by all the (recursive) invocations of the function. If you want to remember the path where you left off, you'll need more (or other) variables.