Можно ли выполнять итеративный обход в BST, у которого node есть родительский указатель (родительский корень null) без использования флага visited или stack?
Я googled и не нашел ответа. Дело в том, как я могу узнать - на определенном node - что я только что пришел к нему, и я закончил все под ним?
Вы можете это сделать, вам просто нужно запомнить последний посещенный node вместе с текущим node. Выполнение этого не запрещено выражением проблемы: оба флага visited для каждого node и a stack являются (наихудший случай) O (n), помня последний node является просто O (1).
В С# алгоритм может выглядеть так:
static void Walk(Node node)
{
Node lastNode = null;
while (node != null)
{
if (lastNode == node.Parent)
{
if (node.Left != null)
{
lastNode = node;
node = node.Left;
continue;
}
else
lastNode = null;
}
if (lastNode == node.Left)
{
Output(node);
if (node.Right != null)
{
lastNode = node;
node = node.Right;
continue;
}
else
lastNode = null;
}
if (lastNode == node.Right)
{
lastNode = node;
node = node.Parent;
}
}
}
Вот еще один способ сделать это. Я думаю, что это по сути эквивалентно ответу svick, но избегает дополнительной переменной. Эта версия реализована в Python:
node=root
if node is not None:
while node.left is not None:
node=node.left
while node is not None:
output(node)
if node.right is not None:
node=node.right
while node.left is not None:
node=node.left
else:
while node.parent is not None and node.parent.right is node:
node=node.parent
node=node.parent
Независимо от того, какой node вы посетили, последний определяет следующий node, который вам нужно посетить. Если вы только что посетили node X, вам нужно посетить самый левый node справа от X. Если X не имеет правильного дочернего элемента, то следующий node является первым предком, где node X не исходил с правой стороны.
Используя svick правильную идею (см. его ответ), это проверенный код в С++, Обратите внимание, что я не тестировал его код или даже не смотрел на него, я просто взял его идею и реализовал свою собственную функцию.
void in_order_traversal_iterative_with_parent(node* root) {
node* current = root;
node* previous = NULL;
while (current) {
if (previous == current->parent) { // Traversing down the tree.
previous = current;
if (current->left) {
current = current->left;
} else {
cout << ' ' << current->data;
if (current->right)
current = current->right;
else
current = current->parent;
}
} else if (previous == current->left) { // Traversing up the tree from the left.
previous = current;
cout << ' ' << current->data;
if (current->right)
current = current->right;
else
current = current->parent;
} else if (previous == current->right) { // Traversing up the tree from the right.
previous = current;
current = current->parent;
}
}
cout << endl;
}
public void inorderNoStack() {
if (root == null) {
return;
}
// use the previous to always track the last visited node
// helps in deciding if we are going down/up
Node prev = null;
Node curr = root;
while (curr != null) {
// going down
if (prev == null || prev.left == curr || prev.right == curr) {
if (curr.left != null) {
prev = curr;
curr = curr.left;
continue;
} else {
visitn(curr);
if (curr.right != null) {
prev = curr;
curr = curr.right;
continue;
} else {
// swap states
prev = curr;
curr = prev.parent;
}
}
}
// going up after left traversal
if (curr != null && prev == curr.left) {
visitn(curr);
if (curr.right != null) {
prev = curr;
curr = curr.right;
continue;
} else {
// swap states
prev = curr;
curr = prev.parent;
}
}
// going up after right traversal
if (curr != null && prev == curr.right) {
// swap states
prev = curr;
curr = prev.parent;
}
}
}
Мое решение Java без введения какого-либо флага в существующем TREE. И никакой родительский указатель. Этот подход будет удерживать узлы до высоты дерева. Пожалуйста, смотрите.
https://github.com/skanagavelu/Algorithams/blob/master/src/tree/InOrderTraversalIterative.java
Шаг 1: напишите функцию, которая возвращает преемника in-order
Шаг 2: начиная с самого левого node, найдите преемника в порядке до тех пор, пока не будет
public class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode parent;
}
public class TreeUtility {
public void inorderNoRecursion(TreeNode root) {
TreeNode current = leftmostNode(root);
while(current != null) {
System.out.println(current.data);
current = inorderSuccessor(current);
}
}
public TreeNode inorderSuccessor(TreeNode node) {
if (node.right!=null) {
return leftmostNode(node.right);
}
TreeNode p = node.parent;
TreeNode c = node;
while(p!=null && c != p.left) {
c = p;
p = p.parent;
}
return p;
}
private TreeNode leftmostNode(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
}
Ключ - это родительские указатели (или способность мутировать дерево), но вам нужно постоянное количество дополнительного состояния (например, счетчик программ для следующей сопрограммы).
Это в С++:
void InOrder(Node *r)
{
if(r==NULL)
return;
Node *t=r;
while(t!=NULL)
t=t->left;
while(t!=r)
{
if(t==(t->parent->left))
{
cout<<t->parent->data;
t=t->parent->right;
if(t!=NULL)
{
while(t!=NULL)
t=t->left;
}
if(t==NULL)
t=t->parent;
}
if(t==t->parent->right)
{
t=t->parent;
}
}
}