今天我們從計算機的二元樹數據結構講起，然後談談如何從很多具體的事物或者現像中抽像出具有共性的概念，和提出解決一大堆問題的通用工具。

 

在講述今天的內容之前，先請大家思考這樣一個問題：在我們真實的世界裡，到底是具體的數值重要，還是數值之間相對的大小更重要，或者說相對的次序更重要？

 

我想絕大多數人會這樣說，〝這得看具體情況了，比如體育比賽，成績的相對值就比較重要，因為只要比其他選手得分高或者成績好，就是冠軍，至於你在百米比賽中是 9.9 秒還是 10 秒得到的冠軍，或者足球比賽中是1:0 奪冠，還是5:0大勝，其實關係都不大。但是，在另一些地方，比如錢財方面，擁有一個億，100萬還是 1 萬差別就大多了〞。

 

但是，如果必須讓你在上述問題中做出二選一的回答，並且明確地告訴你，那種〝既 xxx，又xxx 〞的答案統統是零分，你會怎麼辦？如果你在面試中遇到這樣的兩難，我不妨告訴你一個技巧 — 任何選擇都比沒有選擇要好！在生活中也是如此，我們通常無法腳踩兩隻船。

 

具體到上面這個問題，在計算機科學中其實是有明確答案的，那就是相對的大小要比絕對的數量更重要。這一點，計算機科學和數、 理、化都不相同。在數學上，數字是準確的。在物理中，水的冰點有一個確切的溫度，水如果不到0度，是無法結冰的。但在計算機科學裡並不是這樣的。AiphaGo 在和柯潔下棋時， 講解棋局的幾位高手有時會覺得 AIphaGo 下得莫名其妙，因為明明有一步棋可以贏 20 目， 它卻要走一步穩妥的。原因其實很簡單，計算機只看重相對的輸贏。

 

世界上有什麼樣的問題，就有什麼樣的工具，或者說工具的發明是針對問題來的。在數學上要計算數字，人類就發明了算盤。在物理學上，要測量絕對的數值，人類就發明了各種度量長度的尺子、計時的鐘、稱重量的天平和秤等等。在化學上，要測量化學反應的當量， 人類就發明了各種有刻度的量器。在計算機中，由於經常要做的事情是判斷真假、比較大小、排序、挑選最大值這類的操作，而它們在計算機的世界裡又如此重要，當然也就值得為這些事情專門設計一種數據結構，這種數據結構被稱為二元樹。

 

你可以看一眼下面二元樹的圖示，有一個感性認識。

 

 

 

為了便於理解二元樹，我們可以將它和自然界的樹木對應起來。

 

首先，它們都有一個根，二元樹的根就是圖中頂上紅色的那個點。當然，為了將來把二元樹一層層擴展，二元樹的根畫在了最頂端， 而不是下面，你把自然界的大樹轉180度就可以了。

 

其次，從根開始，它們都有分叉，只不過二元樹為了簡單起見，只能有兩個分叉，不能更多，這一點和自然界的樹不同。每一個分叉也有一個自己的根結點，就是圖中藍色的那些點，你可以把它們想像成大樹各級主幹分叉前的部分。當然，你可能會問，如果遇到一個特殊的問題，需要三個分支怎麼辦？在數學上， 兩個分支和 N 個分支是等價的，或者說N個分支的情況可以通過兩個分支來實現。因此，為了簡單起見，也為了更好的通用性，我們只研究二元樹就可以了。

 

最後，我們知道一棵樹的樹權還能再分叉，二元樹也是如此，任何一個枝權都可以再分出兩枝，這個過程可以無限持續下去。

 

我們在生活中，一些組織結構其實就是樹狀結構，比如一個公司的大老闆是根結點，每一個部門的老闆是主幹的根，下面職能部門的總監是枝幹的根，再下面小組的經理是更小枝子的根，最後基層員工是葉子節點。

 

接下來你可能會問，這種怪怪的數據結構在計算機科學中有什麼用處呢？它的用途很多，比如說可以用於排序。

 

我們在前面的課程中介紹了一些排序的算法，無論是高效率的快速排序，還是最直觀的冒泡排序，使用的都是昨天介紹的數組，或者說一個線性的列表。其實，二元樹可以直接完成排序，因為它有一個很好的性質，就是它左右兩個分叉可以和比較大小後的兩種結果自然對應起來。具體講，用二元樹排序的過程只要道循下面兩條規則就可以了：

 

1. 第一，先來的佔據根部，以及靠近頂部層級比較高的位置，後來的放在相對靠下的位置。

 

2. 第二，每當一個分支的根部被佔據之後， 接下來的數字，是和根部的數字進行比較，小的放到左邊分叉中，大的放到右邊分叉中。

 

這樣安排得出來的二元樹，裡面的數字從左到右自然是從小到大排好序的。

 

為了便於理解這個操作的原則，我們不妨打個比方。假如一個公司的組織架構是個二元樹，創始人最先來，因此佔據了頂部位置，隨後來的人是元老，直接匯報給創始人，因此放在了左右兩個位置，你可以理解成他們是事業部的副總裁。當然，我們加了一條規定，如果新人的個兒頭比創始人矮，他就站在左邊，比他高，就站在右邊。再接下來，新來的人一級級地往下放，最後加入公司的只好到下面去當葉子了。但是在這個過程中還遵循另一個原則，矮個子的到左邊，高個子的到右邊。最後，如果把這個公司的人從左往右掃一眼，個兒頭正好越來越高。

 

這個方法的正確性我們就不證明了，我不妨給你看一個具體的例子，你就明白了。比如我們對（3、5、-2、0、6）這組數排序。

 

1. 第一步，把第一個數 3 放到二叉樹的頂端 ( 根部 )。

 

2. 第二步，把第二個數 5 拿來，和樹根部的那個數 3 做對比，由於 5 大於 3，就放在右邊的叉樹中，由於它是右邊叉樹上的第一個數字，因此就佔據了右邊叉樹根部的位置。

 

3. 第三步，把第三個數 -2 拿來，和根部的那個數 3 對比一下，這次 -2 比 3 小了，於是放在左邊。同樣，因為它是左邊第一個數，因此佔了左邊叉樹的根的位置。

 

4. 第四步，把第四個數 0 拿來，和根部的 3 對比一下，因為它比 3 小，所以要放在左邊的叉樹中。但是，左邊叉枝的根部已經被 -2 佔據了，因此 0 需要放到以 -2 為根部的左邊的叉樹下一層的某個位置，至於放在這個叉樹的左邊還是右邊，需要再和 -2 比較一次，來決定它的位置。由於 0 比 -2 大，因此放到了 -2 的右邊。

 

5. 第五步，把第五個，也就是最後一個數6 拿來，先和根部的3比較一下，發現它比3 大，因此放在右邊的叉樹中，但是右邊的叉樹根部已經被5佔據，沒有地方了，於是和右叉樹的根結點5比較了一下，發現比5大，因此要放在右叉樹的右邊。

 

好了到此為止，所有的數字都放進了這裸二叉樹中。你可以看一眼下面的這張圖，它是插入了所有數字後的結果。

 

 

 

那麼接下來呢？接下來你只要把二叉樹中的數字從左到右取出來即可，從上面的過程我們可以看到，最左邊的是 -2，然後是 0，中間根部是 3，往右邊是 5 和 6。

 

這樣一來，把一堆數字按照一定的規則放到二元樹中，再拿出來，它們就有序了，神奇吧？當然，在計算機中這些數據一進一出需要時間，這個時間和快速排序是同一個量級。

 

二元樹這種數據結構的用途遠不止排序， 我舉了排序的例子，只是為了說明它有用而已。在現實的工程中，二元樹可以做很多事情，比如快速查找到某一個數值。

 

另外，由於網站的目錄結構也是樹狀的（當然它們有N個分叉），因此，針對二叉樹的各種算法，稍加改變，就可以用於互聯網。比如，我們找到一個網站後，要下載一個網站裡面所有的網頁，就會用到二元樹中的一種遍曆算法。

 

類似地，一個組織的管理結構也和二元樹類似。也就是說二元樹雖然是一種抽象的東西，在自然界中並不存在，但是它卻濃縮了自然界很多事物的共性，那就是分叉、層層遞進和有序。而針對這些共性，科學家們又總結出一些具有普遍性的算法，能夠回過頭來，應用到各種實際問題中。

 

在Google這樣的公司面試時，不會考大家教科書上的那些基本內容，而會考如何利用那些工具 ( 包括數據結構 )，解決一些實際問題。如果候選人能答得上來，說明那些書上的內容他已經掌握了。事實上，我們前面提到的如何找到周圍最近的幾個加油站，這個問題就可以用到二叉樹的一些算法解決。

 

今天的內容有點抽象，不過這是這週，也是這門課到目前為止最難的內容了，如果你堅持聽完了今天的內容，一定要恭喜你，因為你已經上了一些計算機系大二的課了。

 

為了便於你進一步理解，我把今天的內容總結如下：

 

1. 世界上的工具常常是根據所遇到的問題而發明的，有什麼樣的問題，就有什麼樣的工具。

 

2. 在計算機科學中，數據的相對大小比絕對的數值重要，出於很多數據比大小的需求以及其他一些需求，就產生了一個抽象的數據結構一一二元樹。

 

3. 和很多抽象的工具一樣，二元樹其實能在現實生活中找到很多對應。除了比大小之外，我們的組織架構，我們的文件目錄，網站的鏈接層次，以及我們明天要講到的錦標賽， 都能對應到二元樹中。

 

4. 所有能夠對應到二元樹的問題，都有一些共性，解決它們之間問題的方法是可以觸類旁通的。這就是我們要學習理論的目的，因為我們希望它能夠在很多場合應用，而不只是用一次，記住第四條很重要。

 

有了今天的鋪墊，明天我們就用二元樹這個工具，講解高盛和 Google 的面試題。

 

 

 

來源：《吳軍-從二元樹數據結構到對具體問題共性的抽象化》