3

例如，如果我有

  A
 / \
 B  C
/  
D

我希望下一个补充是：

  A
 / \
 B  C
/ \ 
D  E

但是我在检测下一个要输入的项目的位置时遇到了很多麻烦。我有以下代码：

    public static BinaryTree<String> addToTree(BinaryTree<String> tree, String name) {
        if (tree.getLeft() == null) {
            BinaryTree<String> newTree = new BinaryTree<String>();
            newTree.makeRoot(name);
            tree.attachLeft(newTree);
        }
        else if (tree.getRight() == null) {
            BinaryTree<String> newTree = new BinaryTree<String>();
            newTree.makeRoot(name);
            tree.attachRight(newTree);
        }
        // Both are non-null
        else {
            if (tree.getLeft().getLeft() == null || tree.getLeft().getRight() == null) {
                tree.attachLeft(addToTree(tree.getLeft(), name));
            }
            else if (tree.getRight().getLeft() == null || tree.getRight().getRight() == null) {
                tree.attachRight(addToTree(tree.getRight(), name));
            }
        }

        return tree;
    }

但它只适用于最多三层树。如果我尝试添加第四个，它不再添加任何内容。

我该如何实现它，以便它找出下一个项目为空的位置，然后将其添加到那里？

我也想过有一个checkNullity()方法，我会拿一棵树，检查它的孩子是否为空，但我也很难弄清楚如何得到孩子的孩子。我想找到它为空的位置，然后将其添加到那里。

谁能提供一些意见？

4

5 回答 5

2

我认为您可以修改广度优先遍历来完成此操作。当您从队列中弹出项目时，检查是否有任何子项为空。第一个空子槽是您要添加的位置。

addNode(root, newNode) 
  q = empty queue
  q.enqueue(root)
  while not q.empty do
    node := q.dequeue()
    if node.left == null
      //create new node as nodes left child
      return
    q.enqueue(node.left)
    if node.right == null
      //create new node as nodes right child
      return
    q.enqueue(node.right)
于 2012-11-03T23:06:30.747 回答
0

您可以枚举所有节点，同时将它们添加到树中。如果要将n第 -th 节点添加到树中，它将是n/2第 -th 节点的子节点：left ifn%2 == 0和 right if n%2 == 1。

于 2012-11-03T23:10:08.187 回答
0

因为，您希望按从左到右的顺序插入元素，并从同一级别开始。我建议您查看呼吸优先搜索。我提供了一个基本的实现。

public void insert(child, root){

    if (root == null){
        root = child
    }

    Node iter = root
    Myqueue q = new Myqueue(); //Implementation of the Java Queue Interface

    while (iter!=null){

        //Check: If the left node exists, enque in the que
        if(iter.is_left()){
            q.insert(iter.left)
        }
        else{
            iter.left = child
            iter = null
        }

        //Similary for the right
        if(iter.is_right()){
            q.insert(iter.right)
        }
        else{
            iter.right = child
            iter = null
        }
        if (iter != null){
        iter = q.poll() //Retreiving the head of the queue
        }
    }
}
于 2012-11-03T23:30:00.283 回答
0

这肯定会创建您要求的树，尽管我仍然不确定它是否是您想要的：

public class BinaryTree<T> {
  T root = null;
  BinaryTree<T> left = null;
  BinaryTree<T> right = null;

  public BinaryTree<T> getLeft() {
    return left;
  }

  public BinaryTree<T> getRight() {
    return right;
  }

  public void makeRoot(T root) {
    this.root = root;
  }

  public void attachLeft(BinaryTree<T> tree) {
    left = tree;
  }

  public void attachRight(BinaryTree<T> tree) {
    right = tree;
  }

  public static BinaryTree<String> addToTree(BinaryTree<String> tree, String name) {
    if (tree.getLeft() == null) {
      BinaryTree<String> newTree = new BinaryTree<String>();
      newTree.makeRoot(name);
      tree.attachLeft(newTree);
    } else if (tree.getRight() == null) {
      BinaryTree<String> newTree = new BinaryTree<String>();
      newTree.makeRoot(name);
      tree.attachRight(newTree);
    } else {
      addToTree(tree.getLeft(), name);
    }
    return tree;
  }

  public static void main(String[] args) {

    try {
      BinaryTree<String> tree = new BinaryTree<String>();
      String add = "ABCDEFG";
      tree.makeRoot(add.substring(0, 1));
      for (int i = 1; i < add.length(); i++) {
        addToTree(tree, add.substring(i, i + 1));
      }
      System.out.println("Done");
    } catch (Throwable e) {
      e.printStackTrace();
    }
  }
}

添加

我显然误解了这个问题。也许一个例子会有所帮助。

如果我从以下字符串中一次添加一个字符（作为字符串），您会期望什么？

“ABCDEFG”

  A
 / \
 B   C
/ \  | \
D  E F  G?

或者是其他东西。

然后你会期待什么

“ADEFGBC”

  A
 / \
 D   E
/ \  | \
F  G B  C

或者

  A
 / \
 B   C
/ \  | \
D  E F  G

或者是其他东西？

两者都是可能的，但在任何一种情况下我都看不到任何价值。

于 2012-11-03T23:34:05.243 回答
0

为了将元素添加到二叉树的适当位置，您必须从每个节点的根开始回答以下问题：我应该下降到左边还是右边的子树？这就是您的问题归结为 - 如何在每个节点上做出此决定。

你开始就OK了。如果节点没有左子树，那么新添加的叶子应该是它的左孩子。如果节点有左子树但没有右子树，那么新添加的叶子应该是它的右孩子。

但是如何判断节点是否有两个子树呢？为此，您需要在可用于决定的节点上保留某种信息。一种可能性是在每个节点上保持其子树的总大小。然后，如果两个子树的大小相同，则意味着两者都是完美平衡的，因此您将其添加到左侧。否则，如果左子树的大小为2^n-1，则意味着它是平衡的（而右子树不是），因此您添加到右侧。如果没有，请添加到左侧。

但是，您可以做的比这简单得多。由于您的树始终保持这种结构，因此您可以将树表示为ArrayList. 根节点位于索引0处，对于索引n处的节点，其子节点位于索引 _2*n+1_ 和 _2*n+2_ 处。这就是二进制堆的实现方式。这样，您将获得O(1)添加新节点的时间复杂度 - 只需将其附加到列表的末尾即可。（但是，如果您需要一些经典的树操作，例如旋转，则此实现将不起作用。）

于 2012-11-04T15:14:44.590 回答