Question

数据结构问题"编写一个判断两颗二叉树是否相等的程序"

编写一个程序判断两棵二叉树是否是相似的，关于相似性的定义如下：
这两棵二叉树或者都是空树，或者非空且有相似的左子树和右子树

Answer 1

2、程序源代码：
public class SimiliarTreeTest {
public static boolean test(BinNode t1,BinNode t2){
if(t1==null&&t2==null)
return true;
else if(t1!=null&&t2!=null)
{
return test(t1.left,t2.left)&&test(t1.right,t2.right);
}
return false;
}
}

3、测试类：
public class SimiliarilityTest {
public static void main(String[] args){
BST<Integer> intTree=new BST<Integer>();
BST<Character> charTree=new BST<Character>();
BST<String> strTree=new BST<String>();

Integer[] numbers={14,15,2,26,36,11,25,58,47,44,16,1};
Character[] chars={14,15,2,26,36,11,25,58,47,44,16,1};
String[] strs={"this","is ","so ","dispointed","and ","i ","am","trying"};

for(int i=0;i<strs.length;i++){
strTree.insert(new BinNode<String>(strs[i]));
}
for(int i=0;i<numbers.length;i++)
intTree.insert(new BinNode<Integer>(numbers[i]));
for(int i=0;i<chars.length;i++)
charTree.insert(new BinNode<Character>(chars[i]));

boolean b=SimiliarTreeTest.test(intTree.root, strTree.root);
System.out.println("intTree and strTree are similiar with each other?"+b);
System.out.println("-----------------");
b=SimiliarTreeTest.test(intTree.root, charTree.root);
System.out.println("intTree and charTree are similiar with each other?"+b);

}
}
（注明：其中BST为二叉查找树）

Answer 2

public boolean isSimilar(BinNode rt1,BinNode rt2){
if(rt1==null&&rt2==null)return true;
else if(rt1==null)return false;
else if(rt2==null)return false;
if(isSimilar(rt1.left(),rt2.left())&&isSimilar(rt1.right(),rt2.right()))return true;
return false;
}
其中,BinNode是节点类的接口
//这是二叉树节点的抽象数据类型(ADT)
public interface BinNode {

public Object element();

public Object setElement(Object v);

public BinNode left();

public BinNode setLeft(BinNode p);

public BinNode right();

public BinNode setRight(BinNode p);

public boolean isLeaf();

}
递归的使用可以很方便的实现程序,但也增加了程序的时间消耗.谢谢