如何从一般树创建二叉树？

Question

我必须为 java 中的 BinaryTree 类解决以下构造函数：

BinaryTree(GeneralTree<T> aTree)

此方法应创建一个二叉树（BT）从通用树（GT）如下：

gt 中的每个顶点都将表示为bt 中的叶子。

• 如果 gt 是叶子，那么 bt 将是与 gt 具有相同值的叶子
• 如果 gt 不是叶子，那么 bt 将被构造为一个空根，一个左子树（lt）和一个右子树（lr）。Lt 是从 gt 的最老子树（最左边的子树）创建的严格二叉树，lr 是从 gt 创建的严格二叉树，没有最左边的子树。

第一部分是微不足道的，但第二部分给我带来了一些麻烦。我已经走了这么远：

public BinaryTree(GeneralTree<T> aTree){
        if (aTree.isLeaf()){
            root= new BinaryNode<T>(aTree.getRootData());
        }else{
            root= new BinaryNode<T>(null); // empty root
            LinkedList<GeneralTree<T>> childs = aTree.getChilds(); // Childs of the GT are implemented as a LinkedList of SubTrees
            child.begin(); //start iteration trough list
            BinaryTree<T> lt = new BinaryTree<T>(childs.element(0)); // first element = left-most child
            this.addLeftChild(lt);
            aTree.DeleteChild(hijos.elemento(0));
            BinaryTree<T> lr = new BinaryTree<T>(aTree);
            this.addRightChild(lr);
        }
    }

这是正确的方法吗？如果没有，你能想出更好的方法来解决这个问题吗？例如，这个解决方案给了我一堆根本没有数据的节点，我不知道这是问题本身的问题还是我的问题。

谢谢！

Answer 1

问题是大多数树无法有效地简化为二叉树。读了你的评论你就完全意识到了这一点。以一棵具有根节点和 3 个子节点的树为例。没有直接的方法可以在不牺牲连接性的情况下创建二叉树。这就是那些空节点的来源。有了它们，一般树的结构就被保留了。您可以重建它，删除空节点并从两个子树重新组装树。

我没有调试过你的代码。如果它按照你所说的那样做，那么这是一个很好的解决方案。空节点存储了一般树的连通性信息。他们被允许在那里。