二叉樹順序存儲和遍歷

1 二叉樹的存儲

1.1 順序存儲

使用數組自上而下，自左至右存儲完全二叉樹上的結點元素，即將完全二叉樹上編號為i的結點元素存儲在某個數組下標為i-1的分量中，然後通過一些方法確定結點在邏輯上的父子和兄弟關系。

根據二叉樹的性質，完全二叉樹和滿二叉樹樹采用順序存儲比較合適，樹中結點的序號可以唯一地反映出結點之間的邏輯關系，既能節省存儲空間，又能利用數組元素下標值確定結點在二叉樹中的位置，以及結點之間的關系。

而對於一般的二叉樹也必須按照完全二叉樹的形式存儲，也就是必須添加一些並不存在的虛擬結點，造成空間的浪費。

圖1 二叉樹順序存儲

順序存儲的關鍵是數組下標確定結點的位置，如結點從1開始編號，那麼結點i的左孩子為2*i，右孩子為2*i+1。不存在結點用0表示。

先回憶一下二叉樹的一些性質：

（1） 非空二叉樹第k層最多有2^k-1個結點

（2） 高度為h的二叉樹至多有2^h-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; 
    }
}

1.2 層次遍歷

/**
 * 層次遍歷，利用隊列是實現
 */
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);
        }
    }
}

1.3 先序遍歷

1.3.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.3.2 非遞歸實現

實現方法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; // 看它的右孩子是否存在
        }
    }
}

1.4 中序遍歷

1.4.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); // 遞歸遍歷右子樹
    }
}

1.4.2 非遞歸實現

/**
 * 中序遍歷，非遞歸實現，更改訪問時機即可
 * @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; // 看左孩子的右孩子是否存在
        }
    }
}

1.5 後序遍歷

1.5.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]+" "); // 訪問根節點
    }
}

1.5.2 非遞歸實現

/**
 * 後序遍歷，非遞歸實現<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;
        }
    }
}

2 測試

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();
}

2.1 輸出結果

二叉樹的常見問題及其解決程序 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