0

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

例如，如果我有

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

2 回答 2

1

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

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

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

你从：

    A
   / \
  B  C
 /  
D

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

  A
 / \
 B  C
/ \ 
D  E

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

"B".attachRight("E");

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

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

于 2012-11-04T19:47:18.763 回答
0

你的问题在这里：

if (!treeQueue.isEmpty()) t1 = treeQueue.remove(); 否则 t1 = null;

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

于 2012-11-04T02:41:03.897 回答