http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/9.4.png" alt="picture9.4" /> http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/9.5.png" alt="picture9.5" />

上面這個例子中左邊的是一棵樹，而右邊的是一個圖。因?yàn)樽筮叺臎]有回路，而右邊的存在 1->2->5->3->1 這樣的回路。

正是因?yàn)闃溆兄安话芈贰边@個特點(diǎn)，所以樹就被賦予了很多特性。
一棵樹中的任意兩個結(jié)點(diǎn)有且僅有唯一的一條路徑連通。
一棵樹如果有 n 個結(jié)點(diǎn)，那么它一定恰好有 n-1 條邊。

在一棵樹中加一條邊將會構(gòu)成一個回路。樹這個特殊的數(shù)據(jù)結(jié)構(gòu)在哪里會用到呢？比如足球世界杯的晉級圖，家族的族譜圖、公司的組織結(jié)構(gòu)圖、書的目錄、我們用的操作系統(tǒng) Windows、Liunx 或者 Mac 中的“目錄（文件夾）”都是一棵樹。下面就是“啊哈 C”這個軟件的目錄結(jié)構(gòu)。


    C:\啊哈C
    ├─codes
    ├─core
    │ ├─bin
    │ ├─include
    │ │ ├─ddk
    │ │ ├─gdb
    │ │ ├─gdiplus
    │ │ ├─GL
    │ │ └─sys
    │ ├─lib
    │ │ └─gcc
    │ │ └─mingw32
    │ │ └─4.7.1
    │ │ ├─finclude
    │ │ ├─include
    │ │ │ └─ssp
    │ │ ├─include-fixed
    │ │ └─install-tools
    │ │ └─include
    │ ├─libexec
    │ │ └─gcc
    │ │ └─mingw32
    │ │ └─4.7.1
    │ │ └─install-tools
    │ └─mingw32
    │ ├─bin
    │ └─lib
    │ └─ldscripts
    └─skin

假如現(xiàn)在正處于 libexec 文件夾下，需要到 gdiplus 文件夾下。你必須先“向上”回到上層文件夾 core，再進(jìn)入 include 文件夾，最后才能進(jìn)入 gdiplus 文件夾。因?yàn)橐豢脴渲械娜我鈨蓚€結(jié)點(diǎn)（這里就是文件夾）有且僅有唯一的一條路徑連通。

為了之后講解的方便，我們這里對樹進(jìn)行一些定義。

首先，樹是指任意兩個結(jié)點(diǎn)間有且只有一條路徑的無向圖。或者說，只要是沒有回路的連通無向圖就是樹。

喜歡思考的同學(xué)可能會發(fā)現(xiàn)同一棵樹可以有多種形態(tài)，比如下面這個兩棵樹。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/9.6.png" alt="picture9.6" /> http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/9.7.png" alt="picture9.7" />

為了確定一棵樹的形態(tài)，在一棵樹中可以指定一個特殊的結(jié)點(diǎn)——根。我們在對一棵樹進(jìn)行討論的時候，將樹中的每個點(diǎn)稱為結(jié)點(diǎn)，有的書中也稱為節(jié)點(diǎn)。有一個根的樹叫做有根樹（哎，這不是廢話嘛）。比如上方左邊這棵樹的樹根是 1 號結(jié)點(diǎn)，右邊這棵樹的樹根是 3 號結(jié)點(diǎn)。

根又叫做根結(jié)點(diǎn)，一棵樹有且只有一個根結(jié)點(diǎn)。根結(jié)點(diǎn)有時候也稱為祖先。既然有祖先，理所當(dāng)然就有父親和兒子。比如上圖右邊這棵樹中 3 號結(jié)點(diǎn)是 1、6 和 7 號結(jié)點(diǎn)的父親，1、6 和 7 號結(jié)點(diǎn)是 3 號結(jié)點(diǎn)的兒子。同時 1 號結(jié)點(diǎn)又是 2 號結(jié)點(diǎn)的父親，2 號結(jié)點(diǎn)是 1 號結(jié)點(diǎn)的兒子，2 號結(jié)點(diǎn)與 4、5 號結(jié)點(diǎn)關(guān)系也顯而易見了。

父親結(jié)點(diǎn)簡稱為父結(jié)點(diǎn)，兒子結(jié)點(diǎn)簡稱為子結(jié)點(diǎn)。2 號結(jié)點(diǎn)既是父結(jié)點(diǎn)也是子結(jié)點(diǎn)，它是 1 號結(jié)點(diǎn)的子結(jié)點(diǎn)，同時也是 4 和 5 號結(jié)點(diǎn)的父結(jié)點(diǎn)。另外如果一個結(jié)點(diǎn)沒有子結(jié)點(diǎn)（即沒有兒子）那么這個結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，例如 4、5、6 和 7 號結(jié)點(diǎn)都是葉結(jié)點(diǎn)。沒有父結(jié)點(diǎn)（即沒有父親）的結(jié)點(diǎn)稱為根結(jié)點(diǎn)（祖先）。如果一個結(jié)點(diǎn)既不是根結(jié)點(diǎn)也不是葉結(jié)點(diǎn)則稱為內(nèi)部結(jié)點(diǎn)。最后每個結(jié)點(diǎn)還有深度，比如 5 號結(jié)點(diǎn)的深度是 4。哎，終于啰嗦完了，寫的我汗都流出來了，沒有理解的請看下面這幅插圖吧。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/9.8.png" alt="picture9.8" />

說了這么多你可能都沒有感受到樹究竟有什么好處。不要著急，請看下回——二叉樹。

【啊哈！算法】算法 9：開啟“樹”之旅
 http://ahalei.blog.51cto.com/4767671/1403823

上一篇：算法 8：巧妙的鄰接表（數(shù)組實(shí)現(xiàn)）下一篇：最快最簡單的排序——桶排序