迭代的方式處理樹，就必須清楚你將要訪問的順序，對應的就是指針怎么走，你必須很清楚

樹的寬度優先搜索，他是一層一層的訪問，就搞不清楚怎么劃分子問題了，但是你訪問的順序

你很清楚，那么就使用迭代的方式實現，你的指針應該可以按照一層一層的走

怎么走？在線性結構里，我們處理的是數組，可以直接一個一個的走

在樹里，按照層次訪問，每一層結點之間是跳躍的，那我們該怎么實現指針的連續走動？

很容易的思路，把每一層的結點放在一個數組里，然后指針就可以連續走動了

把每一層的結點放在一個數組里，也需要注意放入和取出順序，我們需要實現每一層從左到

右的層次訪問，先左后右放入數組的話，取出的時候，也必須是先左后右取出

很明顯我們需要先進先出的數據結構，FIFO

從這個代碼結構可以看出和分支限界法隊列實現方式很像，

分支限界就是把解定義成樹，在樹里搜索結果

# 首先需要定義結點 class BinTNode:def __init__(self,data=None,left =None,right =None):self.data =dataself.left =leftself.right =right# 迭代的方式處理樹，就必須清楚你將要訪問的順序，對應的就是指針怎么走，你必須很清楚# 樹的寬度優先搜索，他是一層一層的訪問，就搞不清楚怎么劃分子問題了，但是你訪問的順序 # 你很清楚，那么就使用迭代的方式實現，你的指針應該可以按照一層一層的走 # 怎么走？在線性結構里，我們處理的是數組，可以直接一個一個的走 # 在樹里，按照層次訪問，每一層結點之間是跳躍的，那我們該怎么實現指針的連續走動？ # 很容易的思路，把每一層的結點放在一個數組里，然后指針就可以連續走動了 # 把每一層的結點放在一個數組里，也需要注意放入和取出順序，我們需要實現每一層從左到 # 右的層次訪問，先左后右放入數組的話，取出的時候，也必須是先左后右取出 # 很明顯我們需要先進先出的數據結構，FIFO# 從這個代碼結構可以看出和分支限界法隊列實現方式很像， # 分支限界就是把解定義成樹，在樹里搜索結果 def levelorder(root):# 初始化，把根結點放入隊列queue = [root,] # 當隊列為空時代表，所有結點都遍歷了while queue:# 彈出先放出的元素node = queue.pop(0)# 彈出的過程也是處理數據的過程print(node.data,end=' ')# 葉子結點不需要把左右的None添加到隊列if node.left:queue.append(node.left)if node.right:queue.append(node.right)

實現迭代方式的先根遍歷，不管怎么遍歷，首先你必須知道你是如何掃描的，然后再考慮如何遍歷

所有的遍歷掃描方式都是，一直往左走，到底回溯，往右走一步，一直往左走，到底回溯，往右走一步。。。

在這種掃描方式下，如何實現：回溯，往右走一步？就是提前把往右走的步驟放在一個數組里，回溯的時候

直接從數組取出要回溯到哪里，首先我們知道要回溯的結點都是右結點，那我們按照順序掃描的過程中，

把右結點都放入一個數組，我們到底之后，回溯的是最近的右結點，很明顯這個是LILO，后進先出

這個明顯是棧，所以我們需要借助于棧實現。

還有一種思路，直接針對遞歸的實現方式，想辦法通過棧來實現遞歸，得到的還是和上面一樣

# # 實現迭代方式的先根遍歷，不管怎么遍歷，首先你必須知道你是如何掃描的，然后再考慮如何遍歷 # 所有的遍歷掃描方式都是，一直往左走，到底回溯，往右走一步，一直往左走，到底回溯，往右走一步。。。 # 在這種掃描方式下，如何實現：回溯，往右走一步？就是提前把往右走的步驟放在一個數組里，回溯的時候 # 直接從數組取出要回溯到哪里，首先我們知道要回溯的結點都是右結點，那我們按照順序掃描的過程中， # 把右結點都放入一個數組，我們到底之后，回溯的是最近的右結點，很明顯這個是LILO，后進先出 # 這個明顯是棧，所以我們需要借助于棧實現。# 還有一種思路，直接針對遞歸的實現方式，想辦法通過棧來實現遞歸，得到的還是和上面一樣 # def preorder(root):pointer = rootstack =[]while pointer:# 這個叫做下行循環，一直向左走，直到走到空樹while pointer:print(pointer.data,end=' ')if pointer.right:stack.append(pointer.right)pointer = pointer.left if stack:# 遇到空樹了，也就是走到底了，回溯pointer = stack.pop() # 這里看見2個while,看起來應該可以簡化，一個while的話下行循環就需要和下行循環一起 # 什么時候彈出了，當前指針為空時彈出，出口了就是沒有元素彈出時為出口 def preorder2(root):pointer = rootstack =[]while pointer:# 這個叫做下行循環，一直向左走，直到走到空樹print(pointer.data,end=' ')if pointer.right:stack.append(pointer.right)pointer = pointer.leftif not pointer and stack:pointer = stack.pop()# 還有一種方案，就是把之前所說的模擬遞歸的操作，這里是把左結點和右結點均放入stack # 這個思路計較簡單，放入時先右后左，彈出時一直都是左 def preorder3(root):stack =[root,]while stack:pointer = stack.pop()print(pointer.data,end=' ')if pointer.right:stack.append(pointer.right)if pointer.left:stack.append(pointer.left)

中根遍歷

# 這里迭代分為2個部分，一是一直往左走，走到空樹，彈出結點 # 彈出結點時，一直彈出，直到彈出的結點的右子樹存在，對右子樹做相同的操作 def inorder(root):stack =[root,]pointer = rootwhile stack:# 下行循環走到底，并把結點都存入進來while pointer:if pointer.left:stack.append(pointer.left)pointer = pointer.left# 一直往上打印結點，直到當前結點的右子樹存在 while stack:pointer = stack.pop()print(pointer.data,end=' ')if pointer.right:pointer = pointer.right stack.append(pointer)breakdef inorder3(root):stack =[]pointer = rootwhile True:# 下行循環走到底，并把結點都存入進來while pointer:stack.append(pointer)pointer = pointer.left# 一直往上打印結點，直到當前結點的右子樹存在 while stack:pointer = stack.pop()print(pointer.data,end=' ')if pointer.right:pointer = pointer.right break# 思考一下退出為什么要放在這里，沒有右結點需要加入而且棧已空的情況下循環退出if not stack:returndef inorder2(root):stack =[]pointer = rootwhile stack or pointer:# 下行循環走到底，并把結點都存入進來while pointer:stack.append(pointer)pointer = pointer.left# 一直往上打印結點，直到當前結點的右子樹存在 ,代碼可以簡化如下# 右邊為空時也是會一直彈出元素pointer = stack.pop()print(pointer.data,end=' ')pointer = pointer.right

后根遍歷

def postorder(root):stack =[root,]pointer = rootwhile stack:# 下行循環走到底，并把結點都存入進來,加入左結點為空，右結點非空，就往右走while pointer:if pointer.left:stack.append(pointer.left)pointer = pointer.leftelif pointer.right:stack.append(pointer.right)pointer = pointer.rightelse:pointer = None# 一直往上打印結點，棧頂 的元素的左兒子是當前結點，把棧頂的元素的右兒子# 問題的關鍵是何時放入右結點while stack:pointer = stack.pop()print(pointer.data,end=' ')if stack and stack[-1].left == pointer and stack[-1].right:pointer = stack[-1].right stack.append(pointer)break def postorder2(root):stack =[]pointer = root# 這個循環體設計得很巧妙while stack or pointer:# 下行循環走到底，并把結點都存入進來while pointer:stack.append(pointer)pointer = pointer.left if pointer.left else pointer.left# 一直往上打印結點，直到當前結點的右子樹存在 ,代碼可以簡化如下# 右邊為空時也是會一直彈出元素pointer = stack.pop()print(pointer.data,end=' ')if stack and stack[-1].left == pointer:pointer = stack[-1].right# 當stack[-1].left ！= pointer時，即右子樹遍歷完畢，我們現在需要遍歷stack[-1]# 直接設置pointer = None就可以直接遍歷了，這里是一個點else:pointer = None

后根還有一種實現方式：

# 后根還有一種實現方式，后根是左右中，先根處理時：右左中的到結果倒敘輸出就是后根處理結果 def postorderBypreorder(root):""":type root: TreeNode:rtype: List[int]"""if root is None:return []stack, output = [root, ], []while stack:root = stack.pop()output.append(root.item)if root.left is not None:stack.append(root.left)if root.right is not None:stack.append(root.right)return output[::-1]

測試結果

root = BinTNode(1,BinTNode(2,BinTNode(4),BinTNode(5)),BinTNode(3,BinTNode(6),BinTNode(7))) print('levelorder:',end='') levelorder(root) print(end='\n') print('preorder:',end='') preorder(root) print(end='\n') print('preorder2:',end='') preorder2(root) print(end='\n') print('preorder3:',end='') preorder3(root) print(end='\n') print('inorder:',end='') inorder(root) print(end='\n') print('inorder2:',end='') inorder2(root) print(end='\n') print('inorder3:',end='') inorder3(root) print(end='\n') print('postorder:',end='') postorder(root) print(end='\n') print('postorder2:',end='') postorder2(root) print(end='\n')runfile('D:/share/test/TreeIteration.py', wdir='D:/share/test') levelorder:1 2 3 4 5 6 7 preorder:1 2 4 5 3 6 7 preorder2:1 2 4 5 3 6 7 preorder3:1 2 4 5 3 6 7 inorder:4 2 5 1 6 3 7 inorder2:4 2 5 1 6 3 7 inorder3:4 2 5 1 6 3 7 postorder:4 5 2 6 7 3 1 postorder2:4 5 2 6 7 3 1 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的树形结构：迭代方式遍历树，宽度优先，先序遍历,中序遍历，后序遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。