Можно ли выполнить обход по бинарному дереву без рекурсии и стека?

Question

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

Answer 1

Второе редактирование: я думаю, что это правильно.Требуется node.isRoot, node.isLeftChild и node.parent в дополнение к обычным node.left_child и node.right_child.

state = "from_parent"
current_node = root
while (!done)
  switch (state)
    case "from_parent":
      if current_node.left_child.exists
        current_node = current_node.left_child
        state = "from_parent"
      else
        state = "return_from_left_child"
    case "return_from_left_child"
      if current_node.right_child.exists
        current_node = current_node.right_child
        state = "from_parent"
      else
        state = "return_from_right_child"
    case "return_from_right_child"
      if current_node.isRoot
        done = true
      else
        if current_node.isLeftChild
         state = "return_from_left_child"
        else
         state = "return_from_right_child"
        current_node = current_node.parent

Answer 2

Начните с tree_first (), продолжайте с tree_next (), пока не получите NULL. Полный код: https://github.com/virtan/tree_closest

struct node {
    int value;
    node *left;
    node *right;
    node *parent;
};

node *tree_first(node *root) {
    while(root && root->left)
        root = root->left;
    return root;
}

node *tree_next(node *p) {
    if(p->right)
        return tree_first(p->right);
    while(p->parent) {
        if(!p->parent->right || p->parent->right != p)
            return p->parent;
        else p = p->parent;
    }
    return 0;
}

Answer 3

Как уже здесь кто-то сказал, это возможно, но не без родительского указателя. Родительский указатель в основном позволяет вам пройти «путь», если хотите, и, следовательно, распечатать узлы. Но почему рекурсия работает без родительского указателя? Хорошо, если вы понимаете рекурсию, она выглядит примерно так (представьте, что стек рекурсии):

  recursion //going into
   recursion
    recursion
     recursion 
     recursion //going back up
    recursion
   recursion
  recursion

Итак, когда рекурсия заканчивается, вы печатаете выбранную сторону двоичного дерева в обратном порядке.

Answer 4

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

Answer 5

Поскольку для обхода двоичного дерева требуется какое-то состояние (узлы для возврата после посещения преемников), которое может быть предоставлено стеком, подразумеваемым рекурсией (или явным образом в массиве).

Ответ - нет, вы не можете. (согласно классическому определению)

Итерационным способом, наиболее близким к обходу двоичного дерева, вероятно, является использование heap

EDIT: Или, как уже показано, двоичное дерево с резьбой ,