find.java~36~

来自「源程序（包括最初的版本」· JAVA~36~ 代码 · 共 42 行

package datastructures;

/**start 2005.3.28  20:01
 *  习题书P42 6.33
 * finish 2005.3.28  21:07
 */
class Find {
  //判别节点u是否为v的子孙
  //L[i]，R[i]指示节点i的左右小孩，0表示空
  protected int L[]=new int[20];
  protected int R[]=new int[20];
  int t; //判断u是否为v的子孙

  public Find() {
    super();
  }

  public int find(int v,int u) {
    if(L[v]==u||R[v]==u) {t=1;return t;}   //当前节点的左小孩或右小孩等于u
    if(L[v]!=u&&R[v]!=u) {t=0;}
    if (L[v] != 0) find(L[v], u);
    if (R[v] != 0) find(R[v], u);

    return t;

  }
  public static void main(String args[]){
    int a[]={-1,2,10,5,6,8,9,0,0,0,11,13,0,0};
    int b[]={-1,3,4,0,7,0,0,0,0,0,12,0,0,0};
    Find f=new Find();
    f.L=a;  f.R=b;
    int ture1=f.find(2,8);//测试第一组数据，已知2是13的祖先
    if(ture1==1)   System.out.println("13 is 2's descendant");
    else   System.out.println("13 isn't 2's descendant");

    int ture2=f.find(2,8);//测试第二组数据，已知2不是7的祖先
    if(ture2==1)  System.out.println("3 is 2's descendant");
    else   System.out.println("3 isn't 2's descendant");

  }
}