Сокращение числа бинарного дерева

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

Я немного скептически отношусь к этому решению, особенно для случая

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

Почему его номер сокращения равен 2?

Его лес задается как

    1   && 3
   /      /
  2      4

Таким образом, его номер обрезки должен быть 1. Ответ показывает 2

Answer 4

Алгоритм проверяет, что L [index-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 будет удален при второй обрезке.