根据数组建立平衡二叉搜索树

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉（搜索）树。

二分：用有序数组中中间的数生成搜索二叉树的头节点，然后对数组的左右部分分别生成左右子树即可（重复过程）。

生成的二叉树中序遍历一定还是这个序列。

非常简单，不过多叙述：

      public class SortedArrayToBalancedBST {
     	public static class Node {
     		public int value;
     		public Node left;
     		public Node right;
     		public Node(int data) {
     			this.value = data;
      		}
      	}
     	public static Node generateTree(int[] sortArr) {
     		if (sortArr == null) {
     			return null;
      		}
     		return generate(sortArr, 0, sortArr.length - 1);
      	}
     	public static Node generate(int[] sortArr, int start, int end) {
     		if (start > end) {
     			return null;
      		}
     		int mid = (start + end) / 2;
      		Node head = new Node(sortArr[mid]);
      		head.left = generate(sortArr, start, mid - 1);
      		head.right = generate(sortArr, mid + 1, end);
     		return head;
      	}
     	// for test -- print tree
     	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[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
      		printTree(generateTree(arr));
      	}
      }
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/84556551