#!/use/bin/env python
#encoding=gbkimport Queueclass Stack(): def __init__(self, volume = 0): self.list = [0 for i in range(0, 1000)] if volume == 0 else [0 for i inrange(0,volume)] self.top = 0 def push(self, element): if self.list != None: self.top += 1 self.list[self.top] = element def pop(self): if self.list != None and self.top >= 0: ele = self.list[self.top] self.list[self.top] = None self.top -= 1 return ele return None def empty(self): return self.top == 0 ‘‘‘二叉树的二叉链表表示 A / \ B C / / \ D E F \ / G H先根遍历：访问根节点，遍历左子树，遍历右子树中根遍历：遍历左子树，访问根节点，遍历右子树后根遍历：遍历左子树，遍历右子树，访问根节点preOrder A B D G C E F HinOrder D G B A E C H FpostOrder G D B E H F C A深度优先遍历（先根遍历），广度优先遍历（层次遍历）depthFrist A B D G C E F HbreadthFir A B C D E F G H‘‘‘class BinaryNode(): def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def isLeaf(self): return self.left == None and self.right == None def toString(self): return self.dataclass BinaryTree(): def __init__(self, root = None): self.root = root def isEmpty(self): return self.root == None def getRoot(self): return self.root def preOrder(self, node): if node != None: cstr = node.data lstr = self.preOrder(node.left) rstr = self.preOrder(node.right) return cstr + lstr + rstr return "" def inOrder(self, node): if node != None: lstr = self.inOrder(node.left) cstr = node.data rstr = self.inOrder(node.right) return lstr + cstr + rstr return "" def postOrder(self, node): if node != None: lstr = self.postOrder(node.left) rstr = self.postOrder(node.right) cstr = node.data return lstr + rstr + cstr return "" """get tree‘s height""" def height(self, node): if node != None: lh = self.height(node.left) rh = self.height(node.right) return lh + 1 if lh > rh else rh + 1 return 0 """get tree‘s node number""" def count(self, node): if node != None: lc = self.count(node.left) rc = self.count(node.right) return lc + rc + 1 return 0 """find node, and it‘s data is X """ def search(self, value, node): tnode = None if node != None and value != None and value != "": if node.data == value: tnode = node else: tnode = self.search(value, node.left) if tnode == None: tnode = self.search(value, node.right) return tnode """get parent node""" def getParent(self, node, rnode): tnode = None if rnode != None and node != None: if rnode.left == node or rnode.right == node: tnode = rnode else: tnode = self.getParent(node, rnode.left) if tnode == None: tnode = self.getParent(node, rnode.right) return tnode """depth first search base on stack, like preOrder(non-recursive)""" def depth_first_search(self, node): list = [] if node != None: stack = Stack() stack.push(node) while not stack.empty(): tmp = stack.pop() list.append(tmp) if tmp.right != None: stack.push(tmp.right) if tmp.left != None: stack.push(tmp.left) return list """depth first search base on queue, like levelOrder(non-recursive)""" def breadth_first_search(self, node): list = [] if node != None: queue = Queue.Queue() queue.put(node) while not queue.empty(): tmp = queue.get() list.append(tmp) if tmp.left != None: queue.put(tmp.left) if tmp.right != None: queue.put(tmp.right) return listif __name__ == ‘__main__‘: print "binary tree training." LNode = BinaryNode("B", BinaryNode("D", None, BinaryNode("G",None,None)), None) RNode = BinaryNode("C", BinaryNode("E", None, None), BinaryNode("F", BinaryNode("H", None, None), None)) root = BinaryNode("A", LNode, RNode) tree = BinaryTree(root) print "pre order : %s"%(" ".join(tree.preOrder(tree.getRoot()))) print "in order : %s"%(" ".join(tree.inOrder(tree.getRoot()))) print "post order: %s"%(" ".join(tree.postOrder(tree.getRoot()))) list = tree.depth_first_search(tree.getRoot()) if list != None: print "depth first search: ", for xn in list: print xn.data + " ", print "" list = tree.breadth_first_search(tree.getRoot()) if list != None: print "breadth first search: ", for xn in list: print xn.data + " ", print ""原文：http://www.cnblogs.com/ariesblogs/p/4046622.html