計(jì)算機(jī)軟件基礎(chǔ)04課件

數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容12.4樹和二叉樹一、樹的基本概念二、二叉樹的表示和實(shí)現(xiàn)三、樹和二叉樹的轉(zhuǎn)換四、樹的應(yīng)用（二叉排序樹）樹結(jié)構(gòu)的特點(diǎn)：非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)直接后繼。（一對(duì)多結(jié)構(gòu)）2一、樹的基本概念討論5個(gè)問題：什么是樹？關(guān)于樹有哪些常用術(shù)語？3.樹的邏輯結(jié)構(gòu)？4.樹的存儲(chǔ)結(jié)構(gòu)？5.樹的基本運(yùn)算？32.若干術(shù)語ABCGEIDHFJFLK根葉子森林——即根結(jié)點(diǎn)(沒有前驅(qū))——即終端結(jié)點(diǎn)(沒有后繼)——指m棵互不相交的樹的集合(例如刪除A后的子樹集合)——即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū))——即下層結(jié)點(diǎn)的子樹的根(直接后繼)——同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）——即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）雙親孩子兄弟堂兄弟——樹中結(jié)點(diǎn)在同層中按從左至右有序排列，不能互換——結(jié)點(diǎn)各子樹可互換位置。有序樹無序樹52.若干術(shù)語（續(xù)）結(jié)點(diǎn)結(jié)點(diǎn)的度結(jié)點(diǎn)的層次終端結(jié)點(diǎn)分支結(jié)點(diǎn)樹的度樹的深度(或高度)ABCGEIDHFJFLK——從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）——即度為0的結(jié)點(diǎn)，即葉子——即度不為0的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)）——所有結(jié)點(diǎn)度中的最大值（Max{各結(jié)點(diǎn)的度}）——指所有結(jié)點(diǎn)中最大層次數(shù)（Max{各結(jié)點(diǎn)的層次}）問：右上圖中的結(jié)點(diǎn)數(shù)＝；樹的度＝；樹的深度＝1334——即樹的數(shù)據(jù)元素——結(jié)點(diǎn)所擁有的子樹數(shù)（有幾個(gè)直接后繼就是幾度）63.樹的邏輯結(jié)構(gòu)

一對(duì)多（1:n），有多個(gè)直接后繼（如家譜樹、目錄樹等），但只有一個(gè)根結(jié)點(diǎn)，且子樹之間互不相交。4.樹的存儲(chǔ)結(jié)構(gòu)

討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲(chǔ)？特點(diǎn)：——仍然有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)等方式。

7先研究二叉樹！討論3：樹的鏈?zhǔn)酱鎯?chǔ)方案應(yīng)該怎樣制定？復(fù)原困難討論2：樹的順序存儲(chǔ)方案應(yīng)該怎樣制定？可用多重鏈表：一個(gè)前趨指針，n個(gè)后繼指針。細(xì)節(jié)問題：

樹中結(jié)點(diǎn)的結(jié)構(gòu)類型樣式該如何設(shè)計(jì)？

即應(yīng)該設(shè)計(jì)成“等長(zhǎng)”還是“不等長(zhǎng)”？

缺點(diǎn)：

等長(zhǎng)結(jié)構(gòu)太浪費(fèi)（每個(gè)結(jié)點(diǎn)的度不一定相同）；不等長(zhǎng)結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。先研究最簡(jiǎn)單、最有規(guī)律的樹，然后設(shè)法把一般的樹轉(zhuǎn)化為簡(jiǎn)單樹來處理?？梢?guī)定為：從上至下、從左至右將樹的結(jié)點(diǎn)依次存入內(nèi)存。重大缺陷：解決思路：復(fù)原不具有唯一性就無實(shí)用價(jià)值！8二、二叉樹的表示和實(shí)現(xiàn)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”的樹？二叉樹的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；可以證明，所有樹都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹，不失一般性。1. 二叉樹的定義2. 二叉樹的性質(zhì)二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的基本運(yùn)算（遍歷）102.二叉樹的性質(zhì)討論1：第i層的結(jié)點(diǎn)數(shù)最多是多少？

性質(zhì)1:在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i>0）。性質(zhì)2:深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k>0）。再提問：第i層上至少有

個(gè)結(jié)點(diǎn)？1討論2：深度為k的二叉樹，最多有多少個(gè)結(jié)點(diǎn)？

2i-1個(gè)2k-1個(gè)123.深度為9的二叉樹中至少有

個(gè)結(jié)點(diǎn)。Ａ)２9Ｂ)２8Ｃ)９Ｄ)２9－12.深度為Ｋ的二叉樹的結(jié)點(diǎn)總數(shù)，最多為

個(gè)。Ａ)２k-1Ｂ)log2kＣ)２k－１Ｄ)２k1.樹Ｔ中各結(jié)點(diǎn)的度的最大值稱為樹Ｔ的

。Ａ)高度Ｂ)層次Ｃ)深度Ｄ)度DCC課堂練習(xí)：3.結(jié)論“

”是正確的。Ａ)二叉樹的度為2Ｂ)樹中結(jié)點(diǎn)的度可以小于2Ｃ)二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2Ｄ)二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2B14滿二叉樹：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。

（特點(diǎn)：每層都“充滿”了結(jié)點(diǎn)）完全二叉樹：深度為k的、有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。（特點(diǎn)：k-1層都“滿”，最后一層的左邊也是滿的）AOBCGEKDJFIHNML深度為4的滿二叉樹完全二叉樹EABCGIDHFJ三種特殊的二叉樹：平衡二叉樹：或是一空樹，或具有下列性質(zhì)①左、右子樹均為平衡二叉樹；②左、右子樹的深度之差的絕對(duì)值不超過1且J?平衡二叉樹ABCDFGH?HG15課堂討論：?jiǎn)?：為何要研究完全/滿二叉樹這兩種特殊的二叉樹？答：因?yàn)樗鼈冊(cè)陧樞虼鎯?chǔ)方式下可以復(fù)原！問2：滿二叉樹和完全二叉樹有什么區(qū)別？答：滿二叉樹是葉子一個(gè)也不少的樹，而完全二叉樹雖然前n-1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。滿二叉樹是完全二叉樹的一個(gè)特例。16對(duì)于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹）

還特別具備以下2個(gè)性質(zhì)：性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度必為log2n＋1性質(zhì)5:對(duì)完全二叉樹，若從上至下、從左至右編號(hào)，則編號(hào)為i的結(jié)點(diǎn)，其左孩子編號(hào)必為2i，其右孩子編號(hào)為2i＋1；其雙親的編號(hào)必為i/2

（i＝1時(shí)為根除外)。性質(zhì)4證明：根據(jù)性質(zhì)2，深度為k的二叉樹最多只有2k-1個(gè)結(jié)點(diǎn)，且完全二叉樹的定義是與同深度的滿二叉樹前面編號(hào)相同，即它的總結(jié)點(diǎn)數(shù)n位于k層和k-1層滿二叉樹容量之間，即2k-1-1<n≤2k-1或2k-1≤n<2k三邊同時(shí)取對(duì)數(shù)得：k-1≤log2n<k因?yàn)閗是整數(shù)，所以k=log2n+1173.二叉樹的存儲(chǔ)結(jié)構(gòu)(一)順序存儲(chǔ)結(jié)構(gòu)按二叉樹的結(jié)點(diǎn)“自上而下、從左至右”編號(hào)，用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF討論1：順序存儲(chǔ)后能否復(fù)原成唯一對(duì)應(yīng)的二叉樹形狀？若是完全/滿二叉樹則可以做到唯一復(fù)原，而且有以下規(guī)律：下標(biāo)值為i的雙親，其左孩子的下標(biāo)值必為2i，其右孩子的下標(biāo)值必為2i＋1（即性質(zhì)5）

例如，對(duì)應(yīng)[2]的兩個(gè)孩子必為[4]和[5],即B的左孩子必是D,右孩子必為E。18(二)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

用二叉鏈表即可方便表示。dataleft_childright_childdataleft_childright_child二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義：typedefstructnode{intdata;structnode*left_child,*right_child;}Node;一般從根結(jié)點(diǎn)開始存儲(chǔ)。

（相應(yīng)地，訪問樹中結(jié)點(diǎn)時(shí)也只能從根開始）注：如果需要倒查某結(jié)點(diǎn)的雙親，可以再增加一個(gè)雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。20二叉樹的鏈?zhǔn)酱鎯?chǔ)示例：ABECDFAB^D^C^^E^^^F214.二叉樹的運(yùn)算——遍歷遍歷定義——遍歷用途——遍歷方法——遍歷規(guī)則——指按某條搜索路線遍訪全部結(jié)點(diǎn)且每個(gè)結(jié)點(diǎn)只被訪問一次(即不重復(fù))它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。對(duì)每個(gè)結(jié)點(diǎn)的查看通常都是“先左后右”。為什么今天只討論遍歷運(yùn)算？——因?yàn)樗嵌鏄湟磺羞\(yùn)算的基礎(chǔ)和核心，是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提。見下頁。23遍歷規(guī)則———二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、L、R以根結(jié)點(diǎn)為參照系注：“先、中、后”的意思是指訪問的結(jié)點(diǎn)D是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。

D、L、R的組合定義了六種可能的遍歷方案：LDR,LRD,DLR,DRL,RDL,RLD

若限定先左后右，則有三種實(shí)現(xiàn)方案：DLRLDRLRD先序遍歷中序遍歷后序遍歷

24題2：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG和DECBHGFA，請(qǐng)畫出這棵二叉樹。解題思路分析：①由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部（即A）；②由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左子樹的子孫（即BDCE），其右部必全部是右子樹的子孫（即FHG）；③繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推。若已知先序（或后序）遍歷結(jié)果和中序遍歷結(jié)果，能否“恢復(fù)”出二叉樹？能！26已知中序遍歷：BDCEAFHG已知后序遍歷：DECBHGFA（BDCE）（FHG）A（DCE）BFGHCDEABBACCD

C

E“恢復(fù)”過程：27思路：先畫樹然后進(jìn)行后序遍歷

思考題：

已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為：ABDEGCFH和DBEGACFH，則該二叉樹的后序遍歷序列是什么？

A

BCDEGFH故后序遍歷為：

DGEBHFCA28中序遍歷算法LDR(Node*root){if(root!=NULL){LDR(root->lchild);printf(“%d”,root->data);LDR(root->rchild);}return(0);}后序遍歷算法LRD(Node*root){if(root!=NULL)

{LRD(root->lchild);

LRD(root->rchild);printf(“%d”,root->data);}return(0);}結(jié)點(diǎn)數(shù)據(jù)類型自定義typedefstructnode{intdata;structnode*lchild,*rchild；}Node;Node*root;

先序遍歷算法DLR(Node*root){if(root!=NULL)//非空二叉樹

{printf(“%d”,root->data);//訪問DDLR(root->lchild);//遞歸遍歷左子樹LDLR(root->rchild);

//遞歸遍歷右子樹R}return(0);}30對(duì)遍歷的分析：1.從前面的三種遍歷算法可以知道：如果將print語句刪去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問根結(jié)點(diǎn)的時(shí)機(jī)不同。2.二叉樹遍歷的時(shí)間效率和空間效率：時(shí)間效率:O(n)

//每個(gè)結(jié)點(diǎn)只訪問一次空間效率:O(n)

//占用的最大輔助空間

(因?yàn)閚個(gè)結(jié)點(diǎn)肯定會(huì)有n＋1個(gè)空指針，即輔助空間為n)31例1：編寫遞歸算法，計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。

思路：輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計(jì)并打印出來。DLR(Node*root)//采用先序遍歷的遞歸算法{if(root!=NULL)//非空二叉樹條件，等效于if(root){if(!root->lchild&&!root->rchild)//是葉子結(jié)點(diǎn)則統(tǒng)計(jì)并打印{sum++;printf("%d\n",root->data);}

DLR(root->lchild);//遞歸遍歷左子樹，直到葉子處；

DLR(root->rchild);}//遞歸遍歷右子樹，直到葉子處；}return(0);}32用空格字符表示‘無孩子’或設(shè)指針為空注：要實(shí)現(xiàn)遍歷運(yùn)算，必須先把二叉樹存入電腦內(nèi)怎樣建樹？試將下面的二叉樹以二叉鏈表形式存入計(jì)算機(jī)內(nèi)。ABGDFCE考慮1：輸入結(jié)點(diǎn)時(shí)怎樣表示“無孩子”？考慮2：以何種遍歷方式來輸入并建樹？可以自行設(shè)計(jì)，將二叉樹按先序遍歷次序輸入：ABC

DE

G

F

(/n)以先序遍歷最為合適，讓每個(gè)結(jié)點(diǎn)都能及時(shí)被連接到位。33附：建樹算法：BiTNode*CreateBiTree(BiTNode*T){//構(gòu)造二叉樹Tscanf(“%c”,&ch);if(ch==‘’)T=NULL;else{

T->data=ch;

//生成根結(jié)點(diǎn)

BiTNode*t;t=(BiTNode*)malloc(sizeof(BiTNode));

T->lchild

=CreateBiTree(t);//構(gòu)造左子樹

t=(BiTNode*)malloc(sizeof(BiTNode));

T->rchild

=CreateBiTree(t);//構(gòu)造右子樹}returnT;}//CreateBiTree演示程序|建樹及遍歷34例2.如何按層次輸出二叉樹中所有結(jié)點(diǎn)？

算法思路：既然要求從上到下，從左到右，則利用隊(duì)列存放各子樹結(jié)點(diǎn)的指針是個(gè)好辦法，不能用遞歸算法。技巧：當(dāng)根結(jié)點(diǎn)入隊(duì)后，令其左、右孩子結(jié)點(diǎn)入隊(duì)，而左孩子出隊(duì)時(shí)又令它的左右孩子結(jié)點(diǎn)入隊(duì)，……由此便可產(chǎn)生按層次輸出的效果。ABCDE35三、樹與二叉樹的轉(zhuǎn)換轉(zhuǎn)換步驟：step1:將樹中同一結(jié)點(diǎn)的兄弟相連;加線抹線旋轉(zhuǎn)討論1：樹如何轉(zhuǎn)為二叉樹？用孩子—兄弟表示法step2:保留結(jié)點(diǎn)的最左孩子連線，刪除其它孩子連線；step3:將同一孩子的連線繞左孩子旋轉(zhuǎn)45度角。36方法：加線—抹線—旋轉(zhuǎn)

abeidfhgc樹轉(zhuǎn)二叉樹舉例：abeidfhgc兄弟相連長(zhǎng)兄為父孩子靠左右孩子都是兄弟！根結(jié)點(diǎn)肯定沒有右孩子！右孩子都是兄弟！37二叉樹還原為樹舉例：abeidfhgc只需逆操作，把所有右孩子變?yōu)樾值埽?/p>

abdefhgic38四、樹的應(yīng)用（二叉排序樹）排序樹——帶權(quán)樹——最優(yōu)樹——特點(diǎn)：路徑帶權(quán)值（例如長(zhǎng)度）是帶權(quán)路徑長(zhǎng)度最短的樹，又稱哈夫曼樹，用途之一是通信中的壓縮編碼。特點(diǎn)：所有結(jié)點(diǎn)“左小右大”今天只介紹二叉排序樹391.二叉排序樹的定義----或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹：

（1）左子樹的所有結(jié)點(diǎn)數(shù)據(jù)值均小于根結(jié)點(diǎn)的數(shù)據(jù)值；（2）右子樹的所有結(jié)點(diǎn)數(shù)據(jù)值均大于或等于根結(jié)點(diǎn)的數(shù)據(jù)值；（3）它的左右子樹也分別為二叉排序樹。45245312902453151290看圖：判斷它們是不是二叉排序樹？(a)(b)簡(jiǎn)言之：左小右大！√×想一想：對(duì)二叉排序樹中序遍歷之后的結(jié)果是什么？404524531290如果改變輸入順序?yàn)椋?4，53，45，45，12，24，90），例：將序列（45，24，53，45，12，24，90）建為二叉排序樹則生成的二叉排序樹形態(tài)不同245345129