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

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

forchenyun · 2018-4-30 01:56:51

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();

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

inee123456 · 2018-4-30 01:56:50

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 intTree=new BST();
  BST charTree=new BST();
  BST strTree=new BST();

  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

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

2 个回复

浏览过的版块