二叉樹的遍歷——遞回非遞回實作-有解無憂

一、簡介　

　　二叉樹的三種遍歷方式我相信大家都了然于心，前序遍歷、中序遍歷、后序遍歷，對于這三種遍歷的遞回實作，我們都不容易忘記，不過，對于非遞回實作，我相信會有很多人會跟我一樣，背了忘，再背再忘......（很多演算法題都是這樣，比如各種排序演算法的實作），經過認真觀察思考后，發現實作起來是那么的簡單，只要記住三者遍歷順序就夠了，前序遍歷，先訪問父節點（中）、然后左子樹（左）、最后右子樹（右）；中序遍歷：左、中、右；后序遍歷：左、右、中，如果還不明白這三種遍歷方式的訪問順序，建議去看看影片的教程，

二、遞回實作

　　遞回實作結構很好記，上來寫兩遞回，遞回左子樹，遞回右子樹，前序遍歷，訪問節點（列印節點）在兩個遞回前面——中、左、右；中序遍歷，訪問放遞回中間——左中右；后序遍歷，先兩遞回，最后才訪問——左、中、右，

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 
 9 def preorder_with_recursion(root):          
10         if root is None:
11             return
12       
13         print(root.val)
14         preorder_with_recursion(root.left)
15         preorder_with_recursion(root.right) 
16 
17 
18 def inorder_with_recursion( root):
19         if root is None:
20             return 
21 
22         inorder_with_recursion(root.left)
23         print(root.val)
24         inorder_with_recursion(root.right)
25 
26 
27 def postorder_with_recursion(root):
28         if root is None:
29             return 
30 
31         postorder_with_recursion(root.left)
32         postorder_with_recursion(root.right)
33         print(root.val)
34

三、非遞回實作

　非遞回不外乎就是我們自己維護一個堆疊結構，來控制出堆疊、進堆疊的時機，對于前序遍歷（中、左、右），因為先列印父節點，因此我們每回圈一次，就可以出堆疊列印，并且將右孩子和左孩子壓入堆疊中；中序遍歷（左、中、右），先列印最左子樹，我們可以不斷地將左節點壓入堆疊中，直到左子節點為空，出堆疊列印，并判斷有孩子是否存在，如果存在則壓入堆疊并重復查找最左子程序，如果不存在右孩子，則繼續出堆疊列印，后序遍歷（左、右、中），訪問左子樹跟中序遍歷的方式相同，唯一區別的是，因為得先列印右子樹，因此把這節點繼續存入堆疊（并處理為已訪問），讓右子樹先進堆疊出堆疊，最后才輪到該節點列印，

 1 def preorder_with_loop(root):
 2     if root is None:
 3         return
 4 
 5     stack = []
 6     stack.append(root)
 7     while stack:
 8         cur = stack.pop()
 9         print(cur.val)
10         if cur.right:
11             stack.append(cur.right)
12         if cur.left:
13             stack.append(cur.left)
14 
15 
16 def inorder_for_loop(root):
17     if root is None:
18         return
19 
20     stack = []
21     cur = root
22     while cur or stack:
23         if cur:
24             stack.append(cur)
25             cur = cur.left
26         else:
27             cur = stack.pop()
28             print(cur.val)
29             cur = cur.right
30 
31 
32 def postorder_with_loop(root): 
33     if root is None:
34         return
35 
36     stack = []
37     cur = root
38     while cur or stack:
39         if cur:
40             stack.append(cur)
41             cur = cur.left
42         else:
43             cur = stack.pop()
44             # 先判斷有沒有右子樹，如果沒有直接列印，如果有，繼續入堆疊，等右子樹先出堆疊列印，
45             if cur.right:
46                 right = cur.right
47                 """
48                 第二次入堆疊，右子樹也隨后入堆疊，因此將右子樹設定為None來控制
49                 下次出堆疊時到可以列印，而不是再次訪問右子樹進入死回圈，
50                 """
51                 cur.right = None
52                 stack.append(cur)
53                 cur = right
54             else:
55                 print(cur.val)
56                 cur = None

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/53398.html

標籤：其他

上一篇：【求助關于通信協議的問題】

下一篇：Unity 保存與打開