学步园

这是根据本人另一个C语言版本采用python实现的，添加了根据中序和后序重建二叉树功能，更多详细解释可参考：http://blog.csdn.net/hinyunsin/archive/2011/04/11/6315502.aspx

下面就是python代码：

#-*- coding: utf-8 -*-<br /> #!/usr/bin/python<br /> #Filename: BTreeNode.py<br /> '''<br /> Created on 2011-4-11<br /> @author: boyce<br /> @contact: boyce.ywr@gmail.com<br /> @version: 1.0<br /> '''<br /> class BTree:<br /> '''<br /> Represent a no in a binary tree.<br /> '''<br /> def __init__(self, c='/0', l=None, r=None):<br /> '''<br /> Initializes the node's data<br /> '''<br /> self.e = c<br /> self.left = l<br /> self.right = r<br /> def preorderTraverse(bt):<br /> '''<br /> 返回前序遍历结果<br /> '''<br /> if bt:<br /> return '%s%s%s' % (bt.e, preorderTraverse(bt.left), preorderTraverse(bt.right))<br /> return ''<br /> def inorderTraverse(bt):<br /> '''<br /> 返回中序遍历结果<br /> '''<br /> if bt:<br /> return '%s%s%s' % (inorderTraverse(bt.left), bt.e, inorderTraverse(bt.right))<br /> return '';<br /> def postorderTraverse(bt):<br /> '''<br /> 返回后序遍历结果<br /> '''<br /> if bt:<br /> return '%s%s%s' % (postorderTraverse(bt.left), postorderTraverse(bt.right), bt.e)<br /> return ''<br /> def printBTree(bt, depth):<br /> '''<br /> 递归打印这棵二叉树，*号表示该节点为NULL<br /> '''<br /> '''<br /> if not bt:<br /> ch = '*'<br /> else:<br /> ch = bt.e<br /> '''<br /> #ch=(lambda x: (x and x.e) or '*')(bt)<br /> ch = bt.e if bt else '*'<br /> if(depth > 0):<br /> print '%s%s%s' % ((depth - 1) * ' ', '--', ch)<br /> else:<br /> print ch<br /> if not bt:<br /> return<br /> printBTree(bt.left, depth + 1)<br /> printBTree(bt.right, depth + 1)<br /> def buildBTreeFromPreIn(preo, ino):<br /> '''<br /> 根据前序和中序遍历结果重构这棵二叉树<br /> '''<br /> if(preo == '' or ino == ''):<br /> return None<br /> pos = ino.find(preo[0])<br /> if(pos < 0):<br /> return None<br /> return BTree(preo[0], buildBTreeFromPreIn(preo[1:pos + 1], ino[0:pos]), buildBTreeFromPreIn(preo[pos + 1:], ino[pos + 1:]))<br /> #return nd<br /> def buildBTreeFromInPost(ino, po):<br /> '''<br /> 根据中序和后序遍历结果重构这棵二叉树<br /> '''<br /> if(ino == '' or po == ''):<br /> return None<br /> pos = ino.find(po[-1])<br /> if(pos < 0):<br /> return None<br /> return BTree(po[-1], buildBTreeFromInPost(ino[0:pos], po[0:pos]), buildBTreeFromInPost(ino[pos + 1:], po[pos:-1]))</p> <p>if __name__ == '__main__':<br /> preo = 'ABDGCEFH'<br /> ino = 'DGBAECHF'<br /> po = 'GDBEHFCA'<br /> bt = buildBTreeFromPreIn(preo, ino)<br /> print 'Build from preorder & inorder'<br /> print 'Preorder: %s' % (preorderTraverse(bt))<br /> print 'Inorder: %s' % (inorderTraverse(bt))<br /> print 'Postorder: %s' % (postorderTraverse(bt))<br /> print 'The BTree is (* means no such a node):'<br /> printBTree(bt, 0)<br /> bt = buildBTreeFromInPost(ino, po)<br /> print 'Build from inorder & postorder'<br /> print 'Preorder: %s' % (preorderTraverse(bt))<br /> print 'Inorder: %s' % (inorderTraverse(bt))<br /> print 'Postorder: %s' % (postorderTraverse(bt))<br /> print 'The BTree is (* means no such a node):'<br /> printBTree(bt, 0)<br />

python确实很有意思，写出来的东西比c要简洁很多，当然，我的其实还远远不够简洁，没办法，还是新手嘛，呵呵~

这里多了根据中序和后序重建二叉树功能，原理和根据前序和中序重建一样。

下面是执行结果：