python数据结构与算法——二叉树结构与遍历方法,,先序遍历,中序遍历,
python数据结构与算法——二叉树结构与遍历方法,,先序遍历,中序遍历,
先序遍历,中序遍历,后序遍历 ,区别在于三条核心语句的位置
层序遍历 采用队列的遍历操作第一次访问根,在访问根的左孩子,接着访问根的有孩子,然后下一层自左向右一一访问同层的结点
# 先序遍历
# 访问结点,遍历左子树,如果左子树为空,则遍历右子树,
# 如果右子树为空,则向上走到一个可以向右走的结点,继续该过程
preorder(t):
if t:
print t.value
preorder t.L
preorder t.R
# 中序遍历
# 从根开始,一直走向左下方,直到无结点可以走则停下,访问该节点
# 然后走向右下方到结点,继续走向左下方:如果结点无右孩子,则向上走回父亲结点
inorder(t):
inorder(t.L)
print t.value
inorder(t.R)
# 后序遍历
inorder(t):
inorder(t.L)
inorder(t.R)
print t.value
1 # 二叉树结点类型2 class BTNode:3 def __init__(self,value,lft=None,rgt=None):4 self.value = value5 self.lft = lft # 结点左分支 BTNode6 self.rgt = rgt # 结点右分支 BTNode
为了方便起见,定义一些打印操作
1 class BinTree(): 2 def __init__(self): 3 self.root = None # 创建一个空的二叉树 4 5 def isEmpty(self): # 判断二叉树是否为空 6 if self.root is None: return True 7 else: return False 8 9 def makeBT(self,bt,L=None,R=None): # 从当前结点创建二叉树10 bt.lft = L11 bt.rgt = R12 13 def returnBTdict(self): # 返回二叉树的字典模式14 if self.isEmpty(): 15 return None16 def rec(bt=None,R=True):17 if R==True:18 bt = self.root19 return {‘root‘:{‘value‘:bt.value,"L":rec(bt.lft,False),20 "R":rec(bt.rgt,False)} }21 else:22 if bt==None:23 return None24 else:25 return {"value":bt.value,26 "L":rec(bt.lft,False) if bt.lft != None else None,27 "R":rec(bt.rgt,False) if bt.rgt != None else None}28 return None29 return rec()30 31 def __repr__(self): # 将二叉树结构打印为字典结构32 return str(self.returnBTdict())
下面是各种遍历方法,添加到树的类中
1 def printT_VLR(self,bt=None,rec_count = 0): # 输出二叉树结构(先序遍历) 2 # rec_count 用于计算递归深度 以便输出最后的换行符 3 """ 4 # 先序遍历 5 # 访问结点,遍历左子树,如果左子树为空,则遍历右子树, 6 # 如果右子树为空,则向上走到一个可以向右走的结点,继续该过程 7 preorder(t): 8 if t: 9 print t.value10 preorder t.L11 preorder t.R12 """13 if bt==None: 14 bt = self.root15 print bt.value,16 btL, btR = bt.lft, bt.rgt17 if btL != None:18 print btL.value,; rec_count += 1; self.printT_VLR(btL,rec_count); rec_count -= 119 if btR != None:20 print btR.value,; rec_count += 1; self.printT_VLR(btR,rec_count); rec_count -= 121 if rec_count == 0:22 print "\n"23
1 def printT_LVR(self,bt=None): 2 """ 3 # 中序遍历 4 # 从根开始,一直走向左下方,直到无结点可以走则停下,访问该节点 5 # 然后走向右下方到结点,继续走向左下方:如果结点无右孩子,则向上走回父亲结点 6 inorder(t): 7 inorder(t.L) 8 print t.value 9 inorder(t.R)10 """11 if bt==None:12 bt = self.root13 btL, btR = bt.lft, bt.rgt14 if btL != None:15 self.printT_LVR(btL)16 17 print bt.value,18 19 if btR != None:20 self.printT_LVR(btR)
1 def printT_LRV(self,bt=None): 2 """ 3 # 后序遍历 4 inorder(t): 5 inorder(t.L) 6 inorder(t.R) 7 print t.value 8 """ 9 if bt==None:10 bt = self.root11 btL, btR = bt.lft, bt.rgt12 if btL != None:13 self.printT_LRV(btL)14 if btR != None:15 self.printT_LRV(btR)16 print bt.value,
1 def printT_levelorder(self): 2 """ 3 层序遍历 采用队列的遍历操作 4 第一次访问根,在访问根的左孩子,接着访问根的有孩子,然后下一层 5 自左向右一一访问同层的结点 6 """ 7 btdict = self.returnBTdict() 8 q = [] 9 q.append(btdict[‘root‘])10 while q:11 tn = q.pop(0) # 从队列中弹出一个结点(也是一个字典)12 print tn["value"],13 if tn["L"]!=None:14 q.append(tn["L"])15 if tn["R"]!=None:16 q.append(tn["R"])17
测试打印效果
1 def test(): 2 bt = BinTree() 3 4 # btns = [BTNode(v) for v in "+*E*D/CAB"] # 层序输入 5 # bt.root = btns[0] 6 # bt.makeBT(btns[0], L=btns[1], R=btns[2]) 7 # bt.makeBT(btns[1], L=btns[3], R=btns[4]) 8 # bt.makeBT(btns[3], L=btns[5], R=btns[6]) 9 # bt.makeBT(btns[5], L=btns[7], R=btns[8])10 11 btns = [BTNode(v) for v in [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]]12 bt.root = btns[0]13 bt.makeBT(btns[0], L=btns[1], R=btns[2])14 bt.makeBT(btns[1], L=btns[3], R=btns[4])15 bt.makeBT(btns[2], L=btns[5], R=btns[6])16 bt.makeBT(btns[3], L=btns[7], R=btns[8])17 bt.makeBT(btns[4], L=btns[9], R=btns[10])18 bt.makeBT(btns[5], L=btns[11], R=btns[12])19 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数据结构与算法——二叉树结构与遍历方法
相关内容
- 暂无相关文章
评论关闭