介紹：樹是數(shù)據(jù)結(jié)構(gòu)中非常重要的一種，主要的用途是用來提高查找效率，對于要重復(fù)查找的情況效果更佳，如二叉排序樹、FP-樹。另外可以用來提高編碼效率，如哈弗曼樹。
#coding=utf-8
class Node(object):
? ? """節(jié)點類"""
? ? def __init__(self, elem=-1, lchild=None, rchild=None):
? ? ? ? self.elem = elem
? ? ? ? self.lchild = lchild
? ? ? ? self.rchild = rchild
class Tree(object):
? ? """樹類"""
? ? def __init__(self):
? ? ? ? self.root = Node()
? ? ? ? self.myQueue = []
? ? def add(self, elem):
? ? ? ? """為樹添加節(jié)點"""
? ? ? ? node = Node(elem)
? ? ? ? if self.root.elem == -1:? # 如果樹是空的，則對根節(jié)點賦值
? ? ? ? ? ? self.root = node
? ? ? ? ? ? self.myQueue.append(self.root)
? ? ? ? else:
? ? ? ? ? ? treeNode = self.myQueue[0]? # 此結(jié)點的子樹還沒有齊。
? ? ? ? ? ? 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é)點存在右子樹，將此結(jié)點丟棄。
? ? def front_digui(self, root):
? ? ? ? """利用遞歸實現(xiàn)樹的先序遍歷"""
? ? ? ? if root == None:
? ? ? ? ? ? return
? ? ? ? print root.elem,
? ? ? ? self.front_digui(root.lchild)
? ? ? ? self.front_digui(root.rchild)
? ? def middle_digui(self, root):
? ? ? ? """利用遞歸實現(xiàn)樹的中序遍歷"""
? ? ? ? if root == None:
? ? ? ? ? ? return
? ? ? ? self.middle_digui(root.lchild)
? ? ? ? print root.elem,
? ? ? ? self.middle_digui(root.rchild)
? ? def later_digui(self, root):
? ? ? ? """利用遞歸實現(xiàn)樹的后序遍歷"""
? ? ? ? if root == None:
? ? ? ? ? ? return
? ? ? ? self.later_digui(root.lchild)
? ? ? ? self.later_digui(root.rchild)
? ? ? ? print root.elem,
? ? def front_stack(self, root):
? ? ? ? """利用堆棧實現(xiàn)樹的先序遍歷"""
? ? ? ? if root == None:
? ? ? ? ? ? return
? ? ? ? myStack = []
? ? ? ? node = root
? ? ? ? while node or myStack:
? ? ? ? ? ? while node:? ? ? ? ? ? ? ? ? ? #從根節(jié)點開始，一直找它的左子樹
? ? ? ? ? ? ? ? print node.elem,
? ? ? ? ? ? ? ? myStack.append(node)
? ? ? ? ? ? ? ? node = node.lchild
? ? ? ? ? ? node = myStack.pop()? ? ? ? ? ? #while結(jié)束表示當(dāng)前節(jié)點node為空，即前一個節(jié)點沒有左子樹了
? ? ? ? ? ? node = node.rchild? ? ? ? ? ? ? ? ? #開始查看它的右子樹
? ? def middle_stack(self, root):
? ? ? ? """利用堆棧實現(xiàn)樹的中序遍歷"""
? ? ? ? if root == None:
? ? ? ? ? ? return
? ? ? ? myStack = []
? ? ? ? node = root
? ? ? ? while node or myStack:
? ? ? ? ? ? while node:? ? ? ? ? ? ? ? ? ? #從根節(jié)點開始，一直找它的左子樹
? ? ? ? ? ? ? ? myStack.append(node)
? ? ? ? ? ? ? ? node = node.lchild
? ? ? ? ? ? node = myStack.pop()? ? ? ? ? ? #while結(jié)束表示當(dāng)前節(jié)點node為空，即前一個節(jié)點沒有左子樹了
? ? ? ? ? ? print node.elem,
? ? ? ? ? ? node = node.rchild? ? ? ? ? ? ? ? ? #開始查看它的右子樹
? ? def later_stack(self, root):
? ? ? ? """利用堆棧實現(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):
? ? ? ? """利用隊列實現(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é)點
? ? tree = Tree()? ? ? ? ? #新建一個樹對象
? ? for elem in elems:? ? ? ? ? ? ? ? ?
? ? ? ? tree.add(elem)? ? ? ? ? #逐個添加樹的節(jié)點
? ? print '隊列實現(xiàn)層次遍歷:'
? ? tree.level_queue(tree.root)
? ? print '\n\n遞歸實現(xiàn)先序遍歷:'
? ? tree.front_digui(tree.root)
? ? print '\n遞歸實現(xiàn)中序遍歷:'
? ? tree.middle_digui(tree.root)
? ? print '\n遞歸實現(xiàn)后序遍歷:'
? ? tree.later_digui(tree.root)
? ? print '\n\n堆棧實現(xiàn)先序遍歷:'
? ? tree.front_stack(tree.root)
? ? print '\n堆棧實現(xiàn)中序遍歷:'
? ? tree.middle_stack(tree.root)
? ? print '\n堆棧實現(xiàn)后序遍歷:'
? ? tree.later_stack(tree.root)
