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