使用广度优先遍历算法，我将项目按连续顺序添加到二叉树中，但它们没有正确添加

Question

我使用以下方法（使用广度优先遍历算法）将项目按连续顺序添加到二叉树中。

例如，如果我有

  A
 / \
 B  C
/  
D 

我希望下一个补充是：

  A
 / \
 B  C
/ \ 
D  E

我的问题在于，我不确定如何正确返回值。我知道当我们遇到第一个空节点时，我们会在其中插入值，但是我们要将它插入到什么中呢？如果我们把它插入到我们从队列中得到的二叉树中，那是根（或我们试图添加到的树）的一个子树，所以返回的不是完整的树。

以下是我的代码：

public static <T> BinaryTree<T> addToTree(BinaryTree<T> t1, BinaryTree<T> t2) {
    Queue<BinaryTree<T>> treeQueue = new LinkedList<BinaryTree<T>>();

    while (t1 != null) {
        if (t1.getLeft() == null) {
            t1.attachLeft(t2);
            break;
        }
        treeQueue.add(t1.getLeft());

        if (t1.getRight() == null) {
            t1.attachRight(t2);
            break;
        }
        treeQueue.add(t1.getRight());

        if (!treeQueue.isEmpty()) t1 = treeQueue.remove();
        else t1 = null;
    }
    return t1;
}

Answer 1

你的问题是：

如果（！treeQueue.isEmpty（））t1=treeQueue。移除（）；else t1=null；

如果节点没有子节点，可以将其引用设置为null以中断while，但这也是函数返回的值。您只需使用一个临时变量来存储对要返回的节点的引用。

Answer 2

好吧，我想我现在明白你的要求了。

您的广度优先实现是正确的。

二叉树是一种“自包含”结构。您从名为A的根开始，有两个对另外两个二叉树的引用，“左”和“右”

你从以下方面开始：

    A
   / \
  B  C
 /  
D 

并添加一棵二叉树E作为B的右子树：

  A
 / \
 B  C
/ \ 
D  E

实际上，您的实现返回一个子树“B”，即新子树的附加位置。我不确定您使用的是什么二进制树实现，但我希望：

"B".attachRight("E");

修改原始树，所以附加节点的“新”树仍然是以“A”开头的树——即您不必返回任何东西！我不知道您的实现是否跟踪“父”，如果是，您可以从“B”开始遍历父级层次结构，直到找到父级为空的节点——根（又是“a”）

调用addToTree（BinaryTree t1， BinaryTree t2）后想要的答案是“t1”，即作为第一个参数传递的“A”根树。