我可以在沒有遞歸和堆棧的情況下遍歷二叉樹嗎？

Question

任何人都可以給我一個解決方案遍歷二進制樹inorder沒有遞歸和沒有使用堆棧？

Answer 1

第二個編輯：我認爲這是對的。除了通常的node.left_child和node.right_child之外，還需要node.isRoot，node.isLeftChild和node.parent。

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

由於遍歷一個binary tree需要某種狀態（在訪問後繼之後返回節點），這可以由遞歸暗示的堆棧提供（或由數組顯式）。

答案是否定的，你不能。 （按照傳統的定義）

的最接近二叉樹遍歷迭代的方式則可能使用heap

編輯： 或者作爲已經顯示出一個threaded binary tree，

Answer 3

是的，你可以。爲了做到這一點，你需要一個父指針來升級樹。

Answer 4

正如這裏已經有人說過的，這是可能的，但不是沒有父指針。如果需要，父指針基本上允許您遍歷「路徑」，因此可以打印出節點。 但爲什麼遞歸沒有父指針？那麼，如果你瞭解它遞歸去這樣的事情（想象中的遞歸棧）：

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

所以當遞歸結束你就必須打印二叉樹的選擇面相反的順序。

Answer 5

從tree_first（）開始，繼續使用tree_next（），直到獲得NULL。 Full code：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; 
}