Каждый "учебник", который я проверял в Google и все ответы в этой теме, использует следующую логику: " Если у узла нет правильного потомка, то его преемник по порядку будет одним из его предков. Использованиеродительская ссылка продолжает перемещаться вверх, пока вы не получите узел, который является левым дочерним элементом своего родителя. Тогда этот родительский узел будет преемником по порядку."
Это то же самое, что и думать" если мой родитель больше меня, то я левый ребенок"(свойство бинарного дерева поиска).Это означает, что вы можете просто пройти по родительской цепочке, пока указанное выше свойство не станет истинным.Что, на мой взгляд, приводит к более элегантному коду.
Я думаю, причина, по которой все проверяют " я ли левый ребенок ", просматривая ветви вместо значений в пути кода, которыеиспользует родительские ссылки, полученные из логики «заимствования» из алгоритма no-link-to-parent.
Также из приведенного ниже кода мы видим, что нет необходимости в структуре данных стека какпредложено другими ответами.
Ниже приводится простая функция C ++, которая работает для обоих вариантов использования (с использованием ссылки на родителя и без нее).
Node* nextInOrder(const Node *node, bool useParentLink) const
{
if (!node)
return nullptr;
// when has a right sub-tree
if (node->right) {
// get left-most node from the right sub-tree
node = node->right;
while (node->left)
node = node->left;
return node;
}
// when does not have a right sub-tree
if (useParentLink) {
Node *parent = node->parent;
while (parent) {
if (parent->value > node->value)
return parent;
parent = parent->parent;
}
return nullptr;
} else {
Node *nextInOrder = nullptr;
// 'root' is a class member pointing to the root of the tree
Node *current = root;
while (current != node) {
if (node->value < current->value) {
nextInOrder = current;
current = current->left;
} else {
current = current->right;
}
}
return nextInOrder;
}
}
Node* previousInOrder(const Node *node, bool useParentLink) const
{
if (!node)
return nullptr;
// when has a left sub-tree
if (node->left) {
// get right-most node from the left sub-tree
node = node->left;
while (node->right)
node = node->right;
return node;
}
// when does not have a left sub-tree
if (useParentLink) {
Node *parent = node->parent;
while (parent) {
if (parent->value < node->value)
return parent;
parent = parent->parent;
}
return nullptr;
} else {
Node *prevInOrder = nullptr;
// 'root' is a class member pointing to the root of the tree
Node *current = root;
while (current != node) {
if (node->value < current->value) {
current = current->left;
} else {
prevInOrder = current;
current = current->right;
}
}
return prevInOrder;
}
}