document.write('如果两棵二叉树root1、root2相等，那么root1与root2结点的值相同，同时它们的左右孩子也有着相同的结
构，并且对应位置上结点的值相等，即root1.data=root2.data，并且root1的左子树与root2的左子树相
等，root1的右子树与root2的右子树相等。根据这个条件，可以非常容易地写出判断两棵二叉树是否相等的
递归算法。实现代码如下：
class BiTNode:
def __init__(self):
self.data=None
self.lchild=None
self.rcbild=None
"""
方法功能: 判断两棵二叉树是否相等
参数: root1与root2分别为两棵二叉树的根结点
返回值: true:如果两棵树相等则返回true, 否则返回false
"""
def isEqual(root1,root2):
if root1==None and root2==None:
return True
if root1==None and root2!=None:
return False
if root1!=None and root2==None:
return False
if root1.data==root2.data:
return isEqual(root1.lchild,root2.lchild) and isEqual(root1.rchild,root2.rchild)
else:
return False
def constructTree():
root=BiTNode()
node1=BiTNode()
node2=BiTNode()
node3=BiTNode()
node4=BiTNode()
root.data=6
node1.data=3
node2.data=-7
node3.data=-1
node4.data=9
root.lchild=node1
root.rchild=node2
nodel.lchild=node3
nodel.rchild=node4
node2.lchild=node2.rchild=node3.lchild=node3.rchild=\\
node4.lchild=node4.rchild=None
return root
if __name__=="__main__":
root1=constructTree()
root2=constructTree()
equal=isEqual(root1,root2)
if equal:
print "这两棵树相等"
else:
print "这两棵树不相等"
程序的运行结果为：
这两棵树相等
算法性能分析：
这种方法对两棵树只进行了一次遍历，因此，时间复杂度为O(N)。此外，这种方法没有申请额外的存储空间。
');