數據結構（五）：二叉樹

樹在日常生活中是廣泛存在的，例如家族的族譜，各種公司部門結構圖等。在計算機里，樹更是無處不在，你平時接觸到的堆，紅黑樹，二叉查找樹，並查集，線段樹，後綴樹，樹狀數組都是樹。資料庫中索引是B+樹，編譯器中的語法樹也是一種樹，操作系統中的文件系統大多設計成樹的結構……還有太多太多了。所以說，樹這種數據結構是程序的靈魂，是程序的根基，是電，是光，是……總之，能不能把樹這種數據結構玩得溜，可以說是做程序員的第一道坎。

樹這種數據結構，最經典，最基礎的實例就是二叉樹，掌握好二叉樹是學習其他高級數據結構的基石，所以，請大家一定要反覆看這一節，反覆寫程序。真的，二叉樹可能比你想像的還要重要得多。

JDK中的TreeMap是一種用樹實現的Map，但是，它的實現是紅黑樹。雖然它本質上仍然是一棵二叉樹，但卻無論如何都得算是高級數據結構了（我敢打賭，90%以上的程序員無法完整地寫出紅黑樹的實現，不要說刪除節點，恐怕光是插入就寫不全）。所以，我強烈建議大家在完全地掌握了二叉樹和AVL樹之前，先不要急著去翻JDK的源代碼。

二叉樹

二叉樹是一種樹型結構，它的特點是每個結點至多只有兩棵子樹，並且，二叉樹的子樹有左右之分，其次序不能任意顛倒。

先上代碼，二叉樹的結點定義：

class Node {n public Object data;n public Node left;n public Node right;n}n

可以看到，我們除了定義了一個結點的左孩子和右孩子，還定義一個data變數用於存儲數據。我們寫一段代碼，來實際地創建一棵二叉樹：

public class Main {n public static void main(String args[]) {n Node a = new Node(Integer.valueOf(1));n Node b = new Node(Integer.valueOf(2));n Node c = new Node(Integer.valueOf(3));n a.left = b;n a.right = c;n }n}nnclass Node {n public Object data;n public Node left;n public Node right;nn public Node(Object d) {n this.data = d;n }n}n

我們通過這種方式，手動地創建了一個二叉樹，這個二叉樹，如果使用圖畫出來，就是以下的樣子：

我們稱 1 是父節點，2 是左孩子結點，3 是右孩子結點。如果一個節點沒有子結點，例如圖中的 2 和 3 ，那這個節點也是葉子節點。如果一個結點有子結點，也可以稱其為內部結點，或者是非葉子結點。

樹的層次是這樣定義的，把樹按照上圖所示的情況畫出來，1 位於第一層，2 和 3 位於第二層。樹中結點的最大層次稱為樹的高度，2 和 3 位於第二層，所以這棵樹的高度就是 2。再練習一下，下面這幅圖中，樹有多少層？每層幾個結點？樹的高度是多少？共有多少個葉子結點？多少個非葉子結點？

答案是：3層，第一層一個結點是 1， 第二層兩個結點是2 和 3，第三層兩個結點 4 和 5；樹中結點的最大層數是3，所以樹的高度就是3；共有三個葉子結點，分別是2， 4， 5；兩個非葉結點，1和3。你答對了嗎？

二叉查找樹

二叉查找樹的規則是，對於樹中的任意一個結點，都滿足，它的左孩子上的所有結點的值都比該結點小，而它的右孩子上的所有結點的值都比該結點大。與該結點值相同的的結點可以放在左孩子上，也可以放在右孩子上，這個可以根據實際情況靈活實現。

根據這個定義，二叉查找樹的插入過程就是遞進地判斷待插入數據與樹中結點值的大小關係，找到待插入數據應該出現的位置。

如果待插入數據比根結點的數據小，就去檢查根結點的左孩子。如果左孩子不為空，就繼續向下檢查，如果左孩子為空，就說明已經找到應該插入數據的位置了。向右的情況則與向左的情況互為鏡像，只是條件判斷的符號換了一下而已。

class BinarySearchTree<T extends Comparable<T>> {n public Node root;nn public boolean insert(T i) {n if (root == null) {n root = new Node(i);n return true;n }nn Node current = root;n while (true) {n // 如果 i 比當前結點的值小n if (i.compareTo((T) current.data) < 0) {n if (current.left != null) {n current = current.left;n } else {n current.left = new Node(i);n break;n }n } else {n if (current.right != null)n current = current.right;n else {n current.right = new Node(i);n break;n }n }n }n return true;n }n}n

在二叉查找樹中找一個數據的思路與插入數據的思路很相似，唯一的不同之處是遇到空指針就是查找失敗，說明待查找數據沒在樹中。程序不再列出，請讀者自行實現。

好了。今天就講這麼多吧。今天的講解少，作業多，大家一定要動起手來，多看多想多寫。爭取把今天講的概念全部牢牢記住。今天的作業：

1. 為BinarySearchTree這個類添加一個方法：

public boolean contains(T t);n

檢查一個數據是否在BST中，如果在，則返回true，否則返回 false。多寫幾個例子，測試一下你的代碼對不對。

2. 以不同的順序往BST中插入數字，然後在紙上畫一下，看看BST會變成什麼樣？舉個例子，如果以(3, 2, 1, 5, 4, 6)的順序插入的話，就會變成這個樣子：

尤其，一定要畫一下(1, 2, 3, 4, 5, 6) 和 (6, 5, 4, 3, 2, 1)的圖。用紙畫，小密圈的同學，交作業的時候可以使用手機拍照，用QQ傳給我。

3. 閱讀一下這篇文章：談遞歸時，我們在談什麼。實現BST的前序遍歷。

上一節課：Java中的容器

下一節課：數據結構（六）：二叉樹的遍歷

目錄：課程目錄

=========== 廣告時間 ====================

課程內容都會發在知乎專欄里，不加小密圈也可以看。小密圈的作用，除了發布作業的答案，還有作業的講解。小密圈是付費的，但是收費剛好是一頓必勝客套餐。持繼一年的課程，只需要請我吃一頓飯，怎麼看也是划算的:)

https://wx.xiaomiquan.com/mweb/views/joingroup/join_group.html?group_id=2214254521&secret=3v8pextw4kz53tpbns53ewxg1846d6hf&extra=222990c1366583bf0f1db69e06ad15575f6e6010196e1abb057aec1164fe7d49 (二維碼自動識別)