Я могу сделать inorder обход двоичного дерева без рекурсии и стека?

Question

Я могу сделать inorder обход двоичного дерева без рекурсии и стека?

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

5

задан Gautham 7 April 2010 в 18:41

2 ответа

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

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

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

РЕДАКТИРОВАТЬ: Или, как уже было показано, двоичное дерево с нитями ,

0

ответ дан 15 December 2019 в 06:21

Другие вопросы по тегам:

tree tree-traversal

Похожие вопросы:

score 4 · Accepted Answer

Второе редактирование: Я думаю, это правильно. Требуется 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