本文實例為大家分享了python實現(xiàn)二叉樹的遍歷具體代碼，供大家參考，具體內(nèi)容如下

代碼：

# -*- coding: gb2312 -*-  class Queue(object):    def __init__(self):     self.q = []    def enqueue(self, item):     self.q.append(item)    def dequeue(self):     # if self.q != []:     if len(self.q)>0:        return self.q.pop(0)            else:       return None    def length(self):     return len(self.q)    def isempty(self):     return len(self.q)==0  class Stack(object):   def __init__(self):     self.s = []    def push(self, item):     self.s.append(item)    def pop(self):     if self.s !=[]:       item = self.s.pop(-1)     else:       item = None     return item    def length(self):     return len(self.s)    def isempty(self):     return self.s == []    def top(self):     return self.s[-1]  class TreeNode(object):    def __init__(self, data, left=None, right=None):     self.data = data     self.left = left     self.right = right     self.visited = False    def setData(self, data):     self.data = data    def setLeft(self, left):     self.left = left    def setRight(self, right):     self.right = right    def visit(self):     print self.data,     self.visited = True    def deVisit(self):     self.visited = False  class BinaryTree(object):   def __init__(self, root):     self.root = root    # 前序遍歷(遞歸)   def freshVisit(self, node):     if node is not None:       node.deVisit()     if node.left:       self.freshVisit(node.left)     if node.right:       self.freshVisit(node.right)    # 前序遍歷(遞歸)   def preOrder(self, node):     if node is not None:       node.visit()     if node.left:       self.preOrder(node.left)     if node.right:       self.preOrder(node.right)    # 中序遍歷(遞歸)   def inOrder(self, node):     if node.left:       self.inOrder(node.left)           if node is not None:       node.visit()         if node.right:       self.inOrder(node.right)    # 后序遍歷(遞歸)   def postOrder(self, node):     if node.left:       self.postOrder(node.left)      if node.right:       self.postOrder(node.right)     if node is not None:       node.visit()      # 遞歸遍歷   def orderTraveral(self, type):     if type == 0:       self.preOrder(self.root)     elif type == 1:        self.inOrder(self.root)     elif type == 2:       self.postOrder(self.root)    # 前序遍歷(非遞歸)   # 用到一個棧和一個隊列   # 首先是根節(jié)點入棧，再循環(huán)出棧   # 出棧元素不為空，則訪問   # 出棧元素有左孩子節(jié)點則入棧，如果有右孩子節(jié)點則入隊列   # 出棧元素為空，則訪問隊列   # 隊列也為空則結(jié)束循環(huán),否則隊列元素出隊   # 訪問出隊元素，出隊元素有左孩子節(jié)點則入棧，出隊元素有右孩子節(jié)點則入隊列   # 循環(huán)直到最后退出   def preOrderByNotRecursion(self):     s = Stack()     q = Queue()     q.enqueue(self.root)      while not s.isempty() or not q.isempty():        if not q.isempty():         item = q.dequeue()         item.visit()         if item.left:           q.enqueue(item.left)                   if item.right:           s.push(item.right)       elif not s.isempty():         item = s.pop()         item.visit()         if item.left:           q.enqueue(item.left)         if item.right:           s.push(item.right)    # 前序遍歷(非遞歸)   # 用到一個棧   # 首先是根節(jié)點入棧，再循環(huán)出棧   # 棧頂元素不為空，則訪問, 并置已訪問標志   # 如棧頂元素有左孩子節(jié)點則入棧   # 若棧頂元素已訪問，則出棧   # 出棧元素若有右孩子節(jié)點則入棧   # 循環(huán)直到棧無元素退出           def preOrderByNotRecursion2(self):     s = Stack()     s.push(self.root)      while not s.isempty():       item = s.top()             if item.visited:         s.pop()         if item.right:           s.push(item.right)       else:         item.visit()         if item.left:           s.push(item.left)     # 中序遍歷(非遞歸)   # 用到一個棧   # 先將根節(jié)點入棧，循環(huán)出棧   # 如果出棧元素有左孩子節(jié)點并且左孩子節(jié)點沒有訪問過則入棧   # 反之，則出棧并且訪問；如果出棧元素有右孩子節(jié)點則入棧   # 重復以上循環(huán)直到棧為空   def inOrderByNotRecursion(self):     s = Stack()     s.push(self.root)      while not s.isempty():       item = s.top()       while(item.left and not item.left.visited):         s.push(item.left)         item = item.left       else:         item = s.pop()         item.visit()         if item.right:           s.push(item.right)     # 后序遍歷(非遞歸)   # 用到一個棧   # 先將根節(jié)點入棧，循環(huán)出棧   # 如果出棧元素有左孩子節(jié)點并且左孩子節(jié)點沒有訪問過則入棧   # 反之，如果棧頂元素如果有右孩子節(jié)點并且右孩子節(jié)點沒有訪問過，則入棧   # 否則，出棧并訪問   # 重復以上循環(huán)直到棧為空   def postOrderByNotRecursion(self):     s = Stack()     s.push(self.root)      while not s.isempty():       item = s.top()       while(item.left and not item.left.visited):         s.push(item.left)         item = item.left       else:         if item.right and not item.right.visited:           s.push(item.right)         else:           item = s.pop()           item.visit()     # 層次遍歷(非遞歸)   # 用到一個隊列   # 先將根節(jié)點入隊列   # 從隊列取出一個元素，訪問   # 如有左孩子節(jié)點則入隊，如有右孩子節(jié)點則入隊   # 重復以上操作直到隊列入空   def layerOrder(self):     q = Queue()     q.enqueue(self.root)      while not q.isempty():       item = q.dequeue()       item.visit()       if item.left:         q.enqueue(item.left)       if item.right:         q.enqueue(item.right)  #      A #    B      C #  D    E  F    G #H if __name__ == '__main__':    nE = TreeNode('E');   nF = TreeNode('F');   nG = TreeNode('G');   nH = TreeNode('H');   nD = TreeNode('D', nH);   nB = TreeNode('B', nD, nE);   nC = TreeNode('C', nF, nG);   nA = TreeNode('A', nB, nC);   bTree = BinaryTree(nA);    # 前序遞歸遍歷   print '----------前序遍歷(遞歸)-----------'   bTree.orderTraveral(0)   print '/n----------中序遍歷(遞歸)-----------'   bTree.orderTraveral(1)   print '/n----------后序遍歷(遞歸)-----------'   bTree.orderTraveral(2)    print '/n/n----------前序遍歷(非遞歸)-----------'   print '----------方法一-----------'   bTree.freshVisit(bTree.root)   bTree.preOrderByNotRecursion()   print '/n----------方法二-----------'   bTree.freshVisit(bTree.root)     bTree.preOrderByNotRecursion2()   print '/n/n----------中序遍歷(非遞歸)-----------'   bTree.freshVisit(bTree.root)   bTree.inOrderByNotRecursion()   print '/n/n----------后序遍歷(非遞歸)-----------'   bTree.freshVisit(bTree.root)   bTree.postOrderByNotRecursion()    print '/n/n----------層次遍歷(非遞歸)-----------'   bTree.freshVisit(bTree.root)   bTree.layerOrder()