Как я могу пройти через двоичное дерево, используя цикл while?

Question

Мне было просто интересно, как я могу пройти через двоичное дерево, используя цикл while (не выполняется рекурсивно).

У меня есть дерево:

typedef struct Node *BSTree;
typedef struct Node {
   int  key;
   BSTree left, right;
} Node;

Я просто хочу знать, какЯ могу получить доступ к каждому узлу во время цикла.Может ли кто-нибудь показать мне это?Я не могу обернуть голову вокруг него.

Answer 1

Вы можете использовать стек для хранения родителей, которые вам нужно посетить при возвращении из уже посещенного филиала.Путь в псевдо-C ++ для обхода предзаказа:

void (Node * root)
{
  if (root == NULL) 
    return;

  Stack<Node *> stack;
  stack.push(root); 

  Node * p;
  while (not stack.is_empty())
    {
      p = stack.pop();

      // here you visit p 

      if (p->right != NULL)
        stack.push(p->left);

      if (p->left != NULL)
        stack.push(p->right);
    }
}

Обратите внимание, что левая и правая ветви толкаются в перевернутом виде, поэтому первым выскользнет левая.

Answer 2

У вас должна быть ссылка на родительский узел.

, если root! = Null, хранить корень в текущем.Если у current есть левый потомок, вы устанавливаете current для левого потомка.Если нет левого ребенка и есть правый дочерний магазин, то правый ребенок в текущем.Если в текущем нет левого и правого дочернего родительского хранилища текущего узла.

Если вы возьмете это, вы попадете в бесконечный цикл, но если вы сохраните один перед текущим и сравните соотношение между текущимузел и последний узел, который вы можете пройти по всему дереву.

Это не полный ответ, но это поможет.