使用數組自上而下，自左至右存儲完全二叉樹上的結點元素，即將完全二叉樹上編號為i的結點元素存儲在某個數組下標為i-1的分量中，然後通過一些方法確定結點在邏輯上的父子和兄弟關系。
根據二叉樹的性質，完全二叉樹和滿二叉樹樹采用順序存儲比較合適，樹中結點的序號可以唯一地反映出結點之間的邏輯關系，既能節省存儲空間，又能利用數組元素下標值確定結點在二叉樹中的位置，以及結點之間的關系。
而對於一般的二叉樹也必須按照完全二叉樹的形式存儲，也就是必須添加一些並不存在的虛擬結點，造成空間的浪費。
圖1 二叉樹順序存儲
順序存儲的關鍵是數組下標確定結點的位置，如結點從1開始編號，那麼結點i的左孩子為2*i，右孩子為2*i+1。不存在結點用0表示。
先回憶一下二叉樹的一些性質：
（1） 非空二叉樹第k層最多有2k-1個結點
（2） 高度為h的二叉樹至多有2h-1個結點
首先按照樹的高度height初始化一顆樹，以及一些有用的方法，代碼如下：
public class ArrayBiTree<T> {
private Object[] data;
private int height = 3; // 樹的高度 默認為3
private int n; // 結點個數
public ArrayBiTree() {
data = new Object[(int) Math.pow(2, height)];
init();
}
/**
* 指定深度初始化一個樹
* @param height 樹的深度
*/
public ArrayBiTree(int height) {
this.height = height;
data = new Object[(int) Math.pow(2, height) - 1];
}
private void init(){
System.out.println("默認生成一顆完全二叉樹，高度為3：");
for(int i=0; i<(int) Math.pow(2, height) - 1; i++){
data[i] = i+1;
n++;
}
print();
}
/**
* 判斷結點是否存在
* @param index 根節點從 1 開始
* @return
*/
public boolean isExist(int index){
if(index > n) return false;
return Integer.valueOf(data[index-1].toString()) != 0;
}
}
/**
* 層次遍歷，利用隊列是實現
*/
public void levelOrder(){
RingBuffer<Integer> queue = new RingBuffer<Integer>(n+1);
queue.put(1); // 根節點先進隊列
while(queue.size()>0){
int tmp = queue.get();
System.out.print(data[tmp-1]+" ");
if (isExist(2 * tmp)) { // 如果左子樹存在，把左子樹編號入棧
queue.put(2 * tmp);
}
if (isExist(2 * tmp + 1)) { // 如果右子樹存在，把右子樹編號入棧，
queue.put(2 * tmp + 1);
}
}
}
/**
* 先序遍歷，遞歸實現Recursion
* @param index 根節點從 1 開始
*/
public void preOrderRecur(int index){
if(isExist(index)){ //判斷結點是否存在
System.out.print(data[index-1]+" "); // 訪問根節點
preOrderRecur(2*index); // 遞歸遍歷左子樹
preOrderRecur(2*index + 1); // 遞歸遍歷右子樹
}
}
實現方法1：
/**
* 先序遍歷，非遞歸實現，借助棧來實現<p>
* 根節點先入棧，訪問棧頂結點，若棧頂元素的右孩子存在則入棧，若棧頂元素的左孩子存在則入棧，如此循環直到棧空
*/
public void preOrder(){
ArrayStack<Integer> stack = new ArrayStack<Integer>(n);
stack.push(1); // 根節點入棧
while(!stack.isEmpty()){
int tmp = stack.pop(); // 取根結點，把每個結點都看作根節點
System.out.print(data[tmp-1]+" "); // 訪問根結點
if (isExist(2 * tmp + 1)) { // 如果根節點的右子樹存在，把右子樹編號入棧
stack.push(2 * tmp + 1);
}
if (isExist(2 * tmp)) { // 如果根節點的左子樹存在，把左子樹編號入棧
stack.push(2 * tmp);
}
}
}
實現方法2：
/**
* 先序遍歷1，非遞歸實現，借助棧來實現<p>
* @param index 根節點從 1 開始
*/
public void preOrderOne(int index){
ArrayStack<Integer> stack = new ArrayStack<Integer>(n);
while (isExist(index) || !stack.isEmpty()) {
// (1) 首先訪問根節點，一直往左下方走，直到一個左孩子不存在的結點。
while (isExist(index)) {
System.out.print(data[index - 1] + " ");
stack.push(index); // 根節點入棧，把每個結點都看作一個根節點，檢查其左右孩子是否存在
index = 2 * index;
}
// 此時，棧內是從根節點左孩子開始的左孩子���最後一個結點是不存在左孩子的結點
// (2) 拿棧頂元素，看其右孩子是否存在，把當前結點置為其右孩子，繼續循環判斷(1)
if (!stack.isEmpty()) {
int tmp = stack.pop(); // 彈出的左子樹結點
index = 2 * tmp + 1; // 看它的右孩子是否存在
}
}
}
/**
* 中序遍歷，遞歸實現Recursion
* @param index 根節點從 1 開始
*/
public void inOrderRecur(int index){
if(isExist(index)){
inOrderRecur(2*index); // 遞歸遍歷左子樹
System.out.print(data[index-1]+" "); // 訪問根節點
inOrderRecur(2*index + 1); // 遞歸遍歷右子樹
}
}
/**
* 中序遍歷，非遞歸實現，更改訪問時機即可
* @param index
*/
public void inOrder(int index){
ArrayStack<Integer> stack = new ArrayStack<Integer>(n);
while(isExist(index) || !stack.isEmpty()){
while(isExist(index)){
stack.push(index); // 根節點入棧
index = 2 * index; // 是否存在左孩子
}
if(!stack.isEmpty()){
int tmp = stack.pop(); // 彈出左孩子
System.out.print(data[tmp-1]+" "); // 訪問結點
index = 2 * tmp + 1; // 看左孩子的右孩子是否存在
}
}
}
/**
* 後序遍歷，遞歸實現Recursion
* @param index 根節點從 1 開始
*/
public void postOrderRecur(int index){
if(isExist(index)){
postOrderRecur(2*index); // 遞歸遍歷左子樹
postOrderRecur(2*index + 1); // 遞歸遍歷右子樹
System.out.print(data[index-1]+" "); // 訪問根節點
}
}
/**
* 後序遍歷，非遞歸實現<p>
* 與前中序相比實現比較麻煩，先訪問左子樹再訪問右子樹
*/
public void postOrder(int index){
ArrayStack<Integer> stack = new ArrayStack<Integer>(n);
int visited = 0; // 標記前一個已被訪問的結點
while(isExist(index) || !stack.isEmpty()){
while(isExist(index)){
stack.push(index); // 根節點入棧
index = 2 * index;
}// 先把 index 的左孩子全部找到
int top = stack.peek(); // 查看棧頂元素，沒有彈出，訪問完右孩子之後在彈出訪問根節點
// 如果當前結點不存在右孩子或者右孩子已經訪問過，則訪問當前結點
if(!isExist(2*top+1) || (2*top+1) == visited){
int tmp = stack.pop();
System.out.print(data[tmp-1]+" ");
visited = tmp;
} else { // 否則訪問右孩子
index = 2 * top + 1;
}
}
}
public static void main(String[] args) {
ArrayBiTree<Integer> biTree = new ArrayBiTree<Integer>();
System.out.print("先序遍歷(遞歸)：");
biTree.preOrderRecur(1);
System.out.print("\n中序遍歷(遞歸)：");
biTree.inOrderRecur(1);
System.out.print("\n後序遍歷(遞歸)：");
biTree.postOrderRecur(1);
System.out.print("\n層次遍歷：");
biTree.levelOrder();
System.out.print("\n先序遍歷(非遞歸)：");
biTree.preOrder();
// biTree.preOrderOne(1);
System.out.print("\n中序遍歷(非遞歸)：");
biTree.inOrder(1);
System.out.print("\n後序遍歷(非遞歸)：");
biTree.postOrder(1);
System.out.println();
biTree.stdIn();
}
相關閱讀：
二叉樹的常見問題及其解決程序 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