Генерирование полного двоичного дерева рекурсивно через метод Java

Question

Метод должен принимать два параметра по одному для глубины и один для целочисленного значения корня дерева. Например: для любого заданного N возвращает корневую ссылку полного дерева двоичного поиска с глубиной N, так что узлы хранят целые числа 1, 2, ..., 2 N + 1 - 1. Я изо всех сил пытаюсь это понять. Вот что у меня есть:

public static BinaryNode BSTFactory(int top,int depth) { 
     BinaryNode root=new BinaryNode(null,null,top); 
     BinaryNode leftChild,rightChild; 
     if(depth==0){ 
      return root; 
     } 
     if(depth==1){ 
      //create 2 children left and right 
      leftChild=new BinaryNode(null,null,top-1); 
      rightChild=new BinaryNode(null,null,top+1); 
      root=new BinaryNode(rightChild,leftChild,top); 
      return root; 
     } 
     if(depth>1){ 

      leftChild=BSTFactory(top-1,depth-1); 
      rightChild=BSTFactory(top+1,depth-1); 
      root=new BinaryNode(rightChild,leftChild,top); 
      return root; 
     } 
     return root; 
    } 

Answer 1

Прежде всего, два параметра вашего метода зависят друг от друга. Например, BSTFactory (1,3) не может быть полным двоичным деревом с минимальным узлом из 1, поскольку, если корень уже содержит минимальный узел, левое поддерево должно быть пустым (если вы не разрешаете отрицательные значения в вашем дерево, что непонятно из вашего вопроса, поскольку вам кажется, что дерево должно хранить целые числа, начиная с 1).

Поэтому я бы предложил метод обертки, который бы принял только глубину и вычислил соответствующий корневой узел. Посмотрим, как эти два параметра будут связаны позже.

Теперь давайте посмотрим на некоторые небольшие полных бинарных деревьев, чтобы выяснить рекурсии:

Глубина 0

1 

Глубина 1

2 
1  3 

Глубина 2

 4 
    2 6 
1 3 5 7 

глубина 3

  8 
    4  12 
    2  6 10 14 
1 3 5 7 9 11 13 15 

Что мы можем извлечь из этих примеров?

Если мы создаем полный двоичный поиск дерево глубины п:

1. Корень будет 2^n
2. Левое поддерево будет корнем root - 2^(n-1)
3. Право суб-дерево коренится в root + 2^(n-1)

Таким образом, recusion должно быть:

public static BinaryNode BSTFactory(int root, int depth) 
{ 
    BinaryNode leftChild,rightChild; 
    if (depth==0){ 
     return new BinaryNode(null,null,root); 
    } else { 
     leftChild=BSTFactory(root-Math.pow(2,depth-1),depth-1); 
     rightChild=BSTFactory(root+Math.pow(2,depth-1),depth-1); 
     return new BinaryNode(rightChild,leftChild,root); 
    } 
} 

Обратите внимание, что для этого необходимо работать (т. что ваш минимальный узел будет равен 1), вы должны вызвать метод с корнем и глубиной, так что root = 2^depth. Для того, чтобы гарантировать, что позволяет определить метод обертку:

public static BinaryNode BSTFactory(int depth) 
{ 
    return BSTFactory (Math.pow(2^depth),depth); 
} 

При вызове метода два параметра с произвольным корнем и глубины, вы можете получить бинарные деревья, такие как:

BSTFactory (6,1)

 6 
    5 7 

BSTFactory (1,2)

 1 
    -1 3 
    -2 0 2 4 

Есть еще полные бинарные деревья, но их минимальное значение не равно 1.