binary-tree - 在具有 n 个节点的完整二叉树中生成所有可能的拓扑

Question

我想创建一个完整的二叉树的所有可能的拓扑，它必须正好有 n+1 个叶节点和 n 个内部节点。

我想使用递归创建它，树必须是简单的二叉树，而不是二叉搜索树或 BST。

请建议算法来实现此任务。

例如:有 4 个叶节点和 3 个内部节点。

     N                  N                  N
    / \                / \                 /\
   N   N               N  N               N  N
  /\   /\             /\                     /\
 N  N  N N           N  N                    N N
                    / \                        /\
                    N  N                       N N

PS:有一个类似的 thread .如果有人可以详细说明 coproc建议的树生成算法，这将很有帮助。在此 thread .

提前致谢。

Answer 1

这是为给定 n 生成所有可能拓扑的代码。完整二叉树中的节点总数(内部 + 叶节点)是奇数。

如果一棵树是满二叉树，那么它的左子树和右子树也是全二叉树，即左子树和右子树都有奇数个节点。

对于给定的 n，我们像这样生成全二叉树的所有组合

第一次迭代:左侧有 1 个节点，右侧有 1 个根节点，n-2 个。
第二次迭代:左侧有 3 个节点，右侧有 1 个根节点，n-4 个。
第三次迭代:左侧有 5 个节点，右侧有 1 个根节点，n-6 个。
.
.
.
最后一次迭代:左侧 n-2 个节点，1 个根，右侧 1 个

在每次迭代中，我们找到所有可能的左树和右树。如果左侧可能有 L 棵完整树，则右侧可能有 R 棵完整树 - 那么树的总数为 L*R

public void createAllTopologies(int n){

    if(n%2 == 0) return;

    Map<Integer, List<Node>> topologies = new HashMap<Integer, List<Node>>();

    topologies.put(1, new ArrayList<Node>());
    topologies.get(1).add(new Node(1));

    for(int i=3;i<=n;i+=2){

        List<Node> list = new ArrayList<Node>();

        for(int j=1;j<i;j+=2){
            List<Node> left = topologies.get(j);
            List<Node> right = topologies.get(i-j-1);
            list.addAll(generateAllCombinations(left,right));
        }
        topologies.put(i, list);
    }

    List<Node> result = topologies.get(n);

    for(int i=0;i<result.size();i++){
        printTree(result.get(i),0);
        System.out.println("-----------------------------");
    }

}

private List<Node> generateAllCombinations(List<Node> left, List<Node> right) {

    List<Node> list = new ArrayList<Node>();
    for(int i=0;i<left.size();i++){
        for(int j=0;j<right.size();j++){
            Node nNode = new Node(1);
            nNode.left = left.get(i).clone();
            nNode.right = right.get(j).clone();
            list.add(nNode);
        }
    }
    return list;
}

/* This prints tree from left to right fashion i.e 
       root at left, 
       leftNode at bottom, 
       rightNode at top 
*/

protected void printTree(Node nNode,int pos){
        if (nNode==null) {
            for(int i=0;i<pos;i++) System.out.print("\t");
            System.out.println("*");
            return;
        }
        printTree(nNode.right,pos+1);
        for(int i=0;i<pos;i++) System.out.print("\t");
        System.out.println(nNode.data);
        printTree(nNode.left,pos+1);

}

请引用这里的完整代码 - http://ideone.com/Wz2Jhm