二叉樹遍歷python

1. python中yield和return究竟有什麼區別，怎麼用

常看到別人使用或討論yield語法,能搜到的中文解釋卻不多,今天決心搞定yield,把暫時的理解貼到這里.

搞定yield之前: 疊代器(iterator)

發現yield: 生成器(constructor)

使用yield: 遞歸調用

1. iterator

疊代器最簡單例子應該是數組下標了，且看下面的c++代碼：

int array[10];

for ( int i = 0; i < 10; i++ )

printf("%d ", array[i]);

疊代器工作在一個容器里(array[10])，它按一定順序(i++)從容器里取出值(array[i])並進行操作(printf("%d ", array[i])。

上面的代碼翻譯成python：

array = [i for i in range(10)]

for i in array:

print i,

for i in array幹了什麼(別亂想)？首先，array作為一個list是個容器，其次list這個內建類型有默認的next行為，python發現這些之後采 取的秘密的沒被各位看到的動作是：拿出array這丫容器的疊代器，從裡面next一下把值給i供for循環主體處置，for把這個值print了。

現在的問題是數據可以做容器疊代，代碼可以嗎？

怎麼不行，碗碟可以用來放菜，wk們不就聯想出用nt盛嗎，當然我們的yield不會那麼yellow + bt

2. constructor

怎麼把函數變成constructor？ 在函數體里有yield就行了！

def gen():
print 'enter'
yield 1
print 'next'
yield 2
print 'next again'

for i in gen():
print i

各位！python看到gen函數里出現yield，知道可以用next了，問題是怎麼對代碼這個容器玩next？

從容器里拿到iterator的時候它還什麼也不是，處在容器入口處，對於數組來說就是下標為-1的地方，對於函數來說就是函數入口嘛事沒干，但是萬事俱備就欠next。

開始for i in g，next讓itreator爬行到yield語句存在的地方並返回值,

再次next就再爬到下一個yield語句存在的地方並返回值,依次這樣直到函數返回(容器盡頭)。
您一定看出來上面代碼的輸出是：

enter
1
next
2
next again

如果沒看出來請不要往下看了免得反被yield搞定。

3. 使用yield

yield的代碼疊代能力不但能打斷函數執行還能記下斷點處的數據，下次next書接上回，這正是遞歸函數需要的。

例如中序遍歷二叉樹：

(應該是David Mertz寫的)

def inorder(t):
if t:
for x in inorder(t.left):
yield x
yield t.label
for x in inorder(t.right):
yield x

for n in inorder(tree)

print n

當然yield這種代碼next的能力還可以用在其它方面，發現拍案的在貼咯。

2. 樹.層序遍歷的三種實現演算法

樹層序遍歷的三種實現演算法如下：

1. 隊列法：

   • 核心思路：利用隊列先進先出的特性，逐層遍歷二叉樹。首先將根節點入隊，然後進入一個循環，每次循環處理當前隊列中的所有節點，並將它們的子節點入隊。循環直到隊列為空。
   • 實現細節：在每次循環開始時，記錄隊列的大小，然後依次處理這些節點。處理節點時，將其值添加到當前層的結果列表中，並將其左右子節點入隊。

2. 遞歸與棧的結合：

   • 核心思路：通過遞歸和棧的結合來實現層序遍歷。使用一個自定義的節點類，將根節點及其層數壓入棧中。然後進入一個循環，每次循環從棧中彈出一個節點，將其值添加到對應層的結果列表中，並將其左右子節點壓入棧中。
   • 實現細節：在每次彈出節點時，檢查結果列表的大小是否等於當前節點的層數，如果是，則在結果列表中添加一個新的空列表作為當前層的結果容器。然後將節點的值添加到當前層的結果列表中。

3. Python版實現：

   • 核心思路：與遞歸與棧的結合方法類似，但使用Python的列表來模擬棧，並簡化了一些操作。同樣使用一個自定義的節點類來存儲節點值和層數信息。
   • 實現細節：初始化一個棧，將根節點及其層數壓入棧中。然後進入一個循環，每次循環從棧中彈出一個節點，將其值添加到對應層的結果列表中。然後將節點的左右子節點壓入棧中。

這三種方法各有優缺點，隊列法直觀易懂，遞歸與棧的結合方法在處理復雜情況時可能更加靈活，而Python版實現則利用了Python的語言特性使代碼更加簡潔。在實際應用中，可以根據具體需求和場景選擇合適的方法。

3. python二叉樹輸出結果為什麼是這樣

1. 二叉樹

二叉樹(binary tree)中的每個節點都不能有多於兩個的兒子。

圖 ((7+3)*(5-2))的表達式樹表示

2.1 根據中綴表達式構造表達式樹：

遍歷表達式：

1.建立一個空樹

2.遇到'('，為當前的Node添加一個left child，並將left child當做當前Node。

3.遇到數字，賦值給當前的Node，並返回parent作為當前Node。

4.遇到('+-*/')，賦值給當前Node，並添加一個Node作為right child，將right child當做當前的Node。

5.遇到')',返回當前Node的parent。

defbuildexpressionTree(exp):tree=BinaryTree('')stack=[]stack.append(tree)currentTree=treeforiinexp:ifi=='(':currentTree.insertLeft('')stack.append(currentTree)currentTree=currentTree.leftChildelifinotin'+-*/()':currentTree.key=int(i)parent=stack.pop()currentTree=parentelifiin'+-*/':currentTree.key=icurrentTree.insertRight('')stack.append(currentTree)currentTree=currentTree.rightChildelifi==')':currentTree=stack.pop()else:raiseValueErrorreturntree

上述演算法對中綴表達式的寫法要求比較繁瑣，小括弧應用太多，例如要寫成(a+(b*c))的形式。

用後綴表達式構建表達式樹會方便一點:如果符號是操作數，建立一個單節點並將一個指向它的指針推入棧中。如果符號是一個操作符，從棧中彈出指向兩棵樹T1和T2的指針並形成一棵新的樹，樹的根為此操作符，左右兒子分別指向T2和T1.

123456789101112131415defbuild_tree_with_post(exp):stack=[]oper='+-*/'foriinexp:ifinotinoper:tree=BinaryTree(int(i))stack.append(tree)else:righttree=stack.pop()lefttree=stack.pop()tree=BinaryTree(i)tree.leftChild=lefttreetree.rightChild=righttreestack.append(tree)returnstack.pop()

3.樹的遍歷

3.1 先序遍歷(preorder travelsal)

先列印出根，然後遞歸的列印出左子樹、右子樹，對應先綴表達式

12345678defpreorder(tree,nodelist=None):ifnodelistisNone:nodelist=[]iftree:nodelist.append(tree.key)preorder(tree.leftChild,nodelist)preorder(tree.rightChild,nodelist)returnnodelist

3.2 中序遍歷(inorder travelsal)

先遞歸的列印左子樹，然後列印根，最後遞歸的列印右子樹，對應中綴表達式

12345definorder(tree):iftree:inorder(tree.leftChild)printtree.keyinorder(tree.rightChild)

3.3 後序遍歷(postorder travelsal)

遞歸的列印出左子樹、右子樹，然後列印根，對應後綴表達式

1234567defpostorder(tree):iftree:forkeyinpostorder(tree.leftChild):yieldkeyforkeyinpostorder(tree.rightChild):yieldkeyyieldtree.key

3.4 表達式樹的求值

1234567891011defpostordereval(tree):operators={'+':operator.add,'-':operator.sub,'*':operator.mul,'/':operator.truediv}leftvalue=Nonerightvalue=Noneiftree:leftvalue=postordereval(tree.leftChild)rightvalue=postordereval(tree.rightChild)ifleftvalueandrightvalue:returnoperators[tree.key](leftvalue,rightvalue)else:returntree.key

4. Python演算法系列—深度優先遍歷演算法

一、什麼是深度優先遍歷
深度優先遍歷演算法是經典的圖論演算法。從某個節點v出發開始進行搜索。不斷搜索直到該節點所有的邊都被遍歷完，當節點v所有的邊都被遍歷完以後，深度優先遍歷演算法則需要回溯到v以前驅節點來繼續搜索這個節點。
注意：深度優先遍歷問題一定要按照規則嘗試所有的可能才行。

二、二叉樹

2.二叉樹類型
二叉樹類型：空二叉樹、滿二叉樹、完全二叉樹、完美二叉樹、平衡二叉樹。

空二叉樹：有零個節點
完美二叉樹：每一層節點都是滿的二叉樹（如1中舉例的圖）
滿二叉樹：每一個節點都有零個或者兩個子節點
完全二叉樹：出最後一層外，每一層節點都是滿的，並且最後一層節點全部從左排列
平衡二叉樹：每個節點的兩個子樹的深度相差不超過1.

註：國內對完美二叉樹和滿二叉樹定義相同
3.二叉樹相關術語
術語 解釋
度 節點的度為節點的子樹個數
葉子節點 度為零的節點
分支節點 度不為零的節點
孩子節點 節點下的兩個子節點
雙親節點 節點上一層的源節點
兄弟節點 擁有同一雙親節點的節點
根 二叉樹的源頭節點
深度 二叉樹中節點的層的數量

DLR（先序）：
LDR（中序）：
LRD(後序）：
注意：L代表左子樹R代表右子樹；D代表根

6.深度優先遍歷和廣度優先遍歷
深度優先遍歷：前序、中序和後序都是深度優先遍歷
從根節點出發直奔最遠節點，
廣度優先遍歷：首先訪問舉例根節點最近的節點，按層次遞進，以廣度優先遍歷上圖的順序為：1-2-3-4-5-6-7
三、面試題+勵志
企鵝運維面試題：
1.二叉樹遍歷順序：看上文
2.用你熟悉的語言說說怎麼創建二叉樹？ python看上文