python二叉樹類以及其4種遍歷方法實(shí)例

第python二叉樹類以及其4種遍歷方法實(shí)例目錄前言實(shí)例代碼：相關(guān)閱讀內(nèi)容：總結(jié)

前言

之前學(xué)習(xí)過(guò)binarytree第三方庫(kù)，了解了它定義的各種基本用法。

昨天在問(wèn)答頻道中做題時(shí)碰到一個(gè)關(guān)于二叉樹的算法填空題，感覺(jué)代碼不錯(cuò)非常值得學(xué)習(xí)，于是整理代碼分享如下：

實(shí)例代碼：

fromcollectionsimportdeque#層遍歷中用到隊(duì)列數(shù)據(jù)類型

classBTNode:#二叉鏈中結(jié)點(diǎn)類

def__init__(self,d=None):

self.data=d#結(jié)點(diǎn)值

self.lchild=None#左hai子指針

self.rchild=None#右hai子指針

classBTree:#二叉樹類

def__init__(self,d=None):

self.b=None#根結(jié)點(diǎn)指針

defDispBTree(self):#返回二叉鏈的括號(hào)表示串

returnself._DispBTree1(self.b)

def_DispBTree1(self,t):#被DispBTree方法調(diào)用

ift==None:#空樹返回空串

return""

else:

bstr=t.data#輸出根結(jié)點(diǎn)值

ift.lchild!=Noneort.rchild!=None:

bstr+="("#有hai子結(jié)點(diǎn)時(shí)輸出"("

bstr+=self._DispBTree1(t.lchild)#遞歸輸出左子樹

ift.rchild!=None:

bstr+=","#有右hai子結(jié)點(diǎn)時(shí)輸出","

bstr+=self._DispBTree1(t.rchild)#遞歸輸出右子樹

bstr+=")"#輸出")"

returnbstr

defFindNode(self,x):#查找值為x的結(jié)點(diǎn)算法

returnself._FindNode1(self.b,x)

def_FindNode1(self,t,x):#被FindNode方法調(diào)用

ift==None:

returnNone#t為空時(shí)返回null

elift.data==x:

returnt#t所指結(jié)點(diǎn)值為x時(shí)返回t

else:

p=self._FindNode1(t.lchild,x)#在左子樹中查找

ifp!=None:

returnp#在左子樹中找到p結(jié)點(diǎn)，返回p

else:

returnself._FindNode1(t.rchild,x)#返回在右子樹中查找結(jié)果

defHeight(self):#求二叉樹高度的算法

returnself._Height1(self.b)

def_Height1(self,t):#被Height方法調(diào)用

ift==None:

return0#空樹的高度為0

else:

lh=self._Height1(t.lchild)#求左子樹高度lchildh

rh=self._Height1(t.rchild)#求右子樹高度rchildh

returnmax(lh,rh)+1

defPreOrder(bt):#先序遍歷的遞歸算法

_PreOrder(bt.b)

def_PreOrder(t):#被PreOrder方法調(diào)用

ift!=None:

print(t.data,end='')#訪問(wèn)根結(jié)點(diǎn)

_PreOrder(t.lchild)#先序遍歷左子樹

_PreOrder(t.rchild)#先序遍歷右子樹

defInOrder(bt):#中序遍歷的遞歸算法

_InOrder(bt.b)

def_InOrder(t):#被InOrder方法調(diào)用

ift!=None:

_InOrder(t.lchild)#中序遍歷左子樹

print(t.data,end='')#訪問(wèn)根結(jié)點(diǎn)

_InOrder(t.rchild)#中序遍歷右子樹

defPostOrder(bt):#后序遍歷的遞歸算法

_PostOrder(bt.b)

def_PostOrder(t):#被PostOrder方法調(diào)用

ift!=None:

_PostOrder(t.lchild)#后序遍歷左子樹

_PostOrder(t.rchild)#后序遍歷右子樹

print(t.data,end='')#訪問(wèn)根結(jié)點(diǎn)

defLevelOrder(bt):#層序遍歷的算法

qu=deque()#將雙端隊(duì)列作為普通隊(duì)列qu

qu.append(bt.b)#根結(jié)點(diǎn)進(jìn)隊(duì)

whilelen(qu)0:#隊(duì)不空循環(huán)

p=qu.popleft()#出隊(duì)一個(gè)結(jié)點(diǎn)

print(p.data,end='')#訪問(wèn)p結(jié)點(diǎn)

ifp.lchild!=None:#有左hai子時(shí)將其進(jìn)隊(duì)

qu.append(p.lchild)

ifp.rchild!=None:#有右hai子時(shí)將其進(jìn)隊(duì)

qu.append(p.rchild)

defCreateBTree2(posts,ins):#由后序序列posts和中序序列ins構(gòu)造二叉鏈

bt=BTree()

bt.b=_CreateBTree2(posts,0,ins,0,len(posts))

returnbt

def_CreateBTree2(posts,i,ins,j,n):

ifn=0:

returnNone

d=posts[i+n-1]#取后序序列尾元素d

t=BTNode(d)#創(chuàng)建根結(jié)點(diǎn)(結(jié)點(diǎn)值為d)

p=ins.index(d)#在ins中找到根結(jié)點(diǎn)的索引

k=p-j#確定左子樹中結(jié)點(diǎn)個(gè)數(shù)k

t.lchild=_CreateBTree2(posts,i,ins,j,k)#遞歸構(gòu)造左子樹

t.rchild=_CreateBTree2(posts,i+k,ins,p+1,n-k-1)#遞歸構(gòu)造右子樹

returnt

if__name__=='__main__':

inlst=['D','G','B','A','E','C','F']

posts=['G','D','B','E','F','C','A']

print(f"中序列表：{inlst}")

print(f"后序列表：{posts}")

#構(gòu)造二叉樹bt

bt=BTree()

bt=CreateBTree2(posts,inlst)

print(f"\n構(gòu)造二叉樹：{bt.DispBTree()}")

x='F'

ifbt.FindNode(x):

print(f"bt中存在：'{x}'")

else:

print(f"bt中不存在：'{x}'")

print(f"bt的高度：{bt.Height():^3}")

print("\n先序遍歷：",end='')

PreOrder(bt)

print("\n中序遍歷列：",end='')

InOrder(bt)

print("\n后序遍歷：",end='')

PostOrder(bt)

print("\n層序遍歷：",end='')

LevelOrder(bt)

中序列表：[D,G,B,A,E,C,F]

后序列表：[G,D,B,E,F,C,A]

構(gòu)造二叉樹：A(B(D(,G),C(E,F))

bt中存在：F

bt的高度：4