Создать полное и полное бинарное дерево рекурсивно

Question

Цель:

Я хотел бы создать полное и полное двоичное дерево , которое рекурсивно сохраняет значение String в своих листьях.

Пример1: Допустим, вы хотите сохранить две строки в своем дереве.Таким образом, вам понадобится корень и два листа.

   *  <- root node
  / \
v0   v1   <- leaves

Пример 2: Допустим, вы хотите сохранить три строки в своем дереве.Таким образом, вам понадобится корень, два внутренних узла, но четыре листа, так что дерево все еще завершено.

       *    <- root node
      / \
     +   +  <- inner node
    /     \
   /       \  
  / \     / \
v0   v1   v2 v3   <- leaves

---

Математический трюк:

Довольно просто вычислить спецификации длядвоичное дерево.

Высота: ⌈log2 ОжидаемыйNumOfStrings⌉

double height = Math.log(expectedNumOfStrings) / Math.log(2);
int roundedHeight = (int) Math.ceil(height);

Количество листьев : 2 ^Высота

int numOfLeaves =  (int) Math.pow(2, roundedHeight);

Количество внутренних узлов: 2 ^ч - 1

int numOfInnerNodes = (int) (Math.pow(2, roundedHeight)-1)

---

Реализация:

Давайтереализовать пару классов для этого двоичного дерева.Нам понадобится класс BinaryTree.

/**
* Create a complete binary tree recursively depending on the expected leaves.
*/
public class BinaryTree {

  private InnerNode root;
  private LeafNode current;


  public BinaryTree(int expectedNumOfStrings) {
    //sets root node
    this.root = new InnerNode();
    //set inner nodes
    root.createInnerNodes(expectedNumOfStrings);
    //set leaves
    root.createLeaves(expectedNumOfStrings);

   //The way things are now the tree isn't created in one go.
   //I'll have to traverse it again for the leaves.
  }

}

Все элементы дерева имеют общую ссылку на родителя (для корня это null).Давайте создадим класс TreeNode:

public class TreeNode {

private TreeNode parent;
}

Теперь давайте создадим InnerNode и LeafNode, которые просто расширяют TreeNode.

public class InnerNode extends TreeNode {

  private BinaryTree left;
  private BinaryTree right;

  //used to set the root node
  public InnerNode() {
    super.parent = null;
    this.left=null;
    this.right=null;
  }

  public InnerNode(InnerNode parent) {
    super.parent= parent;
  }

  public TreeNode createInnerNodes(int expectedValues) {
  //recursive magic happens here. But how?
  }
}

и

public class LeafNode extends TreeNode {

  private String data;

  public LeafNode(InnerNode parent) {
    super.parent= parent;
  }

  public LeafNode createLeaves(int numOfLeaves) {
    //recursive magic happens here again. But how?
  }
}

Вопросы и проблемы

1. Я хочу, чтобы классы были разделены, как они есть, и я хочу настроить дерево за один раз.Как настроить InnerNodes и Leaves в одно и то же время?
2. InnerNode left и InnerNode right являются частными, поэтому я могу получить к ним доступ только из InnerNode.Но как мне тогда бороться с листьями?Могу ли я просто передать корневой узел для InnerNode / Leaves в методе?
3. Что лучше всего использовать для рекурсии?Высота или количество соответствующих узлов?Или что-то еще целиком?
4. Как установить указатель влево и вправо?Я имею в виду объекты, на которые они указывают, еще не существует, не так ли?
5. Я на правильном пути?/ о \