二叉树的构建及遍历

      树是有穷节点的组，其中有一个节点作为根，根下面的其余节点以层次化方式组织。引用其下节点的节点是父节点，类似，由上层节点引用的节点是孩子节点。没有孩子的节点是叶子节点。一个节点可能同时是父节点和子节点。
一个父节点可以引用所需的多个孩子节点。在很多情况下，父节点至多只能引用两个孩子节点，基于这种节点的树称为二叉树。

public class TestBinTree {

	public List<Node> createBinTree(int[] array){
		List<Node> nodeList = new LinkedList<Node>();
		for (int i = 0; i < array.length; i++) {
			nodeList.add(new Node(array[i]));
		}
		for (int i = 0; i < array.length/2-1; i++) {
			nodeList.get(i).leftChild = nodeList.get(i*2+1);
			nodeList.get(i).rightChild = nodeList.get(i*2+2);
		}
		int lastIndex = array.length/2-1;
		nodeList.get(lastIndex).leftChild = nodeList.get(lastIndex*2+1);
		if(array.length%2==1){
			nodeList.get(lastIndex).rightChild = nodeList.get(lastIndex*2+2);
		}
		return nodeList;
	}
	
	public List<Node> insert(int obj,List<Node> nodeList){
		Node node = new Node(obj);
			if(nodeList.size()!=0){
				int lastIndex = nodeList.size()/2-1;
				if(lastIndex<0){
					nodeList.get(0).leftChild = node;	
				}else{
					Node rightChild = nodeList.get(lastIndex).rightChild; 
					if(rightChild==null){
						nodeList.get(lastIndex).rightChild = node;
					}else{
						nodeList.get(lastIndex+1).leftChild = node;
					}
				}
			}
			nodeList.add(node);
		return nodeList;
	}
	
	public void preOrder(Node node){
		if(node==null)
			return;
		System.out.print(node.data+"\t");
		preOrder(node.leftChild);
		preOrder(node.rightChild);
	}
	
	public void inOrder(Node node){
		if(node==null)
			return;
		inOrder(node.leftChild);
		System.out.print(node.data+"\t");
		inOrder(node.rightChild);
	}
	
	public void postOrder(Node node){
		if(node==null)
			return;
		postOrder(node.leftChild);
		postOrder(node.rightChild);
		System.out.print(node.data+"\t");
	}
	
	public static void main(String[] args) {
		TestBinTree testBinTree = new TestBinTree();
		int[] array = {1,2,3,4,5,6,7,8,9};
		List<Node> nodeList = new LinkedList<Node>();
		for (int i = 0; i < array.length; i++) {
			nodeList = testBinTree.insert(array[i],nodeList);
		}
		List<Node> binTree = testBinTree.createBinTree(array);
		Node root = binTree.get(0);
//		Node root = nodeList.get(0);
		
		System.out.println("先序遍历：");
		testBinTree.preOrder(root);
		System.out.println();
		
		System.out.println("中序遍历：");
		testBinTree.inOrder(root);
		System.out.println();
		
		System.out.println("后序遍历：");
		testBinTree.postOrder(root);
		System.out.println();
	}
}

class Node{
	Node leftChild;
	Node rightChild;
	int data;
	public Node(int data){
		this.data = data;
	}
}