二叉樹的定義：
二叉樹(BinaryTree)是n(n≥0)個結點的有限集，它或者是空集(n=0)，或者由一個根結點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。
二叉樹的遍歷方式主要有：先序遍歷(NLR)，中序遍歷(LNR)，後序遍歷(LRN)，和層次遍歷。
注意：
由二叉樹的先序序列和中序序列可以唯一地確定一顆二叉樹；
由二叉樹的後序序列和中序序列可以唯一地確定一顆二叉樹；
由二叉樹的層序序列和中序序列可以唯一地確定一棵二叉樹；
但，由二叉樹的先序序列和後序序列無法唯一地確定一棵二叉樹。
Java實現鏈式存儲的二叉樹以及其各種遍歷算法：
樹節點：
public class TreeNode<E> {
private E data; //數據域
private TreeNode<E> lchild; //左孩子
private TreeNode<E> rchild; //右孩子
TreeNode(){}
TreeNode(E e){
this.data = e;
}
TreeNode(E data,TreeNode<E> lchild, TreeNode<E> rchild){
this.data = data;
this.lchild = lchild;
this.rchild = rchild;
}
public void setData(E data){
this.data = data;
}
public E getData(){
return this.data;
}
public void setLchild(TreeNode<E> lchild){
this.lchild = lchild;
}
public TreeNode<E> getLchild(){
return this.lchild;
}
public void setRchild(TreeNode<E> rchild){
this.rchild = rchild;
}
public TreeNode<E> getRchild(){
return this.rchild;
}
}
二叉樹的Java實現：
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
/**
* @author Cherish
* 二叉樹的鏈式存儲結構
* @param <E>
*/
public class BinaryTree<E> {
private TreeNode<E> root; //根節點
private List<TreeNode> nodeList = null; //二叉樹節點的鏈式結構
public BinaryTree(){
}
public BinaryTree(TreeNode<E> root){
this.root = root;
}
//把一個數組轉化為一顆完全二叉樹
public TreeNode<E> buildTree(E[] array){
nodeList = new LinkedList<TreeNode>();
//將數組中的元素依次轉換為TreeNode節點，存放於鏈表中
for(int i=0; i< array.length; i++){
nodeList.add(new TreeNode(array[i]));
}
//對前（array.length / 2 - 1）個父節點，按照父節點與孩子節點的數字關系建立完全二叉樹
//對完全二叉樹，按從上到下，從左到右的順序依次編號0,1,2,3....N,則i>0的節點，其左孩子為（2*i+1），
//其右孩子為（2*i+2）
for(int j=0; j < (array.length/2-1);j++){
//左孩子
nodeList.get(j).setLchild(nodeList.get(j*2+1));
//右孩子
nodeList.get(j).setRchild(nodeList.get(j*2+2));
}
//最後一個父節點：因為最後一個父節點可能沒有右孩子，所以單獨處理
int index = array.length/2 -1;
//左孩子
nodeList.get(index).setLchild(nodeList.get(index*2+1));
//右孩子：如果數組的長度為奇數才有右孩子
if(array.length % 2 == 1){
nodeList.get(index).setRchild(nodeList.get(index*2+2));
}
root=nodeList.get(0); //設置根節點
return root;
}
//得到樹的高度
public int height(TreeNode<E> node){
if(node == null){
return 0;
}else{
int i = height(node.getLchild());
int j = height(node.getRchild());
return (i<j)?(j+1):(i+1);
}
}
//得到節點的個數
public int size(TreeNode<E> node){
if(node == null){
return 0;
}else{
return 1+ size(node.getLchild())+size(node.getRchild());
}
}
//遞歸實現先序遍歷 NLR
public void preOrder(TreeNode<E> node){
if(node != null){
System.out.print(node.getData() + " ");
preOrder(node.getLchild());
preOrder(node.getRchild());
}
}
//非遞歸實現先序遍歷 NLR
public void nonRecPreOrder(TreeNode<E> node){
Stack<TreeNode<E>> nodeStack = new Stack<TreeNode<E>>();
TreeNode<E> nodeTemp = node; //nodeTemp作為遍歷指針
while(nodeTemp != null || !nodeStack.isEmpty()){ //當nodeTemp非空或棧非空時循環
if(nodeTemp != null){ //根指針非空，遍歷左子樹
nodeStack.push(nodeTemp); //根指針進棧
System.out.print(nodeStack.peek().getData() + " "); //根指針退棧，訪問根節點
nodeTemp = nodeTemp.getLchild(); //每遇到非空二叉樹先向左走
}else{ //再向右子樹走
nodeTemp = nodeStack.pop();
nodeTemp = nodeTemp.getRchild();
}
}
}
//遞歸實現中序遍歷 LNR
public void inOrder(TreeNode<E> node){
if(node != null){
inOrder(node.getLchild());
System.out.print(node.getData() + " ");
inOrder(node.getRchild());
}
}
//非遞歸實現中序遍歷 LNR
public void nonRecInOrder(TreeNode<E> node){
Stack<TreeNode<E>> nodeStack = new Stack<TreeNode<E>>();
TreeNode<E> nodeTemp = node; //nodeTemp作為遍歷指針
while(nodeTemp != null || !nodeStack.isEmpty()){ //當nodeTemp非空或棧非空時循環
if(nodeTemp != null){ //根指針非空，遍歷左子樹
nodeStack.push(nodeTemp); //根指針進棧
nodeTemp = nodeTemp.getLchild(); //每遇到非空二叉樹先向左走
}else{
nodeTemp = nodeStack.pop(); //根指針退棧，訪問根節點
System.out.print(nodeTemp.getData() +" ");
nodeTemp = nodeTemp.getRchild(); //再向右子樹走
}
}
}
//遞歸實現後序遍歷 LNR
public void postOrder(TreeNode<E> node){
if(node != null){
postOrder(node.getLchild());
postOrder(node.getRchild());
System.out.print(node.getData() + " ");
}
}
//非遞歸實現後序遍歷 LNR
public void nonRecPostOrder(TreeNode<E> node){
Stack<TreeNode<E>> nodeStack = new Stack<TreeNode<E>>();
TreeNode<E> nodeTemp = node; //nodeTemp作為遍歷指針
TreeNode<E> preNode = null; //表示最近一次訪問的節點
while(nodeTemp != null || !nodeStack.isEmpty()){ //當nodeTemp非空或棧非空時循環
while(nodeTemp != null){ //一直向左走，遍歷左子樹
nodeStack.push(nodeTemp);
nodeTemp = nodeTemp.getLchild();
}
nodeTemp = nodeStack.peek();
if(nodeTemp.getRchild()==null || nodeTemp.getRchild() == preNode){ //右子樹為空或右子樹已被訪問時，該節點出棧
nodeTemp = nodeStack.pop();
System.out.print(nodeTemp.getData()+" ");
preNode = nodeTemp; //將該節點賦值給最近一個訪問節點
nodeTemp = null; //此處很重要，將剛出棧節點設置為空，對應於while循環的條件之一，否則陷入死循環
}else{
nodeTemp = nodeTemp.getRchild(); //遍歷右子樹
}
}
}
//層次遍歷
public void levelOrder(TreeNode<E> root){
Queue<TreeNode<E>> nodeQueue = new LinkedList<TreeNode<E>>();
TreeNode<E> node = null;
nodeQueue.add(root); //將根節點入隊
while(!nodeQueue.isEmpty()){ //隊列不空循環
node = nodeQueue.peek();
System.out.print(node.getData()+" ");
nodeQueue.poll(); //隊頭元素出隊
if(node.getLchild() != null){ //左子樹不空，則左子樹入隊列
nodeQueue.add(node.getLchild());
}
if(node.getRchild() != null){ //右子樹不空，則右子樹入隊列
nodeQueue.add(node.getRchild());
}
}
}
public static void main(String args[]){
//將一個數組轉化為一顆完全二叉樹
Object[] array = {1,2,3,4,5,6,7,8};
BinaryTree bt = new BinaryTree();
TreeNode root = bt.buildTree(array);
System.out.print("樹的高度：");
System.out.println(bt.height(root));
System.out.print("節點的個數：");
System.out.println(bt.size(root));
System.out.println("先序遍歷：");
bt.preOrder(root);
System.out.println("\n"+"非遞歸先序遍歷：");
bt.nonRecPreOrder(root);
System.out.println();
System.out.println("中序遍歷：");
bt.inOrder(root);
System.out.println("\n"+"非遞歸中序遍歷：");
bt.nonRecInOrder(root);
System.out.println();
System.out.println("後序遍歷：");
bt.postOrder(root);
System.out.println("\n"+"非遞歸後序遍歷：");
bt.nonRecPostOrder(root);
System.out.println();
System.out.println("層次遍歷：");
bt.levelOrder(root);
//手工構建一顆二叉樹
TreeNode nodeA = new TreeNode("A");
TreeNode nodeB = new TreeNode("B");
TreeNode nodeC = new TreeNode("C");
TreeNode nodeD = new TreeNode("D");
TreeNode nodeE = new TreeNode("E");
TreeNode nodeF = new TreeNode("F");
TreeNode nodeG = new TreeNode("G");
TreeNode nodeH = new TreeNode("H");
TreeNode nodeI = new TreeNode("I");
nodeA.setLchild(nodeB);
nodeA.setRchild(nodeD);
nodeB.setRchild(nodeC);
nodeD.setLchild(nodeE);
nodeD.setRchild(nodeF);
nodeF.setLchild(nodeG);
nodeF.setRchild(nodeI);
nodeG.setRchild(nodeH);
System.out.println("\n\n"+"*****************");
System.out.print("樹的高度：");
System.out.println(bt.height(nodeA));
System.out.print("節點的個數：");
System.out.println(bt.size(nodeA));
System.out.println("先序遍歷：");
bt.preOrder(nodeA);
System.out.println();
System.out.println("中序遍歷：");
bt.inOrder(nodeA);
System.out.println();
System.out.println("後序遍歷：");
bt.postOrder(nodeA);
System.out.println();
System.out.println("層次遍歷：");
bt.levelOrder(nodeA);
}
}
上述程序的運行結果：
樹的高度：4
節點的個數：8
先序遍歷：
1 2 4 8 5 3 6 7
非遞歸先序遍歷：
1 2 4 8 5 3 6 7
中序遍歷：
8 4 2 5 1 6 3 7
非遞歸中序遍歷：
8 4 2 5 1 6 3 7
後序遍歷：
8 4 5 2 6 7 3 1
非遞歸後序遍歷：
8 4 5 2 6 7 3 1
層次遍歷：
1 2 3 4 5 6 7 8
*****************
樹的高度：5
節點的個數：9
先序遍歷：
A B C D E F G H I
中序遍歷：
B C A E D G H F I
後序遍歷：
C B E H G I F D A
層次遍歷：
A B D C E F G I H
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm
