樹和二叉樹遍歷問題
- 2022 年 3 月 5 日
- 筆記
樹和二叉樹遍歷問題
1.樹和二叉樹與數組(python中的列表)的關係？
樹和二叉樹是一種結構體，而數組(python中的列表)也是一種結構體，並且兩者具有相似的地方。樹和二叉樹在電腦中的存儲可以用數組(python中的列表)來進行存儲，存儲的方式是樹和二叉樹從上到下、從左到右依次進行存儲。
2.樹和二叉樹的遍歷有四種？
(1)可以根據將樹和二叉樹存入到數組(python中的列表)的原則進行遍歷
(2)先序遍歷(先根遍歷)：順序是先根，然後是左子樹，最後是右子樹
(3)中序遍歷(中根遍歷)：順序是左子樹，然後是根，最後是右子樹
(4)後序遍歷(後根遍歷)：順序是左子樹，然後是右子樹，最後是根
遍歷演算法？
樹和二叉樹的定義是具有遞歸的韻味在其中，我們可利用遞歸方法解決樹和二叉樹的遍歷問題
下列方法如圖所示可知：
方法1(先序遍歷)：
def preorde(a,i): //先序遍歷，i表示的是根節點的邏輯位置 if i>len(a)-1: //條件終止是當根節點的邏輯位置大於數組的長度，則說明已經遍歷完了樹或二叉樹 return -1 print(a[i]) //列印根節點的值 preorde(a,2*i+1) //列印左子樹的值 preorde(a,2*i+2) //列印右子樹的值 a=[] for i in input().split(' '): //輸入樹或二叉樹的的各個節點值存入數組的順序 a.append(eval(i)) j=0 preorde(a,0)
方法2(中序遍歷)：
def inorde(a,i): //中序遍歷，i表示的是根節點的邏輯位置 if i>len(a)-1: //條件終止是當根節點的邏輯位置大於數組的長度，則說明已經遍歷完了樹或二叉樹 return -1 inorde(a,2*i+1) //先輸出左子樹的值 print(a[i]) //在輸出根節點的值 inorde(a,2*i+2) //最後輸出右子樹的值 a=[] for i in input().split(' '): a.append(eval(i)) j=0 inorde(a,0)
方法3(後序遍歷)：
def outorde(a,i): if i>len(a)-1: return -1 outorde(a,2*i+1) outorde(a,2*i+2) print(a[i]) a=[] for i in input().split(' '): a.append(eval(i)) j=0 outorde(a,0)
