樹(shù)與二叉樹(shù)

?

1.樹(shù)

1.樹(shù)形結(jié)構(gòu)(非線性結(jié)構(gòu))

結(jié)點(diǎn)之間有分支，具有層次關(guān)系

樹(shù)的定義：

樹(shù)(tree)是n(n≥0)個(gè)有限集。

若n = 0，則稱為空樹(shù)；

若n > 0，則它滿足如下兩個(gè)條件：

1. 有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；

2. 其余結(jié)點(diǎn)可分為m(m≥0)個(gè)互不相交的有限集T1,T2,T3,.....,Tm,其中每一個(gè)集合本身又是一棵樹(shù)，并稱為根的子樹(shù)(SubTree)；

??

樹(shù)的其他表示方法：

嵌套集合

?

廣義表

?

凹入表式

?

?

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

結(jié)點(diǎn)：數(shù)據(jù)元素以及指向子樹(shù)的分支。

根節(jié)點(diǎn)：非空樹(shù)中無(wú)前驅(qū)結(jié)點(diǎn)的結(jié)點(diǎn)

結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹(shù)數(shù)

樹(shù)的度：樹(shù)內(nèi)各節(jié)點(diǎn)的度的最大值

非終端結(jié)點(diǎn)：根結(jié)點(diǎn)以外的分支結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)

葉結(jié)點(diǎn)：終端結(jié)點(diǎn)

結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子，該結(jié)點(diǎn)稱為孩子的雙親

?

?

堂兄弟結(jié)點(diǎn)：雙親在同一層的結(jié)點(diǎn)

結(jié)點(diǎn)的祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。

結(jié)點(diǎn)的子孫：以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)。

有序樹(shù)：樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左至右有次序（最左邊的為第一個(gè)孩子）。

?

?

森林：是m(m≥0)棵互不相交的樹(shù)的集合。

把根結(jié)點(diǎn)刪除樹(shù)就變成了森林。

一棵樹(shù)可以看成是一個(gè)特殊的森林。

給森林中的各子樹(shù)加上一個(gè)雙親結(jié)點(diǎn)，森林就變成了樹(shù)。

??

3.樹(shù)結(jié)構(gòu)和線性結(jié)構(gòu)的比較

2.二叉樹(shù)

二叉樹(shù)的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；

可以證明，所有樹(shù)都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹(shù)，不失一般性。

普通樹(shù)（多叉樹(shù)）若不轉(zhuǎn)化為二叉樹(shù)，則運(yùn)算很難實(shí)現(xiàn)。

二叉樹(shù)在樹(shù)結(jié)構(gòu)的應(yīng)用中起著非常重要的作用，因?yàn)閷?duì)二叉的許多操作算法簡(jiǎn)單，而任何樹(shù)都可以與二叉樹(shù)相互轉(zhuǎn)換，這樣就解決了樹(shù)的存儲(chǔ)結(jié)構(gòu)及其運(yùn)算中存在的復(fù)雜性。

1.二叉樹(shù)的定義

二叉樹(shù)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集，它或者是空集(n=0)，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分別稱作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

特點(diǎn)：

1. 每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子（二叉樹(shù)中不存在大于2的結(jié)點(diǎn)）。

2. 子樹(shù)有左右之分，其次序不能顛倒。

3. 二叉樹(shù)可以是空集合，根可以有空的左子樹(shù)或空的右子樹(shù)。

注意：二叉樹(shù)不是樹(shù)的特殊情況，他們是兩個(gè)不同的概念。

二叉樹(shù)結(jié)點(diǎn)的子樹(shù)要區(qū)分左子樹(shù)和右子樹(shù)，即使只有一棵子樹(shù)也要進(jìn)行區(qū)分，說(shuō)明它是左子樹(shù)，還是右子樹(shù)。

樹(shù)當(dāng)結(jié)點(diǎn)只有一個(gè)孩子時(shí)，就無(wú)須區(qū)分它是左還是右的次序。因此二者是不同的。這是二叉樹(shù)與樹(shù)的最主要的差別。

(也就是二叉樹(shù)每個(gè)結(jié)點(diǎn)位置或者說(shuō)次序都是固定的，可以是空，但是不可以說(shuō)它沒(méi)有位置，而樹(shù)的結(jié)點(diǎn)位置是相對(duì)于別的結(jié)點(diǎn)來(lái)說(shuō)的，沒(méi)有別的結(jié)點(diǎn)時(shí)，它就無(wú)所謂左右了)

思考：

?

注意：雖然二叉樹(shù)與樹(shù)概念不同，但有關(guān)樹(shù)的基本術(shù)語(yǔ)對(duì)二叉樹(shù)都適用。

3.應(yīng)用案例

1.數(shù)據(jù)壓縮問(wèn)題

將數(shù)據(jù)文件轉(zhuǎn)換成由0、1組成的二進(jìn)制串，稱之為編碼。

2.利用二叉樹(shù)求解表達(dá)式的值

以二叉樹(shù)表示表達(dá)式的遞歸定義如下：

1. 若表達(dá)式為數(shù)或簡(jiǎn)單變量，則相應(yīng)二叉樹(shù)中僅有一個(gè)根結(jié)點(diǎn)，其數(shù)據(jù)域存放該表達(dá)式信息；

2. 若表達(dá)式為“第一操作數(shù)運(yùn)算符第二操作數(shù)”的形式，則相應(yīng)的二叉樹(shù)中以左子樹(shù)表示第一操作數(shù)，右子樹(shù)表示第二操作數(shù)，根結(jié)點(diǎn)的數(shù)據(jù)域存放運(yùn)算符(若為一元運(yùn)算符，則左子樹(shù)為空)，其中，操作數(shù)本身又為表達(dá)式。

?

?

4.抽象數(shù)據(jù)類型定義

1.二叉樹(shù)的抽象數(shù)據(jù)類型定義

類型定義

ADT BinaryTree
{
 ? ?數(shù)據(jù)對(duì)象D:D是具有相同特性的數(shù)據(jù)元素的集合
 ? ?數(shù)據(jù)關(guān)系R:若D＝?，則R=?中;
             若D≠Φ，則R={H};H是如下二元關(guān)系：
            ①root唯一//關(guān)于根的說(shuō)明
            ②Dj∩Dk=?//關(guān)于子樹(shù)不相交的說(shuō)明
            ③//關(guān)于數(shù)據(jù)元素的說(shuō)明
            ④//關(guān)于左子樹(shù)和右子樹(shù)的說(shuō)明
 ? ?基本操作P:
}ADT BinaryTree;

具體形式

CreateBiTree(&T,definition)
{
 ? ?初始條件:definition給出二叉樹(shù)T的定義;
 ? ?操作結(jié)果:按definition構(gòu)造二叉樹(shù);
}
?
PreOrderTraverse(T)
{
 ? ?初始條件:二叉樹(shù)T存在;
 ? ?操作結(jié)果:先序遍歷T，對(duì)每個(gè)節(jié)點(diǎn)訪問(wèn)一次;
}
?
InOrderTraverse(T)
{
 ? ?初始條件:二叉樹(shù)T存在;
 ? ?操作結(jié)果:中序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)訪問(wèn)一次;
}
?
PostOrderTraverse(T)
{
 ? ?初始條件:二叉樹(shù)T存在;
 ? ?操作結(jié)果:后序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)訪問(wèn)一次;
}

2.二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)

性質(zhì)1：在二叉樹(shù)的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)(i≥1)。

證：采用歸納法證明此性質(zhì)。 歸納基：當(dāng)i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，2^(i-1)=2=1，命題成立。 歸納假設(shè)：設(shè)對(duì)所有的(1 ≤ j < i)，命題成立，即第j層上至多有2^(j-1)個(gè)結(jié)點(diǎn)。那么可以證明 j = i時(shí)命題也成立。

性質(zhì)2：深度為k的二叉樹(shù)至多有2^(k) - 1個(gè)結(jié)點(diǎn)(k≥1)。

證：由性質(zhì)1可知，深度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為：

推論：深度為k時(shí)至少有k個(gè)結(jié)點(diǎn)。

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

?

?

5.特殊形式的二叉樹(shù)

1.滿二叉樹(shù)

一棵深度為k且有2^k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。

??

特點(diǎn)：

1. 每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)（即每層都滿）

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

3. 對(duì)滿二叉樹(shù)結(jié)點(diǎn)位置進(jìn)行編號(hào)

4. 編號(hào)規(guī)則：從根結(jié)點(diǎn)開(kāi)始，自上而下，自左而右。

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

滿二叉樹(shù)在同樣深度的二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)最多

滿二叉樹(shù)在同樣深度的二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)最多

2.完全二叉樹(shù)

深度為k的具有個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)為1~n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹(shù)。

注意：在滿二叉樹(shù)中，從最后一個(gè)結(jié)點(diǎn)開(kāi)始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹(shù)，一定是連續(xù)的去掉?。?！

特點(diǎn)：

1. 葉子只可能分布在層次最大的兩層上。

2. 對(duì)任一結(jié)點(diǎn)，如果其右子樹(shù)的最大層次為i，則其左子樹(shù)的最大層次必為i或i+1。

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[Iog2n]+1。

性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)（深度為[Iog2n]+1點(diǎn)按層序編號(hào)（從第1層到第[Iog2n]+1層，每層從左到右），則對(duì)任一結(jié)點(diǎn)i(1≤i≤n)，有：

1. 如果i = 1，則結(jié)點(diǎn) i 是二叉樹(shù)的根，無(wú)雙親；如果i>1,則其雙親是結(jié)點(diǎn)[ i / 2 ]。

2. 如果2i>n,則結(jié)點(diǎn)為葉子結(jié)點(diǎn)，無(wú)左孩子；否則，其左孩子是結(jié)點(diǎn)2ⅰ。

3. 如果2i+1>n,則結(jié)點(diǎn)無(wú)右孩子；否則，其右孩子是結(jié)點(diǎn)2i+1。

性質(zhì)5表明了完全二叉樹(shù)中雙親結(jié)點(diǎn)編號(hào)與孩子結(jié)點(diǎn)編號(hào)之間的關(guān)系

6.二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)

1.二叉樹(shù)的順序存儲(chǔ)

實(shí)現(xiàn)：按滿二叉樹(shù)的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹(shù)中的數(shù)據(jù)元素。

?

//二叉樹(shù)的順序存儲(chǔ)
#define MAXTSIZE 100
Typedef TElemType SqBiTree[MAXSTIZE]
SqBiTree bt;

注意：普通二叉樹(shù)也能按照這樣的存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，為空的部分預(yù)留位置出來(lái)。

二叉樹(shù)的順序存儲(chǔ)缺點(diǎn)：最壞情況：深度為②的且只有k個(gè)結(jié)點(diǎn)的單支樹(shù)需要長(zhǎng)度為2^k - 1的一維數(shù)組。

?

?

特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中,浪費(fèi)空間，適于存滿二叉樹(shù)和完全二叉樹(shù)

2.二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)

二叉樹(shù)結(jié)點(diǎn)的特點(diǎn)：有兩個(gè)孩子

存儲(chǔ)方式：

?

typedef struct BiNode
{
 ? ?TElemType data;
 ? ?struct BiNode *lchild, *rchild;//左右孩子指針
}BiNode,*BiTree;

分析空指針域：

在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域

分析：必有2個(gè)鏈域。除根結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只會(huì)有 n - 1個(gè)結(jié)點(diǎn)的鏈域存放指針指向非空子女結(jié)點(diǎn)。

空指針數(shù)目 = 2n - (n - 1) = n + 1

??

3.三叉鏈表

?

typedef struct TriTNode
{
 ? ?TelemType data;
 ? ?struct TriTNode *lchild,*parent,*rchild;
}TriTNode, *TriTree;

遍歷二叉樹(shù)

遍歷定義：順著某一條搜索路徑巡訪二叉樹(shù)中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次（又稱周游）

“訪問(wèn)”的含義很廣，可以是對(duì)結(jié)點(diǎn)作各種處理，如：輸出結(jié)點(diǎn)的信息、修改結(jié)點(diǎn)的數(shù)據(jù)值等，但要求這種訪問(wèn)不破壞原來(lái)的數(shù)據(jù)結(jié)構(gòu)。

遍歷目的：得到樹(shù)中所有結(jié)點(diǎn)的一個(gè)線性排列。

遍歷的用途：它是樹(shù)結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹(shù)運(yùn)算的基礎(chǔ)和核心。

1.遍歷的方法

依次遍歷二叉樹(shù)中的三個(gè)組成部分，便是遍歷了整個(gè)二叉樹(shù)

??

DLR——先（根）序遍歷 根左右 ABC

LDR——中（根）序遍歷 左根右 BAC

LRD——后（根）序遍歷 左右根 BCA

例題1：

??

先序：A B D G C E H F

中序：D G B A E H C F

后序：G D B H E F C A

例題2：

已知先序和中序序列求二叉樹(shù)

已知二叉樹(shù)的先序和中序序列，構(gòu)造出相應(yīng)的二叉樹(shù)

先序：A B C D E F G H I J

中序：C D B F E A I H G J

最上面的根是A，通過(guò)中序可知左右子樹(shù)

??

2.遞歸算法

1.先序遍歷算法

Status PreOrderTraverse(BiTree T)
{
 ? ?if(T == NULL) return OK;//空二叉樹(shù)
 ? ?else
 ?  {
 ? ? ? ?visit(T);//訪問(wèn)根節(jié)點(diǎn)
 ? ? ? ?PreOrderTraverse(T->lchild);//遞歸遍歷左子樹(shù)
 ? ? ? ?PreOrderTraverse(T->rchild);//遞歸遍歷右子樹(shù)
 ?  }
}

2.中序遍歷算法

Status PreOrderTraverse(BiTree T)
{
 ? ?if(T == NULL) return OK;//空二叉樹(shù)
 ? ?else
 ?  {
 ? ? ? ?PreOrderTraverse(T->lchild);//遞歸遍歷左子樹(shù)
 ? ? ? ?visit(T);//訪問(wèn)根節(jié)點(diǎn)
 ? ? ? ?PreOrderTraverse(T->rchild);//遞歸遍歷右子樹(shù)
 ?  }
}

3.后序遍歷算法

Status PreOrderTraverse(BiTree T)
{
 ? ?if(T == NULL) return OK;//空二叉樹(shù)
 ? ?else
 ?  {
 ? ? ? ?PreOrderTraverse(T->lchild);//遞歸遍歷左子樹(shù)
 ? ? ? ?PreOrderTraverse(T->rchild);//遞歸遍歷右子樹(shù)
 ? ? ? ?visit(T);//訪問(wèn)根節(jié)點(diǎn)
 ?  }
}

3.非遞歸算法

1.中序遍歷算法

棧

Status InOrderTraverse(BiTree T)
{
 ? ?BiTree p;
 ? ?InitStack(S);
 ? ?p = T;
 ? ?while(p || !StackEmpty(S))
 ?  {
 ? ? ? ?if(p)
 ? ? ?  {
 ? ? ? ? ? ?Push(S,p);
 ? ? ? ? ? ?p = p->lchild;
 ? ? ?  }
 ? ? ? ?else
 ? ? ?  {
 ? ? ? ? ? ?Pop(S,q);
 ? ? ? ? ? ?cout << q->data << " ";
 ? ? ? ? ? ?p = q->rchild;
 ? ? ?  }
 ? ? ? ?return OK;
 ?  }
}

2.層次遍歷算法

將根結(jié)點(diǎn)進(jìn)隊(duì)；

隊(duì)不空時(shí)循環(huán)：從隊(duì)列中出列一個(gè)結(jié)點(diǎn)*p，訪問(wèn)它；

1. 若它有左孩子結(jié)點(diǎn)，將左孩子結(jié)點(diǎn)進(jìn)隊(duì)；

2. 若它有右孩子結(jié)點(diǎn)，將右孩子結(jié)點(diǎn)進(jìn)隊(duì)。

void LevelOrder(BTNode *b)
{
 ? ?BTNode *p;
 ? ?SqOueue *qu;
 ? ?InitQueue(qu);//初始化隊(duì)列
 ? ?enQueue(qu, b);//根結(jié)點(diǎn)指針進(jìn)入隊(duì)列
 ? ?while(!QueueEmpty(qu))
 ?  {
 ? ? ? ?//隊(duì)不為空，則循環(huán)
 ? ? ? ?deQueue(qu, p);//出隊(duì)結(jié)點(diǎn)p
 ? ? ? ?cout << p->data;//訪問(wèn)結(jié)點(diǎn)p
 ? ? ? ?if(p->lchild != NULL)
 ? ? ? ? ? ?enQueue(qu, p->lchild);//有左孩子時(shí)將其進(jìn)隊(duì)
 ? ? ? ?if(p->rchild != NULL)
 ? ? ? ? ? ?enQueue(qu, p->rchild);//有右孩子時(shí)將其進(jìn)隊(duì)
 ?  }
}

4.二叉樹(shù)的建立

按先序遍歷序列建立二叉樹(shù)的二叉鏈表

例：已知先序序列為：A B C D E G F

1. 從鍵盤輸入二叉樹(shù)的結(jié)點(diǎn)信息，建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)；

2. 在建立二叉樹(shù)的過(guò)程中按照二叉樹(shù)先序方式建立；

Status CreateBiTree(BiTree &T)
{
 ? ?cin >> ch;
 ? ?if(ch == "#") T = NULL;
 ? ?else
 ?  {
 ? ? ? ?if(!(T = (BiTNode *)malloc(sizeof(BiTNode))))
 ? ? ?  {
 ? ? ? ? ? ?exit(OVERFLOW);//T = new BiTNode;
 ? ? ?  }
 ? ? ? ?T->data = ch;//生成根結(jié)點(diǎn)
 ? ? ? ?CreateBiTree(T->lchild);//構(gòu)建左子樹(shù)
 ? ? ? ?CreateBiTree(T->rchild);//構(gòu)建右子樹(shù)
 ?  }
 ? ?return OK;
}//CreateBiTree

5.復(fù)制二叉樹(shù)

如果是空樹(shù)，遞歸結(jié)束；

否則，申請(qǐng)新結(jié)點(diǎn)空間，復(fù)制根結(jié)點(diǎn)

遞歸復(fù)制左子樹(shù)和遞歸復(fù)制右子樹(shù)

int Copy(BiTree T, BiTree &NewT)
{
 ? ?if(T == NULL)
 ?  {
 ? ? ? ?//如果是空樹(shù)返回0
 ? ? ? ?NewT = NULL;
 ? ? ? ?return 0;
 ?  }
 ? ?else
 ?  {
 ? ? ? ?NewT = new BiTNode;
 ? ? ? ?NewT->data = T->data;
 ? ? ? ?Copy(T->lchild, NewT->lchild);
 ? ? ? ?Copy(T->rchild, NewT->rchild);
 ?  }
}

6.計(jì)算二叉樹(shù)的深度

如果是空樹(shù)則深度為0；

否則，遞歸計(jì)算左子樹(shù)的深度記為，遞歸計(jì)算右子樹(shù)的深度記為n,二叉樹(shù)的深度則為m與的較大者加1。

int Depth(BiTree T)
{
 ? ?if(T == NULL) return 0;//如果是空樹(shù)就返回0
 ? ?else
 ?  {
 ? ? ? ?m = Depth(T->lchild);
 ? ? ? ?n = Depth(T->rchild);
 ? ? ? ?if(m > n) return ( m + 1 );
 ? ? ? ?else return (n + 1);
 ?  }
}

7.二叉樹(shù)結(jié)點(diǎn)總數(shù)

如果是空樹(shù)，則結(jié)點(diǎn)個(gè)數(shù)為

否則，結(jié)點(diǎn)個(gè)數(shù)為左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù) + 右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù) + 1。

int NodeCount(BiTree T)
{
 ? ?if(T == NULL)
 ?  {
 ? ? ? ?return 0;
 ?  }
 ? ?else
 ? ? ? ?return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

8.二叉樹(shù)葉子結(jié)點(diǎn)數(shù)

如果是空樹(shù)，則葉子結(jié)點(diǎn)個(gè)數(shù)為0；

否則，為左子樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù) + 右子樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)。

int LeadCount(BiTree T)
{
 ? ?if(T == NULL)//如果是空樹(shù)返回0
 ? ? ? ?return 0;
 ? ?if(T->lchild == NULL && T->rchild == NULL)
 ?  {
 ? ? ? ?return 1;//如果是葉子結(jié)點(diǎn)返回1
 ?  }
 ? ?else
 ?      return LeafCount(T->lchild) + LeafCount(T->rchild);
}

線索二叉樹(shù)

1.線索二叉樹(shù)概念

提出的問(wèn)題：

如何尋找特定遍歷序列中二叉樹(shù)結(jié)點(diǎn)的前驅(qū)和后繼？？？

解決的方法：

1. 通過(guò)遍歷尋找——費(fèi)時(shí)間；

2. 再增設(shè)前驅(qū)、后繼指針域——增加了存儲(chǔ)負(fù)擔(dān)；

回顧：

二叉樹(shù)鏈表中空指針域的數(shù)量：具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，一共有2n個(gè)指針域；因?yàn)閚個(gè)結(jié)點(diǎn)中有n - 1個(gè)孩子，即2n個(gè)指針域中，有n - 1個(gè)用來(lái)指示結(jié)點(diǎn)的左右孩子，其余n + 1個(gè)指針域?yàn)榭铡?/p>

利用二叉鏈表中空指針域：如果某個(gè)結(jié)點(diǎn)的左孩子為空，則將空的左孩子指針域改為指向其前驅(qū)；如果某結(jié)點(diǎn)的右孩子為空，則將右孩子指針域改為指向其后繼。

——這種改變指向的指針稱為“線索”

加上線索的二叉樹(shù)稱為線索二叉樹(shù)(Threaded Binary Tree)

?

按照存儲(chǔ)結(jié)構(gòu)的前驅(qū)和后繼，將指針域的值進(jìn)行指向

為了區(qū)分lchild和rchild指針到底是指向孩子的指針，還是指向前驅(qū)或者后繼的指針，對(duì)二叉鏈表中每一個(gè)結(jié)點(diǎn)增設(shè)兩個(gè)標(biāo)志域ltag和rtag，并且約定：

ltag = 0 lchild指向該結(jié)點(diǎn)的左孩子

ltag = 1 lchild指向該結(jié)點(diǎn)的前驅(qū)

rtag = 0 rchild指向該結(jié)點(diǎn)的右孩子

rtag = 1 rchild指向該結(jié)點(diǎn)的后繼

增設(shè)頭結(jié)點(diǎn)：ltag=O,Ichild指向根結(jié)點(diǎn)，rtag=1,rchild指向遍歷序列中最后一個(gè)結(jié)點(diǎn)。遍歷序列中第一個(gè)結(jié)點(diǎn)的c域和最后一個(gè)結(jié)點(diǎn)的rc域都指向頭結(jié)點(diǎn)。

??

2.線索二叉樹(shù)練習(xí)

1.先序線索二叉樹(shù)

??

先序序列：A B C D E

?

?

2.中序線索二叉樹(shù)

?

中序遍歷：H D I B E A F C G

樹(shù)和森林

1.樹(shù)與森林概念

??

樹(shù)(Tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集。若n=0,稱為空樹(shù)； 若n>0

1. 有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；

2. 其余結(jié)點(diǎn)可分為m(m≥0)個(gè)互不相交的有限集T1,T2,T3,...,Tm,

??

森林：是m(m≥0)棵不相交的樹(shù)的集合。

2.樹(shù)的存儲(chǔ)結(jié)構(gòu)

1.雙親表示法

實(shí)現(xiàn)：定義結(jié)構(gòu)數(shù)組，存放樹(shù)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域；

1. 數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息。

2. 雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的位置。

?

?

?

類型描述

typedef struct PTNode
{
 ? ?TElemType data;
 ? ?int parent;//雙親位置域
}PTNode;

樹(shù)結(jié)構(gòu)：

#define MAX_TREE_SIZE 100
typedef struct
{
 ? ?PTNode nodes[MAX_TREE_SIZE];
 ? ?int r, n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)
}PTree;

2.孩子鏈表

把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，看成是一個(gè)線性表，用單鏈表存儲(chǔ)，則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表（葉子的孩子鏈表為空表）。而n個(gè)頭指針又組成一個(gè)線性表，用順序表（含n個(gè)元素的結(jié)構(gòu)數(shù)組）存儲(chǔ)。

?

?

C語(yǔ)言類型描述：

孩子結(jié)點(diǎn)結(jié)構(gòu)：

typedef struct CTNode
{
 ? ?int child;
 ? ?struct CTNode *next;
}*ChildPtr;
雙親結(jié)點(diǎn)結(jié)構(gòu)：

typedef struct
{
 ? ?TElemType data;
 ? ?ChildPtr firstchild;//孩子鏈表頭指針
}CTBox;

特點(diǎn)：找孩子容易，找雙親難。

3.孩子兄弟表示法

（二叉樹(shù)表示法，二叉鏈表表示法）

實(shí)現(xiàn)：用二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)

typedef struct CSNode
{
 ? ?ElemType data;
 ? ?struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

?

?

3.樹(shù)與二叉樹(shù)的轉(zhuǎn)換

1.將樹(shù)轉(zhuǎn)化為二叉樹(shù)

將樹(shù)轉(zhuǎn)化為二叉樹(shù)進(jìn)行處理，利用二叉樹(shù)的算法來(lái)實(shí)現(xiàn)對(duì)樹(shù)的操作。

由于樹(shù)與二叉樹(shù)都可以用二叉鏈表做存儲(chǔ)，則以二叉鏈表作為媒介可以導(dǎo)出樹(shù)與二叉樹(shù)之間的一個(gè)對(duì)應(yīng)關(guān)系。

??

算法：

1. 加線：在兄弟之間加一連線

2. 抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系

3. 旋轉(zhuǎn)：以樹(shù)的根結(jié)點(diǎn)為軸心，將整樹(shù)順時(shí)針轉(zhuǎn)45°

口訣：樹(shù)變二叉樹(shù)：兄弟相連留長(zhǎng)子

例題：

?

?

2.將二叉樹(shù)還原回樹(shù)

1. 加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將的右孩子，右孩子的右孩子.…沿分支找到的所有右孩子，都與p的雙親用線連起來(lái)

2. 抹線：抹掉原二叉樹(shù)中雙親與右孩子之間的連線

3. 調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹(shù)結(jié)構(gòu)

口訣：二叉樹(shù)變樹(shù)，左孩右右連雙親，去掉原來(lái)右孩線。

例題：

?

?

?

4.森林與二叉樹(shù)的轉(zhuǎn)化

1.森林轉(zhuǎn)換成二叉樹(shù)(二叉樹(shù)與多棵樹(shù)之間的關(guān)系)

1. 將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù)

2. 將每棵樹(shù)的根結(jié)點(diǎn)用線相連

3. 以第一棵樹(shù)根結(jié)點(diǎn)為二叉樹(shù)的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹(shù)型結(jié)構(gòu)

?

?

2.二叉樹(shù)轉(zhuǎn)化成森林

1. 抹線：將二叉樹(shù)中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹(shù)

2. 還原：將孤立的二叉樹(shù)還原成樹(shù)

口訣：去掉全部右孩線，孤立二叉再還原

例題：

??

5.樹(shù)與森林的遍歷

1.樹(shù)的遍歷（三種方式）

1. 先序：根左右

   若樹(shù)不為空，則先訪問(wèn)根節(jié)點(diǎn)，然后依次遍歷各棵子樹(shù)

2. 后序：左右根

   若樹(shù)不為空，則先依次后根遍歷各棵子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)

3. 按層次遍歷：

   若樹(shù)不為空，則自上而下自左至右訪問(wèn)樹(shù)中每個(gè)結(jié)點(diǎn)

2.森林的遍歷

將森林看作由三部分構(gòu)成：

1. 森林中第一棵樹(shù)的根結(jié)點(diǎn)；

2. 森林中第一棵樹(shù)的子樹(shù)森林；

3. 森林中其它樹(shù)構(gòu)成的森林。

先序遍歷：

若森林不空，則

1. 訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；

2. 先序遍歷森林中第一棵樹(shù)的子樹(shù)森林；

3. 先序遍歷森林中（除第一棵樹(shù)之外）其余樹(shù)構(gòu)成的森林。

中序遍歷：

若森林不空，則

1. 中序遍歷森林中第一棵樹(shù)的子樹(shù)森林；

2. 訪問(wèn)森林中策一棵樹(shù)的根結(jié)點(diǎn)；

3. 中序遍歷森林中（除第一棵樹(shù)之外）其余樹(shù)構(gòu)成的森林。

??

先序遍歷：A B C D E F G H I J

中序遍歷：B C D A F E H J I G文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-428108.html

到了這里，關(guān)于探索樹(shù)形數(shù)據(jù)結(jié)構(gòu)，通識(shí)樹(shù)、森林與二叉樹(shù)的基礎(chǔ)知識(shí)（專有名詞），進(jìn)一步利用順序表和鏈表表示、遍歷和線索樹(shù)形結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！