统计和生成不同的二叉树
程序员文章站
2022-05-06 21:29:40
...
import java.util.*;
//统计和生成不同的二叉树
public class generateBinaryTree{
//二叉树节点的定义
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int data)
{
this.value=data;
}
}
//统计可能的二叉树的结构数
public static int numTrees(int n)
{
if(n<2){
return 1;
}
int[]num=new int[n+1];
num[0]=1;
//动态规划法
for(int i=1;i<n+1;i++)
{
for(int j=1;j<i+1;j++)
{
num[i]+=num[j-1]*num[i-j];
}
}
return num[n];
}
public static List<Node> generateTrees(int n) {
return generate(1, n);
}
//********************************************************
//生成不同的二叉树
public static List<Node> generate(int start, int end) {
List<Node> res = new LinkedList<Node>();
if (start > end) {
res.add(null);
}
Node head = null;
for (int i = start; i < end + 1; i++) {
head = new Node(i);
List<Node> lSubs = generate(start, i - 1);
List<Node> rSubs = generate(i + 1, end);
for (Node l : lSubs) {
for (Node r : rSubs) {
head.left = l;
head.right = r;
res.add(cloneTree(head));
}
}
}
return res;
}
public static Node cloneTree(Node head) {
if (head == null) {
return null;
}
Node res = new Node(head.value);
//递归调用
res.left = cloneTree(head.left);
res.right = cloneTree(head.right);
return res;
}
//**************************************************
//直观打印二叉树
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
//*************************************************
public static void main(String[]args)
{
int n = 4;
System.out.println(numTrees(n));
List<Node> res = generateTrees(n);
for (Node node : res) {
printTree(node);
}
}
}
推荐阅读
-
生成300个不同的随机数的SQL语句
-
PowerDesigner 建立与SQLSERVER 2005数据库的连接以便生成数据库和从数据库生成到PD中
-
PowerDesigner 建立与数据库的连接以便生成数据库和从数据库生成到PD中(Oracle 10G版)
-
Linux磁盘管理之df命令详细介绍和使用实例(统计文件或目录的磁盘占用情况)
-
Oracle中如何把表和索引放在不同的表空间里
-
python生成不重复随机数和对list乱序的解决方法
-
命名管道和匿名管道的区别(超详解析2者不同处)
-
jdk和jre的关系和区别(jdk和jre有什么不同)
-
HTML4和HTML5之间除了相似以外的10个主要不同
-
java 中的static关键字和final关键字的不同之处