g*l
发帖数: 385 | 1 有 parent link比较容易, 要是没有 parent link, 是不是只能用 iterative inorder
traversal : 找到当前节点, 输出它的下一个? | c******w
发帖数: 102 | 2 Node* nextNode(Node* root, int data)
{
Node* result = NULL;
while(root)
{
if( root->value > data )
{
result = root;
root = root -> left;
}
else
root = root -> right;
}
return result;
}
inorder
【在 g*l 的大作中提到】
: 有 parent link比较容易, 要是没有 parent link, 是不是只能用 iterative inorder
: traversal : 找到当前节点, 输出它的下一个?
| g********d
发帖数: 203 | 3 BST or just binary tree?
inorder
【在 g*l 的大作中提到】
: 有 parent link比较容易, 要是没有 parent link, 是不是只能用 iterative inorder
: traversal : 找到当前节点, 输出它的下一个?
| g*l
发帖数: 385 | 4 yeah, should be two separate questions. I'm asking both.
【在 g********d 的大作中提到】
: BST or just binary tree?
:
: inorder
| g*l
发帖数: 385 | 5 I don't think it's right.
【在 c******w 的大作中提到】
: Node* nextNode(Node* root, int data)
: {
: Node* result = NULL;
: while(root)
: {
: if( root->value > data )
: {
: result = root;
: root = root -> left;
: }
| c******w
发帖数: 102 | 6 这个算法是针对BST的。 如果是一般的binary tree， 需要通过回朔父节点。
【在 g*l 的大作中提到】
: I don't think it's right.
| a****s
发帖数: 22 | 7 不知道这样行不行, 感觉可以,不过没编译试过.基本意思就是Inorder遍历树，记住当
前节点的In-order上一个节点.
void FindInOrderNextInTreeHelper(Node *p, int data, Node *& next, Node *&
prev)
{
if(!p) return;
FindInOrderNextInTreeHelper(p->left, data, next, prev);
if(prev && prev->data == data)
{
next = p;
return;
}
prev = p;
FindInOrderNextInTreeHelper(p->right, data, next, prev);
}
Node * FindInOrderNextInTree(Node *p, int data)
{
if(!p) return NULL;
Node * next = NULL;
Node * prev = NULL;
FindInOrderNextInTreeHelper(p, data, next, prev);
return next;
}
inorder
【在 g*l 的大作中提到】
: 有 parent link比较容易, 要是没有 parent link, 是不是只能用 iterative inorder
: traversal : 找到当前节点, 输出它的下一个?
| h*******0
发帖数: 68 | 8 不知道这样行不行, 感觉可以,不过没编译试过.基本意思就是Inorder遍历树，记住当
前节点的In-order上一个节点.
void FindInOrderNextInTreeHelper(Node *p, int data, Node *& next, Node *&
prev)
{
if(!p) return;
FindInOrderNextInTreeHelper(p->left, data, next, prev);
if(prev && prev->data == data)
{
next = p;
return;
}
prev = p;
FindInOrderNextInTreeHelper(p->right, data, next, prev);
}
Node * FindInOrderNextInTree(Node *p, int data)
{
if(!p) return NULL;
Node * next = NULL;
Node * prev = NULL;
FindInOrderNextInTreeHelper(p, data, next, prev);
return next;
}
inorder
【在 g*l 的大作中提到】
: 有 parent link比较容易, 要是没有 parent link, 是不是只能用 iterative inorder
: traversal : 找到当前节点, 输出它的下一个?
| g*l
发帖数: 385 | 9 This code is surprisingly simple but seems to work. Is this a classic
question? How did you derive it, hehe?
【在 c******w 的大作中提到】
: Node* nextNode(Node* root, int data)
: {
: Node* result = NULL;
: while(root)
: {
: if( root->value > data )
: {
: result = root;
: root = root -> left;
: }
|
|
