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

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

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

討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲？特點：——仍然有順序存儲、鏈?zhǔn)酱鎯Φ确绞健?/p>

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

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

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

缺點：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24題2：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG和DECBHGFA，請畫出這棵二叉樹。解題思路分析：①由后序遍歷特征，根結(jié)點必在后序序列尾部（即A）；②由中序遍歷特征，根結(jié)點必在其中間，而且其左部必全部是左子樹的子孫（即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é)點數(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對遍歷的分析：1.從前面的三種遍歷算法可以知道：如果將print語句刪去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問根結(jié)點的時機(jī)不同。2.二叉樹遍歷的時間效率和空間效率：時間效率:O(n)

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

//占用的最大輔助空間

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

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

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

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

DE

G

F

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

T->data=ch;

//生成根結(jié)點

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é)點？

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

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

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

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