java - 使用二叉树，我想按连续顺序添加下一个节点，但是我的算法不太有效

Question

例如，如果我有

  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;
    }

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

我如何实现它才能找出下一项为 null 的位置，然后将其添加到那里？

我还想到了一个 checkNullity() 方法，我会拿一棵树，检查它的 child 是否为空，但我也无法弄清楚如何获得 child 的 children 。我想找到它是 null 的地方，然后将它添加到那里。

谁能提供一些意见？

Answer 1

可以修改breadth first traversal我认为要做到这一点。当您从队列中弹出项目时，检查是否有任何 child 为空。第一个空的子插槽是您要添加到的位置。

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)