代碼GitHub地址

樹

無論是鏈表，棧還是隊列，它們都是線性結構的倡鲸，每個節(jié)點的左邊最多一個節(jié)點羔巢，右邊也最多一個節(jié)點匪燕。對于大量的輸入數(shù)據(jù)哀澈，線性表的訪問時間太長，效率較低蛉威，不宜使用日丹。
因此需要一種非線性的數(shù)據(jù)結構，樹型結構蚯嫌，其大部分操作的運行時間平均為O(logN)哲虾。

線性結構可以理解為樹的一種特殊表現(xiàn)形式丙躏。

關于樹的一些術語

• 節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度，樹的度是樹內各節(jié)點的度的最大值
• 葉節(jié)點或終端節(jié)點：度為零的節(jié)點稱為葉節(jié)點束凑；
• 非終端節(jié)點或分支節(jié)點：度不為零的節(jié)點晒旅；
• 雙親節(jié)點或父節(jié)點：若一個結點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點汪诉；
• 孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點废恋；
• 兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點；
• 樹的高度或深度：定義一棵樹的根結點層次為1扒寄，其他節(jié)點的層次是其父結點層次加1鱼鼓。一棵樹中所有結點的層次的最大值稱為這棵樹的深度。
• 節(jié)點的層次：從根開始定義起该编，根為第1層迄本，根的子結點為第2層，以此類推课竣；
• 樹的度：一棵樹中嘉赎，最大的節(jié)點的度稱為樹的度；
• 節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點于樟；
• 子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫公条。
• 森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

樹的應用

大部分操作系統(tǒng)的目錄結構就是采用樹結構迂曲。樹的種類有很多靶橱，樹所擴展出來的很多數(shù)據(jù)結構都有著很大的作用，比如說紅黑樹路捧，B樹抓韩，后綴樹等等。

樹的表示方法

• 雙親表示法 [找父親鬓长，找孩子]

  • 優(yōu)點：很容易定位某個節(jié)點的雙親節(jié)點。時間復雜度O(1)
  • 缺點：如果想知道該節(jié)點的孩子節(jié)點尝江。必須遍歷整個結構才知道
  • 解決辦法：為節(jié)點新增一個長子域(指向節(jié)點的左孩子)涉波。如果沒有設為-1。

• 孩子表示法

  • 具體辦法：把每個節(jié)點的孩子節(jié)點排列起來炭序，以單鏈表作存儲結構啤覆，則n個節(jié)點有n個孩子鏈表，如果是葉子節(jié)點則此單鏈表為空惭聂。然后n個節(jié)點有n個孩子鏈表窗声，如果是葉子節(jié)點則此單鏈表為空。然后n個頭指針又組成一個線性表辜纲，采用順序存儲結構笨觅。存放進一個一維數(shù)組
  • 優(yōu)點：既可以讓我們找到節(jié)點的孩子也可以找到節(jié)點的兄弟拦耐。
  • 缺點，父親還是找不到

• 孩子兄弟表示法

  • 具體辦法：每個節(jié)點具有data屬性以及firstchild和rightsib的兩個屬性见剩。這樣就可以方便的找到某個節(jié)點的兄弟節(jié)點以及孩子節(jié)點杀糯，但在尋找其雙親節(jié)點的時候任然有難度。但其實只要再多加一個指針即可苍苞。
  • 優(yōu)點：最大的優(yōu)點或許就是這種表示法把這棵樹變成了一顆二叉樹固翰。

需要注意的是：節(jié)點并不是包含的數(shù)據(jù)域越多越好，這由整個算法適用的整體情況來定羹呵。畢竟屬性多了骂际，內存占用也大。

二叉樹

二叉樹是樹形結構的一個重要類型冈欢。

許多實際問題抽象出來的數(shù)據(jù)結構往往是二叉樹的形式歉铝，即使是一般的樹也能簡單地轉換為二叉樹，比如在某個階段都是兩種結果的情形涛癌，比如開和關犯戏，0和1，真和假等都適合用二叉樹來建模拳话。而且二叉樹的存儲結構及其算法都較為簡單先匪，因此二叉樹顯得特別重要。

需要注意的是：二叉樹的左子樹和右子樹是嚴格區(qū)分并且不能隨意顛倒的

二叉樹種類

• 斜二叉樹
• 滿二叉樹
• 完全二叉樹

一般二叉樹的實現(xiàn)都是基于鏈表而來弃衍。順序存儲結構一般只用于完全二叉樹呀非。我們一般判斷是否適合的判斷方法是，能否方便的找到節(jié)點的孩子節(jié)點镜盯，雙親節(jié)點岸裙。有時一般二叉樹也可以使用順序結構存儲，只是我們需要將樹種缺少的節(jié)點補齊速缆。這是一種以空間換時間的方式

二叉樹實現(xiàn)

二叉樹中每個節(jié)點都有兩個節(jié)點指針屬性降允，分別指向其左孩子和右孩子節(jié)點。如果想找尋其雙親節(jié)點只要再添加一個指向其雙親節(jié)點的屬性即可艺糜，這樣就成了三叉樹了剧董，和之前我們說過的樹結構一樣了。

二叉樹操作集

二叉樹重要操作有：

• 判斷非空
• 遍歷
• 創(chuàng)建一個二叉樹

遍歷方式：

環(huán)繞節(jié)點

• 前序：先根破停，再左翅楼，后右 (第一次碰到節(jié)點時push出來)
• 中序：先左，再根真慢，后右 (第二次碰到節(jié)點時push出來)
• 后序：先左毅臊，再右，后根 (第三次碰到節(jié)點時push出來)
• 層序：從上到下逐層遍歷黑界，同一層中從左到右逐個訪問。

在通過兩種序列確定一棵樹結構的時候，必須至少具有中序遍歷锭部。

遍歷

image

前序遍歷

/**
 * 前序遍歷
 * 中 左 右
 *
 * @param binaryTree
 * @return
 */
public static void preOrderTraverse(BinaryTree binaryTree) {
    if (binaryTree == null) {
        return;
    }
    System.out.println(binaryTree.value);
    preOrderTraverse(binaryTree.lchild);
    preOrderTraverse(binaryTree.rchild);
}

/**
 * 非遞歸前序遍歷
 *
 * @param binaryTree
 */
public static void nonRecursivepreOrderTraverse(BinaryTree binaryTree) {
    BinaryTree tree;
    Stack stack = new Stack();
    while (binaryTree != null || !stack.empty()) {
        while (binaryTree != null) {
            stack.push(binaryTree);
            System.out.println(binaryTree.value);
            binaryTree = binaryTree.lchild;
        }
        if (!stack.empty()) {
            tree = (BinaryTree) stack.pop();
            binaryTree = tree.rchild;
        }
    }
}

遞歸方法的三序遍歷都很簡單挑围。非遞歸方式的前序遍歷，只要想成入棧操作即可。只是節(jié)點的孩子節(jié)點在入棧的時候是先入右孩子再入左孩子。

中序遍歷

/**
 * 中序遍歷
 * 左 中 右
 *
 * @param binaryTree
 */
public static void inOrderTraverse(BinaryTree binaryTree) {
    if (binaryTree == null) {
        return;
    }
    inOrderTraverse(binaryTree.lchild);
    System.out.println(binaryTree.value);
    inOrderTraverse(binaryTree.rchild);
}

/**
 * 非遞歸中序遍歷 - 棧
 *
 * @param binaryTree
 */
public static void nonRecursiveInOrderTraverse(BinaryTree binaryTree) {
    BinaryTree tree;
    Stack stack = new Stack();
    while (binaryTree != null || !stack.empty()) {
        while (binaryTree != null) {
            stack.push(binaryTree);
            binaryTree = binaryTree.lchild;
        }
        if (!stack.empty()) {
            tree = (BinaryTree) stack.pop();
            System.out.println(tree.value);
            binaryTree = binaryTree.rchild;
        }
    }
}

需要注意的是，三序遍歷的區(qū)別無非第幾次碰到時打印著隆。

• 遞歸方式的實現(xiàn)思路很簡單不贅述了。
• 非遞歸的原理還是遞歸呀癣。表示手法變了而已美浦，需要注意的是別漏了stack的判斷，嚴謹一點兒比較好项栏。

流程：

1. 判斷 - 是否空樹或者棧滿了
2. 循環(huán) - 在數(shù)不為空的情況下浦辨，循環(huán)push當前樹的左子樹。
3. 判斷 - 如果棧不為空沼沈，pop出棧頂元素并打印流酬，切換到該樹的右子樹繼續(xù)。

后序遍歷

/**
 * 后序遍歷
 * 左 右 中
 *
 * @param binaryTree
 */
public static void postOrderTraverse(BinaryTree binaryTree) {
    if (binaryTree == null) {
        return;
    }
    postOrderTraverse(binaryTree.lchild);
    postOrderTraverse(binaryTree.rchild);
    System.out.println(binaryTree.value);
}

層序遍歷

/**
 * 層序遍歷
 *
 * @param binaryTree
 */
public static void theSequenceTraverse(BinaryTree binaryTree) {
    if (binaryTree == null) {
        return;
    }

    ArrayBlockingQueue queue = new ArrayBlockingQueue(10);
    BinaryTree tree;

    queue.add(binaryTree.value);
    while (!queue.isEmpty()) {
        tree = (BinaryTree) queue.remove();
        System.out.println(tree.value);
        if (tree.lchild != null) {
            queue.add(tree.lchild);
        }
        if (tree.rchild != null) {
            queue.add(tree.rchild);
        }
    }
}

層序這里我們使用了隊列的方式進行打印更簡單一些列另。每個節(jié)點push進去然后每次打印頭節(jié)點芽腾，打印出來的頭結點再把左右孩子節(jié)點分別push進去等待remove即可。利用隊列存儲規(guī)則

打印所有葉子節(jié)點

/**
 * 輸出一顆二叉樹的所有葉子節(jié)點
 *
 * @param binaryTree
 */
public static void pushLeafnode(BinaryTree binaryTree) {
    if (binaryTree == null) {
        return;
    }
    if (binaryTree.lchild == null && binaryTree.rchild == null) {
        System.out.println(binaryTree.value);
    }
    pushLeafnode(binaryTree.lchild);
    pushLeafnode(binaryTree.rchild);
}

遞歸實現(xiàn)页衙。在任意一種遍歷前加一個判斷語句打印即可摊滔。只要一個節(jié)點不存在左右孩子那么即是leafnode。

計算二叉樹高度

/**
 * 計算二叉樹高度
 *
 * @param binaryTree
 * @return
 */
public static int high(BinaryTree binaryTree) {
    int maxHigh;
    int leftHigh;
    int rightHigh;
    if (binaryTree != null) {
        leftHigh = high(binaryTree.lchild);
        rightHigh = high(binaryTree.rchild);
        maxHigh = leftHigh > rightHigh ? leftHigh : rightHigh;
        return maxHigh + 1;
    }
    return 0;
}

借用后序遍歷處理邏輯店乐。在遞歸左右子樹的時候艰躺，把原先的打印換成比較大小即可。

二叉搜索樹

二叉搜索樹利用了二分查找的原理眨八。之前我們說的二分查找樹是基于數(shù)組的腺兴，雖然查找迅速，但是面臨著插入和刪除上的不便廉侧。所以我們可以把這種思路通過二叉樹來實現(xiàn)含长。

• 二叉搜索樹任意節(jié)點的左葉子節(jié)點都小于該節(jié)點。右葉子節(jié)點都大于該節(jié)點伏穆。

二叉搜索樹操作集

查找某一節(jié)點地址

/**
 * 二叉搜索樹查找某一節(jié)點(尾遞歸)
 *
 * @return
 */
public static BinaryTree recursiveFind(BinaryTree binaryTree, int value) {
    if (binaryTree == null) {
        return null;
    }
    if (value > binaryTree.value) {
        return recursiveFind(binaryTree.rchild, value);
    }
    if (value < binaryTree.value) {
        return recursiveFind(binaryTree.lchild, value);
    }
    return binaryTree;
}

/**
 * 二叉搜索樹查找某一節(jié)點(迭代)
 *
 * @param binaryTree
 * @param value
 * @return
 */
public static BinaryTree ineratorFind(BinaryTree binaryTree, int value) {
    if (binaryTree == null) {
        return null;
    }
    while (binaryTree != null) {
        if (value > binaryTree.value) {
            binaryTree = binaryTree.rchild;
        } else if (value < binaryTree.value) {
            binaryTree = binaryTree.lchild
        } else {
            return binaryTree;
        }
    }
    return null;
}

查找某一節(jié)點的算法利用的是遞歸的方式，而且可以看出來是尾遞歸纷纫。所以可以優(yōu)化成循環(huán)的方式枕扫，但是這種尾遞歸的算法，現(xiàn)如今編譯器在編譯的時候已經(jīng)可以給我們優(yōu)化成循環(huán)的算法辱魁。所以遞歸的寫法還是最好的烟瞧，因為看上去簡潔明了诗鸭。

• 這種算法的查找效率取決于樹的高度。如果該樹是個斜樹的話那么時間復雜度即是O(n)参滴，否則即是O(log n)

查找最小元素地址

/**
 * 查找二叉搜索樹中最小元素
 * 非遞歸
 *
 * @param binaryTree
 * @return
 */
public static BinaryTree nonRecursiveFindMin(BinaryTree binaryTree) {
    if (binaryTree == null) {
        return null;
    }
    while (binaryTree.lchild != null) {
        binaryTree = binaryTree.lchild;
    }
    return binaryTree;
}

/**
 * 查找二叉搜索樹中最小元素
 * 遞歸
 *
 * @param binaryTree
 * @return
 */
public static BinaryTree recursiveFindMin(BinaryTree binaryTree) {
    if (binaryTree == null) {
        return null;
    }
    // 真正退出遞歸的條件
    if (binaryTree.lchild == null) {
        return binaryTree;
    } 
        
    return recursiveFindMin(binaryTree.lchild);
}

查找最大元素地址

/**
 * 查找二叉搜索樹中最大元素
 * 非遞歸
 *
 * @param binaryTree
 * @return
 */
public static BinaryTree nonRecursiveFindMax(BinaryTree binaryTree) {
    if (binaryTree == null) {
        return null;
    }
    while (binaryTree.rchild != null) {
        binaryTree = binaryTree.rchild;
    }
    return binaryTree;
}

/**
 * 查找二叉搜索樹中最大元素
 * 遞歸
 *
 * @param binaryTree
 * @return
 */
public static BinaryTree recursiveFindMax(BinaryTree binaryTree) {
    if (binaryTree == null) {
        return null;
    }
    if (binaryTree.rchild == null) {
        return binaryTree;
    }
    return recursiveFindMax(binaryTree.rchild);
}

插入元素

/**
 * 二叉搜索樹插入節(jié)點
 *
 * @param binaryTree
 * @param value
 * @return
 */
public static BinaryTree insert(BinaryTree binaryTree, int value) {
    if (binaryTree == null) {
        binaryTree = new BinaryTree();
        binaryTree.value = value;
        binaryTree.lchild = null;
        binaryTree.rchild = null;
    } else if (value > binaryTree.value) {
        binaryTree.rchild = insert(binaryTree.rchild, value);
    } else if (value < binaryTree.value) {
        binaryTree.lchild = insert(binaryTree.lchild, value);
    }
    // 遞歸時分析清楚强岸，該層返回的內容 對于上層是什么
    return binaryTree;
}

插入時我們沒有判斷插入已有節(jié)點的情況。
同時插入節(jié)點時只要清楚砾赔，我們最終要插入的位置肯定是一個空的位置蝌箍。我們只是要定位這個空的位置

刪除元素

/**
 * 二叉搜索樹刪除節(jié)點
 *
 * @param binaryTree
 * @param value
 * @return
 */
public static BinaryTree remove(BinaryTree binaryTree, int value) {
    if (binaryTree == null) {
        return null;
    }
    if (value < binaryTree.value) {
        binaryTree.lchild = remove(binaryTree.lchild, value);
    } else if (value > binaryTree.value) {
        binaryTree.rchild = remove(binaryTree.rchild, value);
    } else {
        if (binaryTree.lchild != null && binaryTree.rchild != null) {
            // 右子樹找最小，左子樹找最大
            BinaryTree tempTree = nonRecursiveFindMin(binaryTree.rchild);
            // 替換找到的節(jié)點的值暴心，然后犧牲掉給值的節(jié)點妓盲。
            binaryTree.value = tempTree.value;
            binaryTree.rchild = remove(binaryTree.rchild, tempTree.value);
        } else {
            if (binaryTree.lchild == null) {
                binaryTree = binaryTree.rchild;
            } else if (binaryTree.rchild == null) {
                binaryTree = binaryTree.lchild;
            }
        }
    }
    return binaryTree;
}

待刪除節(jié)點有兩個孩子節(jié)點時：

• 我們從其左子樹找到最大節(jié)點，或者從其右子樹找到最小節(jié)點专普。因為二叉搜索樹的性質悯衬，找到右子樹最小元素后拿出其value來賦予待刪除節(jié)點。然后再把這個最小節(jié)點通過特定值搜索刪除即可檀夹。然后我們再把這個被修改過value得待刪除節(jié)點binaryTree返回給其雙親節(jié)點筋粗。雖然其沒有被刪除只是被改值了，但是也是達到了刪除節(jié)點的目的炸渡。只是刪除了另一個替代節(jié)點

待刪除節(jié)點只有一個孩子節(jié)點時：

• 我們對二叉樹種某一節(jié)點刪除操作其實就是把其雙親節(jié)點對其的指向改變娜亿。由于函數(shù)調用外層已經(jīng)用雙親節(jié)點的孩子指針來指向返回值，所以我們只需要找到待刪除節(jié)點并且把其替代節(jié)點覆蓋的賦予binartTree并返回即可偶摔。

二叉搜索樹的節(jié)點刪除有兩種策略：

• 可以取右子樹中最小元素(沒有左子樹)或者左子樹中的最大元素(沒有右子樹)來替換該被刪除節(jié)點的位置暇唾，因為這兩個節(jié)點都不可能有兩個兒子，這樣在將選取的節(jié)點來填補被刪除節(jié)點的時候辰斋，如果我們選擇的是右邊策州，那么我們只需要保留原刪除節(jié)點的左子樹。重置其右子樹即可宫仗。

平衡二叉樹(AVL樹)

在二叉搜索樹中我們前面也說過够挂，該數(shù)據(jù)結構算法的時間復雜度十分依賴樹的結構。不同排列順序的節(jié)點順序可以形成不同的搜索樹藕夫。將導致不同的深度和平均查找長度(ASL)孽糖。所以一個樹是否左右平衡，是否是一個平衡二叉樹毅贮，對于二叉搜索樹的查找策略將十分重要

概念：

• 任意一棵樹的左右子樹高度差不超過1办悟。

平衡二叉樹的調整

平衡二叉樹的數(shù)據(jù)結構模型固然對我們搜索算法效率提升很高。但是也一定有需要克服的問題滩褥。即如果我們在進行插入刪除的時候把一個原本平衡的二叉樹變得不平衡了怎么辦的問題病蛉。

• 左單旋(RR旋轉)：破壞節(jié)點在被破壞節(jié)點右子樹的右子樹上
• 右單旋(LL旋轉)：破壞節(jié)點在被破壞節(jié)點左子樹的左子樹上
• 左右旋轉(LR旋轉)：破壞節(jié)點在被破壞節(jié)點左子樹的右子樹上
• 右左旋轉(RL旋轉)：破壞節(jié)點在被破壞節(jié)點右子樹的左子樹上
• 提點：需要做左單旋操作那么即提被破壞節(jié)點的左兒子節(jié)點作為父親節(jié)點，然后被破壞節(jié)點作為該節(jié)點的右兒子節(jié)點。如果需要做右單旋操作那么即提被破壞節(jié)點的右兒子節(jié)點作為父親節(jié)點铺然，然后被破壞節(jié)點作為該節(jié)點的左兒子節(jié)點俗孝。

我們在判斷應該做什么旋轉操作的時候應該先考慮好，破壞節(jié)點和被破壞節(jié)點的關系魄健。同時一定要記住它是一顆查找樹赋铝，必須要保證左邊小右邊大這一準則。

遞歸心得

可以看到在樹結構的算法中沽瘦，我們用到了很多遞歸的想法革骨。這里我總結了一些關于遞歸的使用心得。

• 在寫遞歸函數(shù)時其垄，處理掉特殊情況苛蒲。設定好最深層返回條件
• 被遞歸的函數(shù)在調用它時當成既有函數(shù)來使用，不要在意細節(jié)绿满。只要想著臂外，這個被遞歸的函數(shù)能為你做什么即可。然后你只需要調用它并且給他傳遞參數(shù)即可喇颁。
• 多想著遞歸函數(shù)的參數(shù)和返回值是什么漏健。有什么意義
• 要想清楚遞歸函數(shù)的返回值對于上一層遞歸時什么意義。