欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

统计和生成不同的二叉树

程序员文章站 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);
		}
	}
}
统计和生成不同的二叉树