二叉树中的预序后继

Question

我想使用值在二进制搜索树中找到一个预购后继。我有一个代码，但它可以使用Node。

Node* preorderSuccessor(Node* root, Node* n)
{
// If left child exists, then it is preorder
// successor.
if (n->left)
return n->left;
// If a left child does not exist, then
// travel up (using parent pointers)
// until we reach a node that is left
// child of its parent.
Node* curr = n, * parent = curr->parent;
while (parent != NULL && parent->right == curr) {
curr = curr->parent;
parent = parent->parent;
}

// If we reached root, then the given
// node has no preorder successor
if (parent == NULL)
return NULL;
return parent->right;
}

我需要这样的函数Node*preorderSuccessor(Node*root，int n(在这个函数中，CCD_ 1和n是我们想要找到继任者的值。

Answer 1

您可以提前实现简单的深度优先搜索：

Node* depthFirstSearch(Node* node, int value)
{
if(!node)
{
return nullptr;
}
if(node->value == value)
{
return node;
}
auto n = depthFirstSearch(node->left, value);
if(n)
{
return n;
}
return depthFirstSearch(node->right, value)
}

然后，您可以将所需的变体实现为给定函数的重载：

Node* preorderSuccessor(Node* root, int value)
{
Node* node = depthFirstSearch(root, value);
return node ? preorderSuccessor(root, node) : nullptr;
}

Answer 2

使用黑客入侵的访问者模式，我们可以很容易地跟踪是否找到了原始节点，然后记得在下一次调用visit时结束搜索。

struct Visitor
{
Node* n;       // the node to find
Node* successor; // the node that is visited after n
bool found;    // flag to indicate when n is found
};
bool visit(Node* n, Visitor* vis)
{
if (vis->found)
{
vis->successor = n;
return false;    // false tells the caller to stop searching further
}
if (vis->n == n)
{
vis->found = true;
}
return true;
}
bool depthFirstSearch(Node *n, Visitor* vis)
{
if (n == nullptr)
{
return true;
}
// pre-order traversal is:
//  Visit
//  Recurse Left
//  Recurse Right
bool keepGoing = visit(n, vis);
if (keepGoing)
{
keepGoing = depthFirstSearch(n-left, vis);
if (keepGoing)
{
keepGoing = depthFirstSearch(n->right, vis);
}
}
return keepGoing;
}
Node* preorderSuccessor(Node* root, Node* n)
{
Visitor vis = {n, nullptr, false};
depthFirstSearch(root, &vis);
return (vis->successor);
}