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])