Python数据结构与算法之二叉树结构定义与遍历方法详解

Python  /  管理员 发布于 7年前   173

本文实例讲述了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# 二叉树结点类型class BTNode:  def __init__(self,value,lft=None,rgt=None):    self.value = value    self.lft = lft     # 结点左分支 BTNode    self.rgt = rgt     # 结点右分支 BTNode

为了方便起见，定义一些打印操作

class BinTree():  def __init__(self):    self.root = None  # 创建一个空的二叉树  def isEmpty(self):   # 判断二叉树是否为空    if self.root is None: return True    else: return False  def makeBT(self,bt,L=None,R=None):    # 从当前结点创建二叉树    bt.lft = L    bt.rgt = R  def returnBTdict(self):       # 返回二叉树的字典模式    if self.isEmpty():       return None    def rec(bt=None,R=True):      if R==True:        bt = self.root        return {'root':{'value':bt.value,"L":rec(bt.lft,False),"R":rec(bt.rgt,False)} }      else:        if bt==None:          return None        else:          return {"value":bt.value,  "L":rec(bt.lft,False) if bt.lft != None else None,  "R":rec(bt.rgt,False) if bt.rgt != None else None}      return None    return rec()  def __repr__(self):       # 将二叉树结构打印为字典结构    return str(self.returnBTdict())

下面是各种遍历方法，添加到树的类中

def printT_VLR(self,bt=None,rec_count = 0):   # 输出二叉树结构（先序遍历）    # rec_count 用于计算递归深度 以便输出最后的换行符    """    # 先序遍历    # 访问结点，遍历左子树，如果左子树为空，则遍历右子树，    # 如果右子树为空，则向上走到一个可以向右走的结点，继续该过程    preorder(t):      if t:        print t.value        preorder t.L        preorder t.R    """    if bt==None:       bt = self.root      print bt.value,    btL, btR = bt.lft, bt.rgt    if btL != None:      print btL.value,;  rec_count += 1;   self.printT_VLR(btL,rec_count);   rec_count -= 1    if btR != None:      print btR.value,;  rec_count += 1;   self.printT_VLR(btR,rec_count);   rec_count -= 1    if rec_count == 0:      print "\n"def printT_LVR(self,bt=None):    """    # 中序遍历    # 从根开始，一直走向左下方，直到无结点可以走则停下，访问该节点    # 然后走向右下方到结点，继续走向左下方：如果结点无右孩子，则向上走回父亲结点    inorder(t):      inorder(t.L)      print t.value      inorder(t.R)    """    if bt==None:      bt = self.root    btL, btR = bt.lft, bt.rgt    if btL != None:      self.printT_LVR(btL)    print bt.value,    if btR != None:      self.printT_LVR(btR)def printT_LRV(self,bt=None):    """    # 后序遍历    inorder(t):      inorder(t.L)      inorder(t.R)      print t.value    """    if bt==None:      bt = self.root    btL, btR = bt.lft, bt.rgt    if btL != None:      self.printT_LRV(btL)    if btR != None:      self.printT_LRV(btR)    print bt.value,def printT_levelorder(self):    """    层序遍历 采用队列的遍历操作    第一次访问根，在访问根的左孩子，接着访问根的有孩子，然后下一层    自左向右一一访问同层的结点    """    btdict = self.returnBTdict()    q = []    q.append(btdict['root'])    while q:      tn = q.pop(0)  # 从队列中弹出一个结点(也是一个字典)      print tn["value"],      if tn["L"]!=None:        q.append(tn["L"])      if tn["R"]!=None:        q.append(tn["R"])

测试打印效果

def test():  bt = BinTree()#   btns = [BTNode(v) for v in "+*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) for v in [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程序设计有所帮助。