4

我想创建一个完整的二叉树的所有可能的拓扑结构，它必须恰好有 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建议的树生成算法，将会很有帮助。

提前致谢。

4

2 回答 2

3

这是为给定 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

于 2013-10-20T12:51:29.537 回答
0

我在这里使用递归。可以通过使用动态编程来改进此代码。我希望这有帮助。我们从左边的一个节点开始，一个节点作为根节点，右边的 Ni-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;
    }

}
于 2020-03-21T20:09:29.300 回答