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;return t;}
    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,13);//測試第一組數據，已知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");

  }
}