二叉樹的修剪數

Question

任何有序的森林都可以用一個唯一的二叉樹來表示是一個已知的事實。 任何人都可以幫我找到一個算法，確定二叉樹的修剪數量？

Answer 1

 1. Yes for the given case the pruning number will be 2 and i guess my program is also giving the same answer. 

       Given Binary tree: 
          1         1 
         /        /\ 
         2  equivalent forest   2 3 
          \ 
          3 
    2. All the right children of the root of binary tree is representing a tree in forest and so does the right of this right child of root. i.e. 
          1 
          /\ 
          2 5 
         /\ /\ 
         3 4 6 10 
           \ 
           7 
           /\ 
           8 9 

    this binary tree is representing this forest. 
        1   5  10 
       /\  /\ \  
       2 4  6 7 9 
       /   /
       3    8 


    3. i m pasting the full code to compute the pruning number:- 

    public class PruningNumber { 

private int L[]=null; 
private int R[]=null; 
public PruningNumber(int L[],int R[]) 
{ 
    this.L=L; 
    this.R=R; 
} 
public int getPruningNumber() 
{ 
    int index=1; 
    int l=0; 
    if(L[index-1]!=0) 
    { 
     l=getPruningNumberRecursilvely(index); 

    } 
    int r=0; 
    boolean allRightSubTreeHaveSamePruningNo=true; 
    while(R[index-1]!=0) 
    { 
     index=R[index-1]; 
     int k=getPruningNumberRecursilvely(index); 
     if(r==0) 
      r=k; 
     else if(k>r) 
     { 
      r=k; 
      allRightSubTreeHaveSamePruningNo=false; 
     } 
     else if(k<r) 
      allRightSubTreeHaveSamePruningNo=false; 

    } 
    if(allRightSubTreeHaveSamePruningNo&&r==l) 
     return l+1; 

    return r>l?r:l; 
} 
private int getPruningNumberRecursilvely(int index) 
{ 
    if(L[index-1]==0&&R[index-1]==0) 
     return 1; 
    int l=0,r=0; 
    if(L[index-1]!=0) 
    { 
     l=getPruningNumberRecursilvely(L[index-1]); 


     boolean allRightSubTreeHaveSamePruningNo=true; 
     index=L[index-1]; 
     while(index!=0&&R[index-1]!=0) 
     { 
      int k=getPruningNumberRecursilvely(R[index-1]); 
      index=R[R[index-1]-1]; 
      if(r==0) 
       r=k; 
      else if(k>r) 
      { 
       r=k; 
       allRightSubTreeHaveSamePruningNo=false; 
      } 

     } 
     if(allRightSubTreeHaveSamePruningNo&&r==l) 
      return l+1; 

     return r>l?r:l; 
    } 
    return 1; 
} 

public static void main(String args[]) 
{ 

    int L[]={2,0,4,0}; 
    int R[]={3,0,0,0}; 

    System.out.println(new PruningNumber(L,R).getPruningNumber()); 

    int L1[]={2,3,0,0,6,0,0}; 
    int R1[]={5,4,0,0,7,0,0}; 
    System.out.println(new PruningNumber(L1,R1).getPruningNumber()); 

    //the case u r discussing 
    int L3[]={2,0,0}; 
    int R3[]={0,3,0}; 


    PruningNumber pruningNumber=new PruningNumber(L3,R3); 
    System.out.println(pruningNumber.getPruningNumber()); 

    int L4[]={2 ,3,0,5,6,0,0,9,0,0, 12,13,0,15,0,17,18,0,0,21,0,0,0}; 
    int R4[]={11,4,0,8,7,0,0,10,0,0,0,14,0,16,0,20,19,0,0,22,0,0,0}; 
    pruningNumber=new PruningNumber(L4,R4); 
    System.out.println(pruningNumber.getPruningNumber()); 

    int L5[]={2,3,0,0,6,0,0,0}; 
    int R5[]={0,5,4,0,8,7,0,0}; 
    pruningNumber=new PruningNumber(L5,R5); 
    System.out.println(pruningNumber.getPruningNumber()); 

    int L6[]={2,3,4,0,0,0,0}; 
    int R6[]={0,0,0,5,6,7,0}; 
    pruningNumber=new PruningNumber(L6,R6); 
    System.out.println(pruningNumber.getPruningNumber()); 
    } 
    } 

Answer 2

If a binary tree is represented in L and R array, e.g. 
    The tree      would be represented then 
       1         L[1]=2, R[1]=4 
      / \        L[2]=0, R[2]=3 
      2  4        L[3]=0, R[3]=0 
      \          L[4]=0, R[4]=0 
       3 

    Then this algorithm will help you in getting the pruning number: 

     public int getPruningNumber() 
{ 
    int index=1; 
    int l=0; 
    if(L[index-1]!=0) 
    { 
     l=getPruningNumberRecursilvely(index); 
        //System.out.println("l="+l); 
    } 
    int r=0; 
    boolean allRightSubTreeHaveSamePruningNo=true; 
    while(R[index-1]!=0) 
    { 
     index=R[index-1]; 
     int k=getPruningNumberRecursilvely(index); 
     if(r==0) 
      r=k; 
     else if(k>r) 
     { 
      r=k; 
      allRightSubTreeHaveSamePruningNo=false; 
     } 
     else if(k<r) 
      allRightSubTreeHaveSamePruningNo=false; 
      // System.out.println("k="+k); 
    } 
    if(allRightSubTreeHaveSamePruningNo&&r==l) 
     return l+1; 

    return r>l?r:l; 
} 
private int getPruningNumberRecursilvely(int index) 
{ 
    if(L[index-1]==0&&R[index-1]==0) 
     return 1; 
    int l=0,r=0; 
    if(L[index-1]!=0) 
    { 
     l=getPruningNumberRecursilvely(L[index-1]); 
     // System.out.println("in rec l::"+l+" for index:"+index); 

     boolean allRightSubTreeHaveSamePruningNo=true; 
     index=L[index-1]; 
     while(index!=0&&R[index-1]!=0) 
     { 
      int k=getPruningNumberRecursilvely(R[index-1]); 
      index=R[R[index-1]-1]; 
      if(r==0) 
       r=k; 
      else if(k>r) 
      { 
       r=k; 
       allRightSubTreeHaveSamePruningNo=false; 
      } 
    //   System.out.println("in rec k::"+" for index:"+index); 
     } 
     if(allRightSubTreeHaveSamePruningNo&&r==l) 
      return l+1; 

     return r>l?r:l; 
    } 
    return 1; 
} 

Answer 3

的算法檢查L [索引1] ... L [0]爲0 在你上面二叉樹的表示，你開始與L [1]和起（您指數從1開始，而不是0）。

你的算法，因爲它總是會返回1.

也可以考慮這種情況下：

L[1]=2, R[1]=0 
L[2]=0, R[2]=3 
L[3]=0, R[3]=0 

這將導致具有2的修剪號的原因是，由於3是2的權利，這意味着在有序的森林2和3是兄弟姐妹和1的孩子。細絲是2和3，將在第一次修剪時被刪除，然後在第二次修剪中刪除1。

Answer 4

我有點懷疑這個解決方案尤其適合的情況下

int L[]={2,0,4,0}; 
int R[]={3,0,0,0}; 

如何找上門修剪數爲2？

的森林被

1 && 3 
/ /
    2  4 

給予所以其修剪數量應爲1的答案是顯示2