import java.util.LinkedList;
import java.util.Queue;
public class Main {
class BinaryNode {
int val;
BinaryNode left;
BinaryNode right;
public BinaryNode(int val) {
this.val = val;
}
}//BinaryNode
private BinaryNode root;//根节点,这个属性很重要
private void buildOrderTree(int[] vals) {
for (int i = 0; i < vals.length; i++) {
insert(vals[i]);
}
}//build
private void insert(int val) {
root = insert(root, val);
}//insert
private BinaryNode insert(BinaryNode root, int val) {
if (root == null)
return new BinaryNode(val);
if (val <= root.val)
root.left = insert(root.left, val);//把该结点赋值给root结点的左孩子
else //把该结点赋值给root结点的右孩子
root.right = insert(root.right, val);//这里是递归，2在栈中没弹出来，4压入栈，4弹出栈后，栈中还有2，返回2
return root;
}//insert
public void printTreeLineByLine(BinaryNode root) {
Queue<BinaryNode> queue = new LinkedList<BinaryNode>();//把待打印的结点放在队列中
BinaryNode curNode;
queue.offer(root);
int curNum = 1;//当前行未打印的节点数
int next = 0;//下一行待打印的节点数
while (!queue.isEmpty()) {
curNode = queue.poll();
System.out.print(curNode.val + " ");
curNum--;
if (curNode.left != null) {
queue.offer(curNode.left);
next++;
}
if (curNode.right != null) {
queue.offer(curNode.right);
next++;
}
if (curNum == 0) {
curNum = next;
next = 0;
System.out.println();//换行
}
}//while
}//printTreeLineByLine
public static void main(String[] args) {
Main bst = new Main();
// int[] arr = {2, 4, 5, 1, 3,6,7,8,9,10,12,13,14,15,16,17,18};
int[] arr = {2, 4, 5, 1, 3, 6, 7, 8};
// int[] arr = {2, 4, 5, 1, 3};
bst.buildOrderTree(arr);
bst.printTreeLineByLine(bst.root);//用到了root属性
}
}
//2
//1 4
//3 5
//6
//7
//8
参考：http://www.cnblogs.com/hapjin/p/5738354.html
