Python数据结构与算法之二叉树结构定义与遍历方法详解
本文实例讲述了Python数据结构与算法之二叉树结构定义与遍历方法。分享给大家供大家参考，具体如下：
先序遍历，中序遍历，后序遍历，区别在于三条核心语句的位置
层序遍历 采用队列的遍历操作第一次访问根，在访问根的左孩子，接着访问根的有孩子，然后下一层自左向右一一访问同层的结点
#先序遍历 #访问结点，遍历左子树，如果左子树为空，则遍历右子树， #如果右子树为空，则向上走到一个可以向右走的结点，继续该过程 preorder(t): ift: printt.value preordert.L preordert.R #中序遍历 #从根开始，一直走向左下方，直到无结点可以走则停下，访问该节点 #然后走向右下方到结点，继续走向左下方：如果结点无右孩子，则向上走回父亲结点 inorder(t): inorder(t.L) printt.value inorder(t.R) #后序遍历 inorder(t): inorder(t.L) inorder(t.R) printt.value #二叉树结点类型 classBTNode: def__init__(self,value,lft=None,rgt=None): self.value=value self.lft=lft#结点左分支BTNode self.rgt=rgt#结点右分支BTNode
为了方便起见，定义一些打印操作
classBinTree():
def__init__(self):
self.root=None#创建一个空的二叉树
defisEmpty(self):#判断二叉树是否为空
ifself.rootisNone:returnTrue
else:returnFalse
defmakeBT(self,bt,L=None,R=None):#从当前结点创建二叉树
bt.lft=L
bt.rgt=R
defreturnBTdict(self):#返回二叉树的字典模式
ifself.isEmpty():
returnNone
defrec(bt=None,R=True):
ifR==True:
bt=self.root
return{'root':{'value':bt.value,"L":rec(bt.lft,False),
"R":rec(bt.rgt,False)}}
else:
ifbt==None:
returnNone
else:
return{"value":bt.value,
"L":rec(bt.lft,False)ifbt.lft!=NoneelseNone,
"R":rec(bt.rgt,False)ifbt.rgt!=NoneelseNone}
returnNone
returnrec()
def__repr__(self):#将二叉树结构打印为字典结构
returnstr(self.returnBTdict())
下面是各种遍历方法，添加到树的类中
defprintT_VLR(self,bt=None,rec_count=0):#输出二叉树结构（先序遍历） #rec_count用于计算递归深度以便输出最后的换行符 """ #先序遍历 #访问结点，遍历左子树，如果左子树为空，则遍历右子树， #如果右子树为空，则向上走到一个可以向右走的结点，继续该过程 preorder(t): ift: printt.value preordert.L preordert.R """ ifbt==None: bt=self.root printbt.value, btL,btR=bt.lft,bt.rgt ifbtL!=None: printbtL.value,;rec_count+=1;self.printT_VLR(btL,rec_count);rec_count-=1 ifbtR!=None: printbtR.value,;rec_count+=1;self.printT_VLR(btR,rec_count);rec_count-=1 ifrec_count==0: print"\n" defprintT_LVR(self,bt=None): """ #中序遍历 #从根开始，一直走向左下方，直到无结点可以走则停下，访问该节点 #然后走向右下方到结点，继续走向左下方：如果结点无右孩子，则向上走回父亲结点 inorder(t): inorder(t.L) printt.value inorder(t.R) """ ifbt==None: bt=self.root btL,btR=bt.lft,bt.rgt ifbtL!=None: self.printT_LVR(btL) printbt.value, ifbtR!=None: self.printT_LVR(btR) defprintT_LRV(self,bt=None): """ #后序遍历 inorder(t): inorder(t.L) inorder(t.R) printt.value """ ifbt==None: bt=self.root btL,btR=bt.lft,bt.rgt ifbtL!=None: self.printT_LRV(btL) ifbtR!=None: self.printT_LRV(btR) printbt.value, defprintT_levelorder(self): """ 层序遍历采用队列的遍历操作 第一次访问根，在访问根的左孩子，接着访问根的有孩子，然后下一层 自左向右一一访问同层的结点 """ btdict=self.returnBTdict() q=[] q.append(btdict['root']) whileq: tn=q.pop(0)#从队列中弹出一个结点(也是一个字典) printtn["value"], iftn["L"]!=None: q.append(tn["L"]) iftn["R"]!=None: q.append(tn["R"])
测试打印效果
deftest(): bt=BinTree() #btns=[BTNode(v)forvin"+*E*D/CAB"]#层序输入 #bt.root=btns[0] #bt.makeBT(btns[0],L=btns[1],R=btns[2]) #bt.makeBT(btns[1],L=btns[3],R=btns[4]) #bt.makeBT(btns[3],L=btns[5],R=btns[6]) #bt.makeBT(btns[5],L=btns[7],R=btns[8]) btns=[BTNode(v)forvin[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]] bt.root=btns[0] bt.makeBT(btns[0],L=btns[1],R=btns[2]) bt.makeBT(btns[1],L=btns[3],R=btns[4]) bt.makeBT(btns[2],L=btns[5],R=btns[6]) bt.makeBT(btns[3],L=btns[7],R=btns[8]) bt.makeBT(btns[4],L=btns[9],R=btns[10]) bt.makeBT(btns[5],L=btns[11],R=btns[12]) bt.makeBT(btns[6],L=btns[13],R=btns[14])
输出：
{'root':{'R':{'R':{'R':{'R':None,'L':None,'value':15},'L':{'R':None,'L':None,'value':14},'value':7},'L':{'R':{'R':None,'L':None,'value':13},'L':{'R':None,'L':None,'value':12},'value':6},'value':3},'L':{'R':{'R':{'R':None,'L':None,'value':11},'L':{'R':None,'L':None,'value':10},'value':5},'L':{'R':{'R':None,'L':None,'value':9},'L':{'R':None,'L':None,'value':8},'value':4},'value':2},'value':1}}
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。