如何在不遞歸的情況下遍歷二叉搜索樹？

Question

我可以很容易地遍歷二叉搜索樹使用遞歸，但我沒有關於遍歷的想法沒有遞歸，所以請任何人解釋，.....

Answer 1

是的，你可以用堆棧。你必須在這裏採用迭代方式（非遞歸方式/方法）對二進制搜索樹進行重排序，順序和後序遍歷的算法。希望你會得到正確的。

p再順序：

1）創建一個空棧node_Stack和推根節點到疊加。

2）在node_Stack不爲空的情況下執行以下操作。

- >從堆棧中彈出一個項目並打印它。

- >按彈出項的右子堆棧

- >按彈出項的左子堆放有序

：

1）創建一個空棧S.

2）初始化當前節點作爲根

3）推當前節點S和設定電流=電流 - >左直到電流是NULL

4）如果當前是NULL和堆棧不爲空，則

-> Pop the top item from stack. 

-> Print the popped item, set current = popped_item->right 

-> Go to step 3. 

5）如果當前是NULL和棧是空的，則我們完成了。

後序：

1.1創建一個空棧

2.1執行以下，而根本不爲空

-> Push root's right child and then root to stack. 

-> Set root as root's left child. 

2.2從棧中彈出一個項目並將其設置爲根。

-> If the popped item has a right child and the right child 
    is at top of stack, then remove the right child from stack, 
    push the root back and set root as root's right child. 

-> Else print root's data and set root as NULL. 

2.3重複步驟2.1和2.2，同時堆棧不爲空。