import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class buildBinaryTree {
// 静态内部类建立树结构
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) {this.val = val;}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
//建立二叉查找树
public static TreeNode buildBST(int[] arr) {
if (arr.length == 0) return new TreeNode();
TreeNode root = new TreeNode(arr[0]);
for (int i = 1; i < arr.length; i++) {
createBST(root, arr[i]);
}
return root;
}
private static void createBST(TreeNode root, int a) {
if (root.val > a) {
if (root.left == null)
root.left = new TreeNode(a);
else
createBST(root.left, a);
}
else {
if (root.right == null)
root.right = new TreeNode(a);
else
createBST(root.right, a);
}
}
//建立普通的二叉树
public static TreeNode buildBinaryTree(TreeNode root, int[] arr, int index) {
if (index > arr.length / 2) return root;
if (index == 1) root.val = arr[0];
root.left = new TreeNode(arr[2 * index - 1]);
root.right = new TreeNode(arr[2 * index]);
buildBinaryTree(root.left, arr, index + 1);
buildBinaryTree(root.right, arr, index + 2);
return root;
}
//层次遍历二叉树
public static List<Integer> leverOrder(TreeNode root) {
if (root == null) return new ArrayList<>();
List<Integer> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add((node.right));
}
}
return list;
}
//中旬遍历二叉树
public static List<Integer> inOrder(TreeNode root) {
if (root == null) return new ArrayList<>();
List<Integer> list = new ArrayList<>();
inOrder(root, list);
return list;
}
private static void inOrder(TreeNode root, List<Integer> list) {
if (root == null) return;
inOrder(root.left, list);
list.add(root.val);
inOrder(root.right, list);
}
//打印 List内容
private static void printList(List<Integer> l) {
for (int num : l) {
System.out.print(num + " ");
}
System.out.println();
}
// 测试函数
public static void main(String[] args) {
int[] arr = {1, 2, 4, 3, 5};
TreeNode r1 = buildBinaryTree.buildBST(arr);
TreeNode r2 = buildBinaryTree.buildBinaryTree(new TreeNode(), arr, 1);
List<Integer> l1 = buildBinaryTree.inOrder(r1);
List<Integer> l2 = buildBinaryTree.inOrder(r2);
printList(l1);
printList(l2);
}
} 
