樹和二叉樹

• • • 樹
    • • 樹的定義
      • 樹的存儲(chǔ)結(jié)構(gòu)
      • • 雙親表示法
        • 孩子鏈表
        • 孩子兄弟表示法
    • 二叉樹
    • • 定義
      • 案例引入
      • 樹與二叉樹的抽象數(shù)據(jù)類型定義
      • 二叉樹的性質(zhì)
      • 存儲(chǔ)結(jié)構(gòu)
      • 二叉樹的順序存儲(chǔ)
      • 二叉樹的鏈?zhǔn)酱鎯?chǔ)*
      • 遍歷二叉樹方法
      • • 先序遍歷法
        • 中序遍歷
        • 后序遍歷
        • 層次遍歷
      • 根據(jù)遍歷序列確定二叉樹
      • 遞歸調(diào)用的步驟
      • 二叉樹遍歷算法的應(yīng)用
      • • 二叉樹的建立
        • 二叉樹的復(fù)制
        • 二叉樹的深度
        • 二叉樹結(jié)點(diǎn)總數(shù)
        • 二叉樹葉子結(jié)點(diǎn)數(shù)
      • 線索二叉樹

樹

樹的定義

• 樹形結(jié)構(gòu)（非線性結(jié)構(gòu)）：結(jié)點(diǎn)之間有分支；具有層次結(jié)構(gòu)
• 例子：（1）自然界：樹；（2）人類社會(huì)：家譜、行政組織機(jī)構(gòu)；（3）計(jì)算機(jī)領(lǐng)域：①編譯：用樹表示源程序的語(yǔ)法結(jié)構(gòu) ②數(shù)據(jù)庫(kù)系統(tǒng)：用樹組織信息；③算法分析：用樹描述執(zhí)行過(guò)程
• 樹是n個(gè)結(jié)點(diǎn)的有限集，樹的定義顯然是遞歸結(jié)構(gòu)
• 樹的其他表示方式
  
• 樹的基本術(shù)語(yǔ)
  （1）結(jié)點(diǎn)：數(shù)據(jù)元素以及指向子樹的分支
  （2）根結(jié)點(diǎn)：非空樹中無(wú)前驅(qū)結(jié)點(diǎn)的結(jié)點(diǎn)
  （3）結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)
  （4）樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值
  （5）葉子結(jié)點(diǎn)：終端結(jié)點(diǎn)，度=0
  （6）分支結(jié)點(diǎn)：非終端結(jié)點(diǎn)，度≠0
  （7）內(nèi)部結(jié)點(diǎn)：根結(jié)點(diǎn)以外的分支結(jié)點(diǎn)
  （8）孩子、雙親：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子，該結(jié)點(diǎn)稱為孩子的雙親
  （9）兄弟、堂兄弟
  （10）祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)
  （11）子孫：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)
  （12）樹的深度（高度）：樹中結(jié)點(diǎn)的最大層次，根結(jié)點(diǎn)到最底層的最短路徑
  （13）有序樹：樹中結(jié)點(diǎn)的各子樹從左至右有次序（最左邊的為第一個(gè)孩子
  （14）無(wú)序樹：樹中結(jié)點(diǎn)的各子樹無(wú)次序
  （15）森林：是m(m≥0)棵互不相交的樹的集合
  把根節(jié)點(diǎn)刪除的樹就成了森林
  一棵樹可以看成是一個(gè)特殊的森林；給森林中的各子樹加上一個(gè)雙親結(jié)點(diǎn)，森林就變成了樹
  因此，樹一定是森林，森林不一定是樹

樹的存儲(chǔ)結(jié)構(gòu)

雙親表示法

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

• 數(shù)據(jù)域：存放結(jié)點(diǎn)本身的信息
• 雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)數(shù)組中的位置
  
  特點(diǎn)：找雙親容易，找孩子難
  

孩子鏈表

孩子兄弟表示法

又叫二叉樹表示法/二叉鏈表表示法
實(shí)現(xiàn)：用二叉鏈表作樹的存儲(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;

二叉樹

定義

二叉樹的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；可以證明，所有的樹都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹，不失一般性
普通樹若不轉(zhuǎn)化為二叉樹，運(yùn)算很難實(shí)現(xiàn)

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

特點(diǎn)：
（1）每個(gè)結(jié)點(diǎn)最多有倆孩子（二叉樹中不存在度大于2的結(jié)點(diǎn)）
（2）子樹有左右之分，次序不能顛倒
（3）二叉樹可以是空集合，根可以有空的左子樹或空的右子樹

注意事項(xiàng)

二叉樹也并非有序樹，而是一種獨(dú)立的概念

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

案例引入

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

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

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

相似，因此主要研究二叉樹的抽象數(shù)據(jù)類型定義

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

二叉樹的性質(zhì)

滿二叉樹：一棵深度為k且有2^k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹
特點(diǎn)：①每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)（每層都滿）②葉子結(jié)點(diǎn)全部在最底層
編號(hào)：①規(guī)則：從根結(jié)點(diǎn)開始，自上而下，自左而右 ②每一結(jié)點(diǎn)的位置都有元素

完全二叉樹：

注意：在滿二叉樹中，從最后一個(gè)節(jié)點(diǎn)開始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹
特點(diǎn)：①葉子只可能分布在層次最大的兩層上 ②對(duì)任一結(jié)點(diǎn)，如果其右子樹的最大層次為i，則其左子樹的最大層次必為i或i+1
滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹

性質(zhì)：

在二叉樹的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)(i≥1),至少有1個(gè)結(jié)點(diǎn)(不然沒有第i層)

深度為k的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)(k≥1),至少有k個(gè)結(jié)點(diǎn)

對(duì)任何一棵二叉樹T，如果其葉子數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0 = n2+1
證明：邊數(shù)m = 結(jié)點(diǎn)n - 1（每個(gè)結(jié)點(diǎn)與雙親結(jié)點(diǎn)有一條邊，除了根結(jié)點(diǎn)）//邊數(shù)m = 2n2+n11(度為2的n2產(chǎn)生2條邊，度為1的n1產(chǎn)生1條邊)
∴n-1 = 2n2+1n1 ,又∵n = n0+n1+n2 ∴n0 = n2+1

存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)+鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(二叉鏈表+三叉鏈表)

二叉樹的順序存儲(chǔ)

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

定義：typedef TElemType SqBiTree[MAXSIZE]
SqBiTree bt; //定義了bt數(shù)組

缺點(diǎn)：①大小固定 ②可能浪費(fèi)空間

結(jié)點(diǎn)間的關(guān)系蘊(yùn)含在其存儲(chǔ)中，適合滿二叉樹和完全二叉樹

二叉樹的鏈?zhǔn)酱鎯?chǔ)*

二叉鏈表的定義：
typedef struct BiNode {
TElemType data;
struct BiNode * lchild, *rchild; //左右孩子指針
}BiNode, *BiTree;

三叉鏈表的定義
typedef struct TriTNode {
TElemType data;
struct TriTNode *lchild,*rchid,*parent;
}

遍歷二叉樹方法

定義：順著某一條搜索路徑巡防二叉樹中的結(jié)點(diǎn)，使每個(gè)二叉樹均被訪問(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)

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

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

遍歷方法：6種方法(可先右子樹，再左子樹的三種)

先根（序）遍歷：若二叉樹為空，則空操作；否則（1）訪問(wèn)根節(jié)點(diǎn)（2）先序遍歷左子樹（3）先序遍歷右子樹

中根（序）遍歷：若二叉樹為空，則空操作；否則（1）中序遍歷左子樹（2）訪問(wèn)根節(jié)點(diǎn)（3）中序遍歷右子樹

后根（序）遍歷：若二叉樹為空，則空操作；否則（1）后序遍歷左子樹（2）后序遍歷右子樹（3）訪問(wèn)根節(jié)點(diǎn)
由上可知，遍歷時(shí)用遞歸操作

先序遍歷法

若二叉樹為空，則空操作；
否則：
（1）訪問(wèn)根節(jié)點(diǎn)
（2）先序遍歷左子樹
（3）先序遍歷右子樹

• 先序遍歷：ABELADHMIJ
  遞歸算法

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

非遞歸算法
思路：

根結(jié)點(diǎn)非空，進(jìn)棧

中序遍歷

若二叉樹為空，則空操作；
否則：
（1）中序遍歷左子樹
（2）訪問(wèn)根節(jié)點(diǎn)
（3）中序遍歷右子樹

• 中序遍歷：ELBAMHIDJ
  遞歸算法

if (T == NULL) return OK; else {InOrderTraverse(T->lchild);visit(T);InOrderTraverse(T->rchild); }

非遞歸算法
關(guān)鍵：在中序遍歷過(guò)某結(jié)點(diǎn)的整個(gè)左子樹后，如何找到該結(jié)點(diǎn)的根以及右子樹
基本思想：

建立一個(gè)棧

根結(jié)點(diǎn)進(jìn)棧，遍歷左子樹

根結(jié)點(diǎn)出棧，輸出根結(jié)點(diǎn)，遍歷右子樹

BiTree p; IntiStack(S); p = T; while (p || !StackEmpty(S)) {if (p) {Push(S,p); p = p->lchild;}else {Pop(S,q); printf("%c",q->data); p = q->rchild;} } return OK;

后序遍歷

若二叉樹為空，則空操作；
否則：
（1）后序遍歷左子樹
（2）后序遍歷右子樹
（3）訪問(wèn)根節(jié)點(diǎn)

• 后序遍歷：LEBMIHJDA
  遞歸算法：

if (T == NULL) return OK; else {PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);visit(T); }

其中先序的結(jié)果叫做前綴表示（波蘭式）
中序的結(jié)果叫做中綴表示
后序的結(jié)果叫做后綴表示（逆波蘭式）

層次遍歷

對(duì)于一棵二叉樹，從根結(jié)點(diǎn)開始，從上到下，從左到右的順序訪問(wèn)每一個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)僅僅訪問(wèn)一次
算法設(shè)計(jì)思路：使用一個(gè)隊(duì)列
Ⅰ將根結(jié)點(diǎn)進(jìn)隊(duì)
Ⅱ隊(duì)不空時(shí)循環(huán)：從隊(duì)列中出列一個(gè)結(jié)點(diǎn)*p，訪問(wèn)它；
①若它有左孩子結(jié)點(diǎn)，將左孩子結(jié)點(diǎn)進(jìn)隊(duì)
②若它有右孩子結(jié)點(diǎn)，將右孩子結(jié)點(diǎn)進(jìn)隊(duì)

void LevelOrder(BTNode * b) {BTNode *p; SqQueue *qu;IntiQueue(qu); //初始化隊(duì)列enQueue(qu,b); //根結(jié)點(diǎn)指針進(jìn)入隊(duì)列while (!QueueEmpty(qu)) {deQueue(qu,p); //出隊(duì)結(jié)點(diǎn)pprintf("%c", p->data); //訪問(wèn)結(jié)點(diǎn)pif (p->lchild != NULL) enQueue(qu, p->lchild); //有左孩子時(shí)將其進(jìn)隊(duì)if (p->rchild != NULL) enQueue(qu, p->rchild); //有右孩子時(shí)將其進(jìn)隊(duì)} }

根據(jù)遍歷序列確定二叉樹

• 先序序列和中序序列
  eg：
  先序：ABCDEFGHIJ
  中序：CDBFEAIHGJ
• 后序：DCFEBIHJGA
• 中序序列和后序序列
  eg：
  中序：BDCEAFHG
  后序：DECBHGFA
• 先序：ABCDEFGH

遞歸調(diào)用的步驟

時(shí)間效率：O（n） //每個(gè)結(jié)點(diǎn)只訪問(wèn)一次
空間效率：O（n） //棧占用的最大輔助空間

二叉樹遍歷算法的應(yīng)用

二叉樹的建立

僅輸入ABCDEGF所得的樹不唯一
對(duì)如圖所示的二叉樹，輸入字符：ABC##DE#G##F###，僅得到左邊的樹

Status CreateBiTree(BiTree &T) {scanf(&ch);if (ch == '#') T = NULL;else {if (! (T = (BiTNode*)malloc(sizeof(BiTNode))) ) exit (OVERFLOW);T->data = ch;CreateBiTree(T->lchild); //構(gòu)造左子樹CreateBiTree(T->rchild); //構(gòu)造右子樹}return OK; }

二叉樹的復(fù)制

如果是空樹，遞歸結(jié)束
否則，申請(qǐng)新結(jié)點(diǎn)空間，復(fù)制根結(jié)點(diǎn)

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

int Copy(BiTree T,BiTree &NewT) {if (T == NULL) {NewT = NULL; return 0;}else {NewT = (BiTree)malloc(sizeof(BiNode));NewT->data = T->data;Copy(T->lChild, NewT->lchild);Copy(T->rChild, NewT->rchild);} }

二叉樹的深度

如果是空樹，則深度為0
否則，遞歸計(jì)算左子樹的深度記為m，遞歸計(jì)算右子樹的深度記為n，二叉樹的深度則為m與n的較大者+1

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

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

如果是空樹，則結(jié)點(diǎn)個(gè)數(shù)為0；
否則，結(jié)點(diǎn)個(gè)數(shù) = 左子樹的結(jié)點(diǎn)個(gè)數(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; }

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

如果是空樹，則葉子結(jié)點(diǎn)個(gè)數(shù)為0
否則，為左子樹的葉子結(jié)點(diǎn)個(gè)數(shù)+右子樹的葉子結(jié)點(diǎn)個(gè)數(shù)
注：葉子結(jié)點(diǎn)：左子樹和右子樹均為空

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

線索二叉樹

如果某個(gè)結(jié)點(diǎn)的左孩子為空，則將空的左孩子指針域改為指向其前驅(qū)；如果某個(gè)結(jié)點(diǎn)的右孩子為空，則將空的右孩子指針域指向其后繼，這種改變指向的指針?lè)Q為“線索”
加上了線索的二叉樹稱為線索二叉樹
對(duì)二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過(guò)程叫線索化

定義：
typedef struct BiThrNode {
int data;
int ltag, rtag;
struct BiThrNode *lchild, *rachild;
}BiThrNode, *BiThrTree;

eg：



改進(jìn)

總結(jié)

以上是生活随笔為你收集整理的树——树和二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。