二叉樹
8.1 為什么使用二叉樹
- 因為它結合了數組和鏈表的優(yōu)點，查找的速度和數組一樣快院仿，增刪的速度和鏈表一樣快。
8.1.1 在有序數組中插入數據項太慢
- 查找數據項使用二分法勺届，需要O(logN)時間
- 插入或者刪除需要移動一半的數據項（N/2次移動）
8.1.2 在鏈表中查找太慢
- 鏈表中插入和刪除極快，時間復雜度為O(1)
- 鏈表中查找要從頭開始遍歷娶耍，并且逐個比較免姿，費時為O(N)
- 鏈表不支持隨機訪問
8.1.3 用樹解決問題
要是能有一種數據結構，既能像鏈表那樣快速的插入和刪除榕酒，又能像有序數組那樣快速查找胚膊，那樣就好了故俐。樹實現了這些特點，成為最有意思的數據結構之一紊婉。
8.1.4 樹是什么
- 本章著重講解的是一種特殊的的樹——二叉樹
- 先從廣義上討論一下樹：樹由邊連接的節(jié)點而構成
- 節(jié)點：代表實體药版，或者說是對象
- 邊：代表路徑，或者說是引用
- 二叉樹：每個節(jié)點最多有兩個子節(jié)點
8.2 樹的術語
8.2.1 路徑
- 從一個節(jié)點走到另一個節(jié)點喻犁，所經過的節(jié)點的順序排列就稱為“路徑”槽片。
8.2.2 根
- 樹頂端的節(jié)點稱為“根”
- 從根到任意節(jié)點有且僅有一條路徑
8.2.3 父節(jié)點
- 每個節(jié)點向上只有一條路徑
8.2.4 子節(jié)點
- 每個節(jié)點向下可能有多條路徑
8.2.5 葉節(jié)點
- 沒有子節(jié)點的稱為葉節(jié)點
8.2.6 子樹
- 一個節(jié)點所有的后代
8.2.7 訪問
- 查看節(jié)點的數據
8.2.8 遍歷
- 遵循某種特定的順序訪問樹中所有節(jié)點，例如升序
8.2.9 層
- 根節(jié)點是第0層
8.2.10 關鍵字
- 對象中通常會有一個數據域被指定為關鍵字值
- 將關鍵字顯示在樹節(jié)點的圓圈中
8.2.11 二叉樹
- 最多只有兩個子節(jié)點的樹稱為二叉樹
- 二叉搜索樹：左子節(jié)點的值小于父節(jié)點株汉，右子節(jié)點的值大于或等于父節(jié)點
8.3 一個類比
- 計算機系統(tǒng)中筐乳，人們常遇到的樹是分級文件結構
- 目錄對應著子節(jié)點，文件對應著葉節(jié)點
8.4 二叉搜索樹如何工作
- 對于一個給定關鍵字的節(jié)點乔妈，在一顆普通的二叉樹中如何插入，刪除氓皱，遍歷路召。
8.4.1 BinaryTree專題applet
- 非平衡樹
- 大部分節(jié)點在根的一邊
- 它的個別子樹依然可能是非平衡樹
- 非平衡樹源自于有序的插入
8.4.2 用Java代碼表示樹
- 可以用數組或者鏈表實現
8.5 查找節(jié)點
- 根據關鍵值查找節(jié)點是樹的主要操作中最簡單的，所以本章從查找開始學習波材。
8.5.1 使用專題applet查找一個節(jié)點
8.5.2 查找節(jié)點的Java代碼
8.5.3 樹的效率
8.6 插入一個節(jié)點
- 要插入節(jié)點股淡，必須先找到插入的地方，這很像要找一個不存在的節(jié)點的過程廷区。
8.6.1 使用專題applet插入一個節(jié)點
8.6.2 插入一個節(jié)點的Java代碼
- 記錄目標的父節(jié)點：parent
8.7 遍歷樹
- 遍歷樹的意思是根據一種特定順序訪問樹的每一個節(jié)點唯灵。
8.7.1 中序遍歷
- 中序遍歷二叉搜索樹會使所有的節(jié)點按關鍵字值升序被訪問到
8.7.2 遍歷的Java代碼
8.7.3 遍歷一顆三節(jié)點樹
8.7.4 用專題applet遍歷
8.7.5 前序和后序遍歷
- 前綴表達式
- 后綴表達式
8.8 查找最大值和最小值
順便說一下，在二叉搜索樹中得到最大值和最小值是輕而易舉的事情隙轻。
- 最小值：從根開始埠帕，往左走，找到一個沒有左子節(jié)點的節(jié)點玖绿。
- 最大值：從根開始敛瓷，往右走，找到一個沒有右子節(jié)點的節(jié)點斑匪。
8.9 刪除節(jié)點
- 刪除節(jié)點是二叉搜索樹常用的一般操作中最復雜的呐籽。
8.9.1 情況1：刪除沒有子節(jié)點的節(jié)點
image.png
- 將指向該節(jié)點的引用改為null
8.9.2 情況2：刪除有一個子節(jié)點的節(jié)點
image.png
- 父節(jié)點直接指向子樹的根
- 注意應用引用使得移動整棵子樹非常容易，實際上蚀瘸，它們只是概念上的移動狡蝶，并沒有真實的移動。
8.9.3 情況3：刪除有兩個子節(jié)點的節(jié)點
-
對于有兩個子節(jié)點的簡單情況：用中序后繼替代
image.png -
后繼是右子節(jié)點：右子節(jié)點子樹上移
image.png
-
后繼是右子節(jié)點的左子后代
image.png
8.10 二叉樹的效率
- 樹的大部分操作都需要從上到下一層一層地查找某個節(jié)點
- 樹對所有常用的數據存儲操作都有很高的效率
- 遍歷不如其他操作快
8.11 用數組表示樹
- 按從左到右的順序存儲樹的每一層贮勃，下標為0的節(jié)點是根
- 樹中的每個位置贪惹，無論是否存在節(jié)點，都對應數組中的一個位置
- 大多數情況下用數組表示樹不是很有效率
8.12 重復關鍵字
- 有重復關鍵字的節(jié)點都插到與它關鍵字相同的節(jié)點的右子節(jié)點
8.13 完整的tree.java程序
8.14 哈夫曼（Huffman）編碼
- 二叉樹并不全是搜索樹衙猪，很多二叉樹用于其他的情況
8.14.1 字符編碼
- 計算機里每個字符在沒有壓縮的文本文件中由一個字節(jié)（ASCII碼）馍乙，或兩個字節(jié)（Unicode碼）
- 有很多壓縮數據的方法布近。對文本來說，最常用的方法是減少表示最常用字符的位數量
- 每個代碼都不能是其他代碼的前綴
8.14.2 用哈夫曼樹解碼
- 哈夫曼樹用于壓縮文本
- 從根開始丝格，如果遇到0就向左走撑瞧，遇到1就向右走
