二叉树的修剪数

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