document.write('用给定的二叉树的根结点root来构造新的二叉树的方法为：首先创建新的结点dupTree，然后根据root
结点来构造dupTree结点(dupTree.data=root.data)，最后分别用root的左右子树来构造dupTree的
左右子树。根据这个思路可以实现二叉树的复制，使用递归方式实现的代码如下：
class BiTNode:
def __init__(self):
self.data=None
self.lchild=None
self.rchild=None
def createDupTree(root):
if root==None:
return None
#二叉树根结点
dupTree=BiTNode()
dupTree.data=root.data
#复制左予树
dupTree.lchild=createDupTree(root.lchild)
#复制右予树
dupTree.rchild=createDupTree(root.rchild)
return dupTree
def printTreeMidOrder(root):
if root==None:
return
#遍历root结点的左予树
if root.lchild!=None:
printTree MidOrder(root.lchild)
#遍历root结点
print root.data,
#遍历root结点的右子树
if root.rchild!=None:
printTreeMidOrder(root.rchild)
if __name__=="__main__":
root1=constructTree()
root2=createDupTree(root1)
print "原始二叉树中序遍历:",
printTreeMidOrder (root1)
print \'\\n\'
print"新的二叉树中序遍历:",
printTreeMidOrder(root2)
程序的运行结果为：
原始二叉树中序遍历：-1 3 9 6 -7
新的二叉树中序遍历：-1 3 9 6 -7
算法性能分析：
这种方法对给定的二叉树进行了一次遍历，因此，时间复杂度为O(N)，此外，这种方法需要申请N个
额外的存储空间来存储新的二叉树。
');