二叉树的 addChild 方法

Question

为了一个项目，我自己写了一个二叉树class。我需要递归地构建左子树和右子树，所以我添加了一个 makeBinaryTreeNode 方法，它接受根、左子树和右子树。在其中我知道我需要调用某种方法，在创建两个 leftChild 和 rightChild 树后调用 addChild 保存子数据，但我不知道如何为二叉树实现编写 addChild 方法。我看过其他实现，其中子节点存储在节点列表中（Java tree data-structure? <-- 该线程中的最佳答案使用列表存储子节点），但是是否有更好的方法来编写java 中二叉树的 addChild 方法？任何帮助表示赞赏！

Answer 1

//each tree is also a node
public class BinaryTree<T> extends Node<T>{
  private BinaryTree<T> parentNode;
  private BinaryTree<T> leftNode;
  private BinaryTree<T> rightNode;

  public BinaryTree() {

  }
}

public class Node<T> {

  T value;
}

Answer 2

这取决于二叉树的种类，大多数二叉树都有某种平衡来防止树的查找时间不理想。如果您不必进行平衡，那么有多种方法可以将 child 添加到节点。

一个例子是：有两种节点，第一种是没有 childs 的叶节点，第二种是有两个 childs 的内部节点。现在写一个 addChild 可能如下所示：

在叶节点上：

public Node addChild(Node n){
   return new InnerNode(this,n);  //without balancing new InnerNode(n,this); is fine to
}

在内部节点上：

public Node addChild(Node n){ 
   left = left.addChild(n); //without balancing right = right.addChild(n); is fine to
   return this;
}

但如果没有平衡，这是毫无意义的，并且总是退化为某种链表。

一个简单的平衡是计算分支中的叶节点。对于 LeafNode，这是 1，对于 InnerNode，这是左+右叶节点的总和。那么你可以总是将新节点添加到叶子较少的一侧。

但是它们是更好的平衡技术，例如 Red-Black 树。

二叉树的 addChild 方法

addChild method for Binary Tree

java

algorithm

binary-tree

structure