生成具有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：这里有一个类似的帖子。如果有人能详细解释coproc在这个帖子中提出的生成树算法，那将会非常有帮助。

提前感谢。

- prashant

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

- IsAs

Answer 2

我在这里使用递归。通过使用动态规划，可以改进此代码。希望这有所帮助。我们从左侧开始一个节点，一个节点作为根节点，右侧有N-i-1个节点。然后，我们将节点成对从右侧移动到左侧。

import java.util.ArrayList;
import java.util.List;

public class NumberOfFullBTrees {

    public static void main(String[] args) {
        int N = 5;
        NumberOfFullBTrees numberOfFullBTrees = new NumberOfFullBTrees();
        List<TreeNode> result = numberOfFullBTrees.allPossibleFBT(N);
    }

    /**
     * Builds all possible full binary trees. We start by 1 node in left, 1 note at root and n-2 node in right.
     * We move the nodes in pairs from right to left. This method uses recursion. This method can be improved by
     * using dynamic programming.
     *
     * @param N The number of nodes
     * @return The possible full binary trees with N nodes as a list
     */
    public List<TreeNode> allPossibleFBT(int N) {
        List<TreeNode> result = new ArrayList<>();
        if (N % 2 == 0) {
            return result;
        }
        if (N == 1) {
            result.add(new TreeNode(0));
            return result;
        }
        for (int i = 1; i < N; i += 2) {
            List<TreeNode> lefts = allPossibleFBT(i);
            List<TreeNode> rights = allPossibleFBT(N - i - 1);
            for (TreeNode l : lefts) {
                for (TreeNode r : rights) {
                    TreeNode root = new TreeNode(0);
                    root.left = l;
                    root.right = r;
                    result.add(root);
                }
            }
        }
        return result;
    }

}

- Mohammad