1、樹的基本概念

1.1樹的定義

樹是n個(gè)結(jié)點(diǎn)的有限集。

若n=0，稱為空樹；若n>0稱為非空樹，非空樹有且僅有一個(gè)稱之為根的結(jié)點(diǎn)。

除根結(jié)點(diǎn)以外的其余結(jié)點(diǎn)可分成m個(gè)互不相交的有限集T1,T2,......Tm,每個(gè)有限集合本身又是一棵樹，并且稱為根的子樹。

我們可以根據(jù)下面這張圖來(lái)理解。

根結(jié)點(diǎn)：非空樹中無(wú)前驅(qū)結(jié)點(diǎn)的結(jié)點(diǎn)。圖中A就是根結(jié)點(diǎn)

結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹。例如A結(jié)點(diǎn)擁有三棵子樹，所以它的度為3

深度：樹種結(jié)點(diǎn)的最大層次，圖中的樹深度為4

接下來(lái)我們介紹各個(gè)結(jié)點(diǎn)之間的關(guān)系：

葉子：也是終端結(jié)點(diǎn)，即沒(méi)有子樹的結(jié)點(diǎn)

孩子與雙親：一個(gè)結(jié)點(diǎn)伸出的子樹之間的關(guān)系

堂/兄弟：同一層次結(jié)點(diǎn)的關(guān)系

（樹的概念可以類比族譜，這樣更容易理解）

1.2樹的基本術(shù)語(yǔ)

樹可以分成有序樹和無(wú)序樹：

有序樹指的是結(jié)點(diǎn)各子樹從左至右有序不能互換（例如：二叉樹）

無(wú)序樹中各結(jié)點(diǎn)子樹可以互換位置。

學(xué)習(xí)了樹的基本知識(shí)，下面就引出森林的概念：

如圖所示，這是一個(gè)再正常不過(guò)的樹，A是根結(jié)點(diǎn)，T1,T2,T3是它的子樹。這時(shí)如果我們把A結(jié)點(diǎn)和B,C,D結(jié)點(diǎn)的連接斷開，變成下面這個(gè)樣子，就稱為森林：

此時(shí)，B,C,D是三棵相互獨(dú)立的樹。

這就是森林，即m棵互不相交的樹的集合。

1.3樹的其他表示方式

樹所包含的邏輯結(jié)構(gòu)還可以用廣義表，嵌套集合等形式表示，大家根據(jù)圖片就可理解。

2、二叉樹的基本知識(shí)

2.1二叉樹的概念

二叉樹是一種特殊的樹，它只有左子樹和右子樹。其基本特點(diǎn)如下：

1、結(jié)點(diǎn)的度小于等于2

2、是有序樹（子樹有序，不能顛倒）

我們來(lái)看一個(gè)例子：具有三個(gè)結(jié)點(diǎn)的二叉樹可能有幾種不同形態(tài)，普通樹呢？

二叉樹由于子樹有序不能顛倒，所以共有5種形態(tài)：

而普通的樹是無(wú)序的，只用考慮層次，顧只有兩種：

?

?2.2二叉樹的性質(zhì)

我們首先介紹兩種特殊的二叉樹

1、滿二叉樹：

如圖就是一個(gè)滿二叉樹，它具有以下特點(diǎn)：

每層結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)（每層都滿）

葉子結(jié)點(diǎn)全部在最底層

每一結(jié)點(diǎn)位置都有元素

綜上，我們可以很輕松地給出結(jié)論，一棵深度為k的滿二叉樹，它的共有個(gè)結(jié)點(diǎn)。

2、完全二叉樹：

我們?cè)O(shè)完全二叉樹有k層，當(dāng)k-1層是滿二叉樹，只有最后一層葉子不滿，且全部集中在左邊時(shí)即稱為完全二叉樹，如圖所示：

那么我們?cè)賮?lái)辨析以下下面呢幾棵樹哪個(gè)是完全二叉樹：

我們給出結(jié)果，圖1是滿二叉樹，圖三是完全二叉樹，其余的都不是。

下面我們介紹二叉樹最重要的4條性質(zhì)：

性質(zhì)1：在二叉樹的第i層至多有個(gè)結(jié)點(diǎn)

我們可以這樣理解：

性質(zhì)2：深度為k的二叉樹至多有?個(gè)結(jié)點(diǎn)

同樣，這是一個(gè)等比數(shù)列求和的問(wèn)題，第一行為，第二行，如此類推，最終求和結(jié)果就是?

性質(zhì)3：對(duì)任意一棵二叉樹，如果終端結(jié)點(diǎn)數(shù)（葉子結(jié)點(diǎn)）為0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1

性質(zhì)4：具有n個(gè)節(jié)點(diǎn)的完全二叉樹深度為?log2(n+1)?或?log2n?+1

也可以這樣理解-1<n<-1