如何从普通树创建二叉树？

Question

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

BinaryTree(GeneralTree<T> aTree)

此方法应该从通用树(gt)创建一个BinaryTree(bt)，如下所示：

每个顶点来自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 个子节点的树为例。没有直接的方法可以在不牺牲连接性的情况下创建二叉树。这就是那些空节点的来源。有了它们，一般树的结构就被保留了。您可以重建它，删除空节点并从两个子树重新组装树。

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

Answer 2

还有另一种广为人知的方法可以从普通树中生成二叉树，并且没有“连接节点”。
这种方法可以这样理解：

Node{                Node{
 data;                data;
 first_child;   =>    left;
 next_sibling;        right; 
}                    }

这基本上将一般树的子节点列表表示为链表，并且每个节点都具有对其子节点的链表的引用。正如您所看到的，这在结构上相当于二叉树。

因此，在伪代码中（为了简单起见，省略了边缘情况）

BinaryTree(gtree){
    root=BinaryNode(gtree.data,BinaryNode(gtree.children),null);
}

BinaryNode(List<gnode> sibs){
    BinaryNode(sibs.first.data,BinaryNode(sibs.first.children),BinaryTree(sibs.rest));
}

BinaryNode(data,left,right){
    data=data;
    left=left;
    right=right;
}

当然，如果您需要具有您所描述的结构，那么这将是无用的，但总的来说，这是创建一个相当好的方法二叉树与普通树的区别。