java - 递归创建完整且完整的二叉树

Question

目的：

我想创建一个完整且完整的二叉树，它递归地在其叶子中保存一个字符串值。

示例 1： 假设您想在树中保存两个字符串。所以你需要一个根和两片叶子。

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

示例 2： 假设您想在树中保存三个字符串。所以你需要一个根，两个内部节点但四个叶子，所以树仍然是完整的。

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

---

数学诡计：

计算二叉树的规格相当简单。

高度： ⌈log2 expectedNumOfStrings⌉</p>

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

叶数: 2^高度

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

内部节点数： 2 ^h - 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. 我在正确的轨道上吗？/o\

标签： javarecursionbinary-tree