16968575的专栏

biTree.py

import Queue:):self.left = Noneself.right = Noneself.data = data::”’__init__(self,root)self.root = root(根节点)”’self.root = root:”’preTraver(self,root,visit)先序遍历,visit是回调方法”’if root != None:visit(root)self.preTraver(root.left,visit)self.preTraver(root.right,visit):”’inTraver(self,root,visit)中序遍历，visit是用户定义的回调函数”’if root != None:self.inTraver(root.left,visit)visit(root)self.inTraver(root.right,visit):”’postTraver(self,root,visit)后序遍历，visit是用户定义的回调函数”’if root != None:self.postTraver(root.left,visit)self.postTraver(root.right,visit)visit(root):”’levelTraver(self,parent,visit)层次遍历，visit是用户定义的回调函数”’q = Queue.Queue(20)if parent != None:q.put_nowait(parent)while not q.empty():node = q.get_nowait()visit(node)if node.left != None:q.put_nowait(node.left)if node.right != None:q.put_nowait(node.right)

biTreeSort.py

biTree:”’根据参数L创建二叉树，，key是一个用户自定义函数,key(object)返回object的键值，排序时比较键值大小。key函数同list.sort()中key一样。返回root节点”’root = biTree.biTreeNode(L[0])for item in L[1:]:p = rootq = rootis_left = Nonewhile p != None:if key(item) <= key(p.data):q = pp = p.leftis_left = Trueelse:q = pp = p.rightis_left = Falseif is_left:q.left = biTree.biTreeNode(item)else:q.right = biTree.biTreeNode(item)return root:”’biTreeSort(L)对L排序，不返回结果。函数执行完后，L已经排好序”’root = createBitree(L,key)L[:] = []bt = biTree.biTree(root)bt.inTraver(root,lambda node:L.append(node.data))if __name__ == ‘__main__’:L = [‘fgasef’,’gwagew’,’jrde’,’nhaf’,’erhjaz’,’erjf’]biTreeSort(L,key=lambda item:item[2])print L

心有多大，舞台就有多大。