在具有n个节点的完整二叉树中生成所有可能的拓扑 [英] Generating all possible topologies in a full binary tree having n nodes

问题描述

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

I want to create all possible topologies of a full binary tree which must have exactly n+1 leaf nodes and n internal nodes.

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

I want to create it using recursion and tree must be simple binary tree not a binary search tree or BST.

请提出实现此任务的算法.

Kindly suggest algorithm to achieve this task.

示例:具有4个叶节点和3个内部节点.

example: with 4 leaf nodes and 3 internal nodes.

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

PS:有一个类似的线程.如果有人可以详细阐述<此线程 coproc >.

PS: There is a simlar thread .It will be helpful If anybody can elaborate the tree generation algorithm suggested by coproc in this thread.

谢谢.

推荐答案

以下是用于生成给定n的所有可能拓扑的代码.完整二叉树中的节点总数(内部+叶子节点)是奇数.

Here is the code for generating all possibles topologies for given n. Total Number of nodes (internal + leaf nodes) in a full binary tree is odd.

如果树是完整的二叉树，那么它的左右子树也是完整的二叉树，即左右子树的节点数都是奇数.

If a tree is full binary tree, then it's left and right sub trees are also full binary trees i.e both left and right sub trees have odd number of nodes.

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

For a given n, We generate all combinations of full binary tree like this

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

First Iteration: 1 Node on left hand side, 1 root, n-2 on right hand side.
Second Iteration: 3 Nodes on left hand side, 1 root, n-4 on right hand side.
Third Iteration: 5 Nodes on left hand side, 1 root, n-6 on right hand side. .
.
.
Last Iteration: n-2 Nodes on left hand side, 1 root, 1 on right hand side

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

In each iteration, we find all possible left trees and right trees. If L full trees are possible on left hand side, R full trees are possible on right hand side - then total number of trees is 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

Please refer to complete code here - http://ideone.com/Wz2Jhm

这篇关于在具有n个节点的完整二叉树中生成所有可能的拓扑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！