在不使用任何额外空间的情况下在BST中查找inorder后继者
在不使用任何额外空间的情况下在BST中查找inorder后继者
提问于 2010-09-20 19:23:16
我正在寻找一种方法，在不使用额外空间的情况下，在BST中找到节点的顺序后继者。
回答 4
Stack Overflow用户
回答已采纳
发布于 2011-02-16 03:09:11
为了获得给定节点N的有序后继者，我们使用以下规则：
代码如果N有一个右子代码，则inorderSuccessor(N)是R.
- Else的最左边的后代
inorderSuccessor(N)是N的最接近的祖先M(如果存在)，这样N就是<代码>d13的左子代码的后代。如果没有这样的祖先，则inorderSucessor不存在。
考虑一个示例树：
A
/ \
B C
/ \
D E
/
F它的顺序遍历提供了：D B F E A C
inorderSuccessor(A) = C，因为C是A的右子节点的最左边的子节点。
inorderSuccessor(B) = F，因为F是B的右子节点的最左边的子节点。
inorderSuccessor(C) =不存在。
inorderSuccessor(D) = B，因为B是D的左子节点。
inorderSuccessor(E) = A。E没有右子节点，所以我们有场景2。我们转到E的父节点，它是B，但E是B的右后代，所以我们移到B的父节点，它是A，B是A的左子节点，所以A是答案。
inorderSuccessor(F) = E，因为F是E的左子节点。
操作步骤：
treeNodePtr inorderSucessor(treeNodePtr N) {
if(N) {
treeNodePtr tmp;
// CASE 1: right child of N exists.
if(N->right) {
tmp = N->right;
// find leftmost node.
while(tmp->left) {
tmp = tmp->left;
}
// CASE 2: No right child.
} else {
// keep climbing till you find a parent such that
// node is the left decedent of it.
while((tmp = N->parent)) {
if(tmp->left == N) {
break;
}
N = tmp;
}
}
return tmp;
}
// No IOS.
return NULL;
}Stack Overflow用户
发布于 2011-11-08 22:48:53
以下方法可帮助您以非递归方式确定没有任何父节点或额外空间的有序后继
struct node * inOrderSuccessor(struct node *root, struct node *n)
{
//*If the node has a right child, return the smallest value of the right sub tree*
if( n->right != NULL )
return minValue(n->right);
//*Return the first ancestor in whose left subtree, node n lies*
struct node *succ=NULL;
while(root)
{
if(n->datadata < root->data)
{
succ=root; root=root->left;
}
else if(n->data > root->data)
root=root->right;
else break;
}
return succ;
}我很确定这是对的。如果我错了，请纠正我。谢谢。
Stack Overflow用户
发布于 2010-09-20 20:23:59
如果给定的节点有一个右子节点-转到它，然后迭代地跟随左子节点，直到你到达一个没有左子节点的节点N。返回N。
否则，跟随父节点，直到第一次找到节点为左子节点的父节点。返回此父对象。
Node InOrderSuccessor(Node node) {
if (node.right() != null) {
node = node.right()
while (node.left() != null)
node = node.left()
return node
} else {
parent = node.getParent();
while (parent != null && parent.right() == node) {
node = parent
parent = node.getParent()
}
return parent
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3750929
复制相关文章
相似问题
腾讯云开发者
