使用堆棧無需遞歸就能遍歷二叉樹，下面是一個使用堆棧中序遍歷二叉樹的算法。
算法思路
1)創建一個空棧S。
2）將當前節點初始化為root
3)將當前節點推入S并設置current=current->left直到current為NULL
4)如果current為NULL且堆棧不為空，則
a)從堆棧中彈出頂部項目。
b)輸出彈出的項目，設置current=popped_item->right
c)轉到步驟3)。
5)如果current為NULL并且stack為空，那么算法結束。
算法實現步驟
1
/\
2 3
/\
4 5
步驟1創建一個空堆棧：S=NULL
步驟2將current設置為root的地址：current->1
步驟3推送當前節點并設置current=current->left
直到當前為NULL
當前->1
推1：堆棧S->1
當前->2
推2：堆棧>2,1
當前->4
推4：堆棧S>4、2、1
當前=NULL
步驟4從S彈出
a)彈出4：堆棧S->2,1
b)打印“4”
c)current=NULL/*right of 4*/并轉到步驟3
由于current is NULL step 3沒有做任何事情。
步驟4再次彈出。
a)彈出2：堆棧S->1
b)打印“2”
c)current->;5/*right of 2*/并轉到步驟3
第3步將5推入堆棧并使當前為NULL
堆棧S->5,1
當前=NULL
步驟4從S彈出
a)彈出5：堆棧S->1
b)打印“5”
c)current=NULL/*right of 5*/并轉到步驟3
由于current is NULL step 3沒有做任何事情
步驟4再次彈出。
a)彈出1：堆棧S->NULL
b)打印“1”
c)當前->3/*1的右邊*/
第3步將3推入堆棧并使當前為NULL
堆棧S->3
當前=NULL
步驟4從S彈出
a)彈出3：堆棧S->NULL
b)打印“3”
c)current=NULL/*3的右邊*/
由于堆棧S為空且當前為NULL，因此遍歷已完成。
Python實現堆棧中序遍歷二叉樹
class Node: def __init__(self,data): self.data=data self.left=None self.right=None def inOrder(root): current=root stack=[] while True: if current is not None: stack.append(current) current=current.left elif(stack): current=stack.pop() print(current.data,end="") current=current.right else: break print() root=Node(1) root.left=Node(2) root.right=Node(3) root.left.left=Node(4) root.left.right=Node(5) inOrder(root)
登錄后復制
