數(shù)據(jù)結(jié)構(gòu)之 二叉樹：
什么是二叉樹呢？获询？
這個(gè)問題涨岁，是不可能回答的，這輩子都不可能的吉嚣，請同學(xué)們自行g(shù)oogle,
這篇博客梢薪，寫的真的是圖文并茂，推薦下
二叉查找樹(一)之 圖文解析 和 C語言的實(shí)現(xiàn)
不過我更推薦大家系統(tǒng)的學(xué)習(xí)一下《數(shù)據(jù)結(jié)構(gòu)與算法》這門課尝哆。雖然枯燥而且貌似還用不上秉撇，誰知道呢。较解。一定是有用的畜疾，如果不想一直處于it鏈的底端，還是學(xué)習(xí)一下吧印衔，算我求你們了啡捶。。奸焙。瞎暑。
好！不扯了与帆，真的推薦系統(tǒng)學(xué)習(xí)這門課程了赌。特此推薦一本 《數(shù)據(jù)結(jié)構(gòu)，xx考研xx》 具體不太清楚了玄糟，但是考研類的都大同小異吧勿她，這本書比我本科課本好多了，沒有那么多廢話阵翎，說完概念就是練題逢并。真的墻裂推薦！９馈砍聊！
好！現(xiàn)在就假設(shè)大家都有了二叉樹的基本概念贰军。
那么什么是二叉樹呢玻蝌？？ 哈哈
建議：
在讀文章的時(shí)候強(qiáng)烈建議大家找張紙和筆來词疼，使用畫圖輔助理解８┦鳌＜远瘛蹂季！
數(shù)據(jù)結(jié)構(gòu)本來就比較復(fù)雜国觉，再加上邏輯步驟過多爬凑，我們的大腦只能記住7位步驟左右刊橘，所以還是那句話no picture say j8
另外：建議大家直接讀源碼吧拆檬，很多解釋個(gè)人覺得越說越亂于樟，不好意思Ｎ衩帷！
正文：
- 構(gòu)造二叉樹（構(gòu)造完全二叉樹）
- 改進(jìn)版（構(gòu)造任意二叉樹）
- 廣度優(yōu)先（層次遍歷）
- 深度優(yōu)先（前翘贮，中赊窥，后，序遍歷）
- 遞歸實(shí)現(xiàn)遍歷算法
- 堆棧實(shí)現(xiàn)遍歷算法（推薦 ）
測試代碼：
因?yàn)樗惴ū容^多所以先將測試代碼奉上狸页，請自行測試：
...
def main():
#創(chuàng)建一個(gè)二叉樹對象
tree = B_Tree()
#以此向樹中添加節(jié)點(diǎn)锨能，i == 3的情況表示，一個(gè)空節(jié)點(diǎn)芍耘，看完后面就明白了
for i in range(10):
if i == 3:
i = None
tree.add(i)
#廣度優(yōu)先的層次遍歷算法
print([i.data for i in tree.floor_travel()])
#前址遇，中，后序 遍歷算法（遞歸實(shí)現(xiàn)）
print([i.data for i in tree.front_travel()])
print([i.data for i in tree.middle_travel()])
print([i.data for i in tree.back_travel()])
print('------------------------------------')
#前斋竞，中倔约，后序 遍歷算法（堆棧實(shí)現(xiàn)）
print([i.data for i in tree.front_stank_travel()])
print([i.data for i in tree.middle_stank_travel()])
print([i.data for i in tree.back_stank_travel()])
if __name__ == "__main__":
main()
...
構(gòu)造二叉樹
#二叉樹的節(jié)點(diǎn)
class Node(object):
def __init__(self,data=None,l_child=None, r_child=None):
self.data = data
self.l_child = l_child
self.r_child = r_child
class B_Tree(object):
def __init__(self, node=None):
self.root = node
def add(self, item=None):
node = Node(item)
#如果是空樹，則直接添到根
if not self.root:
self.root = node
else:
#不為空坝初，則按照 左右順序 添加節(jié)點(diǎn),這樣構(gòu)建出來的是一棵有序二叉樹浸剩，且是完全二叉樹
my_queue = []
my_queue.append(self.root)
while True:
cur_node = my_queue.pop(0)
if not cur_node.l_child:
cur_node.l_child = node
return
elif not cur_node.r_child:
cur_node.r_child = node
return
else:
my_queue.append(cur_node.l_child)
my_queue.append(cur_node.r_child)
按照層次遍歷的順序?qū)⒐?jié)點(diǎn)入隊(duì)列，然后判斷該節(jié)點(diǎn)是否有左孩子鳄袍，沒有的話則直接將新節(jié)點(diǎn)掛到下面绢要，否則是右邊，建議同學(xué)們畫圖理解拗小。這就是網(wǎng)上的大多數(shù)版本重罪，這樣構(gòu)建出來的二叉樹是一個(gè)完全二叉樹。那我們怎么才能構(gòu)建一個(gè)更一般的二叉樹呢哀九。一個(gè)節(jié)點(diǎn)雖然是空節(jié)點(diǎn)但是我們不能用None來指代它剿配，我們必須需要一個(gè)Node對象來占位所以我們使用下面的代碼：
class B_Tree(object):
...
def add(self, item=None):
#如果輸入item是None 則表示一個(gè)空節(jié)點(diǎn)
node = Node(data=item)
#如果是空樹，則直接添到根
#此時(shí)判斷空的條件為勾栗，
if not self.root or self.root.data is None:
self.root = node
else:
#不為空惨篱，則按照 左右順序 添加節(jié)點(diǎn)
my_queue = []
my_queue.append(self.root)
while True:
cur_node = my_queue.pop(0)
#即如果該當(dāng)前節(jié)點(diǎn)為空節(jié)點(diǎn)則直接跳過它盏筐，起到一個(gè)占位的作用
if cur_node.data is None:
continue
if not cur_node.l_child:
cur_node.l_child = node
return
elif not cur_node.r_child:
cur_node.r_child = node
return
else:
my_queue.append(cur_node.l_child)
my_queue.append(cur_node.r_child)
可以看到围俘，我們主要是使用了一個(gè) 內(nèi)容為None 的Node對象來占位，代表該節(jié)點(diǎn)是個(gè)空節(jié)點(diǎn)琢融，所以該節(jié)點(diǎn)不會(huì)有后代節(jié)點(diǎn)界牡。從而達(dá)到構(gòu)造更一般的二叉樹的目的，但是我們構(gòu)建時(shí)同樣按照完全二叉樹的順序來構(gòu)建樹漾抬，且必須用None 來占位表示空節(jié)點(diǎn)宿亡。和上面的代碼主要有倆處不同:
-
if not self.root or self.root.data is None:對于根節(jié)點(diǎn)來說，None或者 內(nèi)容為None均表示空樹纳令，因?yàn)閮?nèi)容為None不能有后代節(jié)點(diǎn),對于根來說不合理挽荠，所以讓它相當(dāng)于None克胳，不表示占位作用 -
if cur_node.data is None:此處已經(jīng)是非根節(jié)點(diǎn)了，所以需要一個(gè)空節(jié)點(diǎn)來表示占位作用圈匆，當(dāng)下次添加節(jié)點(diǎn)時(shí)遇到內(nèi)容為None的節(jié)點(diǎn)直接什么都不做漠另，跳過它，此時(shí)會(huì)將節(jié)點(diǎn)添加到下一個(gè)節(jié)點(diǎn)上
廣度優(yōu)先（層次遍歷）
其實(shí)我們在構(gòu)建二叉樹的時(shí)候就是層次遍歷的方式跃赚，這樣構(gòu)建出來的樹笆搓，就是符合完全二叉樹的，遍歷算法如下：
...
#層次遍歷
def floor_travel(self):
#如果是空樹則直接返回一個(gè)[]
if not self.root or self.root.data is None:
return []
else:
my_queue = []
#構(gòu)造個(gè)容器來返回遍歷的結(jié)果
re_queue = []
my_queue.append(self.root)
while my_queue:
cur_node = my_queue.pop(0)
re_queue.append(cur_node)
if cur_node.l_child:
my_queue.append(cur_node.l_child)
if cur_node.r_child:
my_queue.append(cur_node.r_child)
return re_queue
...
前纬傲，中满败，后序遍歷 遞歸實(shí)現(xiàn)
class B_Tree(object):
...
#遞歸，前序遍歷
def front_travel(self):
if not self.root or self.root.data is None:
return []
else:
re_queue = []
def loop(root):
if not root:
return
else:
#中 左 右
re_queue.append(root)
loop(root.l_child)
loop(root.r_child)
loop(self.root)
return re_queue
#遞歸叹括，中序遍歷
def middle_travel(self):
if not self.root or self.root.data is None:
return []
else:
re_queue = []
def loop(root):
if not root:
return
else:
#左 中 右
loop(root.l_child)
re_queue.append(root)
loop(root.r_child)
loop(self.root)
return re_queue
#遞歸算墨，后序遍歷
def back_travel(self):
if not self.root or self.root.data is None:
return []
else:
re_queue = []
def loop(root):
if not root:
return
else:
#左 右 中
loop(root.l_child)
loop(root.r_child)
re_queue.append(root)
loop(self.root)
return re_queue
...
如上，三種遍歷方式领猾，其實(shí)只有遞歸體內(nèi)部的三條語句有點(diǎn)區(qū)別米同，用遞歸真的是很簡單，但是遞歸會(huì)開辟大量的椝じ停空間面粮，會(huì)造成空間的浪費(fèi)，更嚴(yán)重的是继低，如果遞歸深度太深將直接導(dǎo)致程序崩潰熬苍，所以我們推薦使用最后的使用堆棧的實(shí)現(xiàn)方式：
class B_Tree(object):
...
#堆棧 ，前序遍歷：
def front_stank_travel(self):
if not self.root or self.root.data is None:
return []
else:
my_stank = []
my_queue = []
my_stank.append(self.root)
while my_stank:
cur_node = my_stank.pop()
my_queue.append(cur_node)
if cur_node.r_child:
my_stank.append(cur_node.r_child)
if cur_node.l_child:
my_stank.append(cur_node.l_child)
return my_queue
#堆棧 袁翁，中序遍歷：
def middle_stank_travel(self):
if not self.root or self.root.data is None:
return []
else:
my_stank = []
my_queue = []
tmp_list = []
my_stank.append(self.root)
while my_stank:
cur_node = my_stank.pop()
#my_queue.append(cur_node)
if cur_node.r_child and cur_node.r_child not in my_stank:
my_stank.append(cur_node.r_child)
if cur_node.l_child:
if cur_node not in tmp_list:
my_stank.append(cur_node)
tmp_list.append(cur_node)
else:
my_queue.append(cur_node)
tmp_list.remove(cur_node)
continue
my_stank.append(cur_node.l_child)
else:
my_queue.append(cur_node)
return my_queue
def back_stank_travel(self):
if not self.root or self.root.data is None:
return []
else:
my_stank = []
my_queue = []
tmp_list = []
my_stank.append(self.root)
while my_stank:
cur_node = my_stank[-1]
if cur_node.r_child and cur_node not in tmp_list:
my_stank.append(cur_node.r_child)
if cur_node.l_child and cur_node not in tmp_list:
my_stank.append(cur_node.l_child)
if cur_node in tmp_list or (cur_node.l_child is None and cur_node.r_child is None):
my_queue.append(my_stank.pop())
if cur_node in tmp_list:
tmp_list.remove(cur_node)
tmp_list.append(cur_node)
return my_queue
...
說實(shí)話這些方法柴底，寫的我很是不滿意，感覺很復(fù)雜粱胜，但是是自己一中午的成果柄驻，所以還是寫在這分享下。再次強(qiáng)烈建議大家讀函數(shù)的時(shí)候焙压，結(jié)合畫圖來了解鸿脓。其實(shí)網(wǎng)上還有篇博文，它的方法比較簡單點(diǎn) 涯曲，但是思想差不多野哭，建議大家學(xué)習(xí)下python實(shí)現(xiàn)二叉樹和它的七種遍歷
好了，大家有沒有發(fā)現(xiàn)我們每次遍歷都需要做判斷樹是否為空幻件，這樣做真的很麻煩拨黔，我們完全可以使用裝飾器來把代碼裝飾下，不了解裝飾器的同學(xué)可以看下我之前的Python 裝飾器系列绰沥，絕壁比這篇寫的好~~（虛）
好那我們上裝飾器修改后的代碼：
import functools
def is_empty(func):
@functools.wraps(func)
def wrapper(self):
if not self.root or self.root.data is None:
return []
else:
return func(self)
return wrapper
class B_Tree(object):
...
#遞歸篱蝇，前序遍歷
@is_empty
def front_travel(self):
re_queue = []
def loop(root):
if not root:
return
else:
#中 左 右
re_queue.append(root)
loop(root.l_child)
loop(root.r_child)
loop(self.root)
return re_queue
#堆棧 贺待，前序遍歷：
@is_empty
def front_stank_travel(self):
my_stank = []
my_queue = []
my_stank.append(self.root)
while my_stank:
cur_node = my_stank.pop()
my_queue.append(cur_node)
if cur_node.r_child:
my_stank.append(cur_node.r_child)
if cur_node.l_child:
my_stank.append(cur_node.l_child)
return my_queue
...
使用測試代碼同樣可以完美輸出。零截。狠持。
總結(jié)：
構(gòu)建任意的二叉樹，而非完全二叉樹遞歸實(shí)現(xiàn)二叉樹遍歷瞻润，但是空間浪費(fèi)嚴(yán)重推薦使用堆棧的方式實(shí)現(xiàn)二叉樹的遍歷使用裝飾器優(yōu)化代碼墻裂建議使用畫圖輔助４埂！Ｉ茏病正勒！
聲明：
本人也是python 小白，加上數(shù)據(jù)結(jié)構(gòu)本來就比較復(fù)雜傻铣，如果上述內(nèi)容有講的不對的地方還請各位批評指點(diǎn)章贞。將不勝感激，再次感謝~~~
講的不好非洲，還請大家見諒~~~~
