本文實(shí)例講述了Python實(shí)現(xiàn)二叉樹及遍歷方法。分享給大家供大家參考，具體如下：

介紹：

樹是數(shù)據(jù)結(jié)構(gòu)中非常重要的一種，主要的用途是用來提高查找效率，對于要重復(fù)查找的情況效果更佳，如二叉排序樹、FP-樹。另外可以用來提高編碼效率，如哈弗曼樹。

代碼：

用Python實(shí)現(xiàn)樹的構(gòu)造和幾種遍歷算法，雖然不難，不過還是把代碼作了一下整理總結(jié)。實(shí)現(xiàn)功能：

① 樹的構(gòu)造
② 遞歸實(shí)現(xiàn)先序遍歷、中序遍歷、后序遍歷
③ 堆棧實(shí)現(xiàn)先序遍歷、中序遍歷、后序遍歷
④ 隊列實(shí)現(xiàn)層次遍歷

#coding=utf-8class Node(object):  """節(jié)點(diǎn)類"""  def __init__(self, elem=-1, lchild=None, rchild=None):    self.elem = elem    self.lchild = lchild    self.rchild = rchildclass Tree(object):  """樹類"""  def __init__(self):    self.root = Node()    self.myQueue = []  def add(self, elem):    """為樹添加節(jié)點(diǎn)"""    node = Node(elem)    if self.root.elem == -1: # 如果樹是空的，則對根節(jié)點(diǎn)賦值      self.root = node      self.myQueue.append(self.root)    else:      treeNode = self.myQueue[0] # 此結(jié)點(diǎn)的子樹還沒有齊。      if treeNode.lchild == None:        treeNode.lchild = node        self.myQueue.append(treeNode.lchild)      else:        treeNode.rchild = node        self.myQueue.append(treeNode.rchild)        self.myQueue.pop(0) # 如果該結(jié)點(diǎn)存在右子樹，將此結(jié)點(diǎn)丟棄。  def front_digui(self, root):    """利用遞歸實(shí)現(xiàn)樹的先序遍歷"""    if root == None:      return    print root.elem,    self.front_digui(root.lchild)    self.front_digui(root.rchild)  def middle_digui(self, root):    """利用遞歸實(shí)現(xiàn)樹的中序遍歷"""    if root == None:      return    self.middle_digui(root.lchild)    print root.elem,    self.middle_digui(root.rchild)  def later_digui(self, root):    """利用遞歸實(shí)現(xiàn)樹的后序遍歷"""    if root == None:      return    self.later_digui(root.lchild)    self.later_digui(root.rchild)    print root.elem,  def front_stack(self, root):    """利用堆棧實(shí)現(xiàn)樹的先序遍歷"""    if root == None:      return    myStack = []    node = root    while node or myStack:      while node:           #從根節(jié)點(diǎn)開始，一直找它的左子樹        print node.elem,        myStack.append(node)        node = node.lchild      node = myStack.pop()      #while結(jié)束表示當(dāng)前節(jié)點(diǎn)node為空，即前一個節(jié)點(diǎn)沒有左子樹了      node = node.rchild         #開始查看它的右子樹  def middle_stack(self, root):    """利用堆棧實(shí)現(xiàn)樹的中序遍歷"""    if root == None:      return    myStack = []    node = root    while node or myStack:      while node:           #從根節(jié)點(diǎn)開始，一直找它的左子樹        myStack.append(node)        node = node.lchild      node = myStack.pop()      #while結(jié)束表示當(dāng)前節(jié)點(diǎn)node為空，即前一個節(jié)點(diǎn)沒有左子樹了      print node.elem,      node = node.rchild         #開始查看它的右子樹  def later_stack(self, root):    """利用堆棧實(shí)現(xiàn)樹的后序遍歷"""    if root == None:      return    myStack1 = []    myStack2 = []    node = root    myStack1.append(node)    while myStack1:          #這個while循環(huán)的功能是找出后序遍歷的逆序，存在myStack2里面      node = myStack1.pop()      if node.lchild:        myStack1.append(node.lchild)      if node.rchild:        myStack1.append(node.rchild)      myStack2.append(node)    while myStack2:             #將myStack2中的元素出棧，即為后序遍歷次序      print myStack2.pop().elem,  def level_queue(self, root):    """利用隊列實(shí)現(xiàn)樹的層次遍歷"""    if root == None:      return    myQueue = []    node = root    myQueue.append(node)    while myQueue:      node = myQueue.pop(0)      print node.elem,      if node.lchild != None:        myQueue.append(node.lchild)      if node.rchild != None:        myQueue.append(node.rchild)if __name__ == '__main__':  """主函數(shù)"""  elems = range(10)      #生成十個數(shù)據(jù)作為樹節(jié)點(diǎn)  tree = Tree()     #新建一個樹對象  for elem in elems:    tree.add(elem)      #逐個添加樹的節(jié)點(diǎn)  print '隊列實(shí)現(xiàn)層次遍歷:'  tree.level_queue(tree.root)  print '/n/n遞歸實(shí)現(xiàn)先序遍歷:'  tree.front_digui(tree.root)  print '/n遞歸實(shí)現(xiàn)中序遍歷:'  tree.middle_digui(tree.root)  print '/n遞歸實(shí)現(xiàn)后序遍歷:'  tree.later_digui(tree.root)  print '/n/n堆棧實(shí)現(xiàn)先序遍歷:'  tree.front_stack(tree.root)  print '/n堆棧實(shí)現(xiàn)中序遍歷:'  tree.middle_stack(tree.root)  print '/n堆棧實(shí)現(xiàn)后序遍歷:'  tree.later_stack(tree.root)