第七章 樹狀結(jié)構(gòu)

第七章樹狀結(jié)構(gòu)第1頁，課件共53頁，創(chuàng)作于2023年2月7.1何謂樹狀結(jié)構(gòu)樹狀結(jié)構(gòu)在計(jì)算機(jī)信息處理中應(yīng)用相當(dāng)廣泛，如文件系統(tǒng)、目錄組織、菜單管理等。樹狀結(jié)構(gòu)中常見的是樹和二叉樹，本章介紹這兩種結(jié)構(gòu)的概念、存儲(chǔ)結(jié)構(gòu)和相關(guān)算法，并研究樹、二叉樹之間的相互轉(zhuǎn)換，最后給出樹形結(jié)構(gòu)在現(xiàn)實(shí)生活中的一些具體應(yīng)用。第2頁，課件共53頁，創(chuàng)作于2023年2月7.1何謂樹狀結(jié)構(gòu)樹是n（n≥0）個(gè)有限元素（習(xí)慣稱作結(jié)點(diǎn)）的集合T。當(dāng)n=0時(shí)，稱這棵樹為空樹；當(dāng)n>0時(shí)，集合T滿足如下條件：（1）有且只有一個(gè)稱為根（Root）的結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼；（2）其余的n-1個(gè)結(jié)點(diǎn)可以劃分為m個(gè)互不相交的有限集T1，T2，T3，…，Tm，其中每個(gè)集合Ti又是一棵樹，稱為根（Root）的子樹。每棵子樹的根結(jié)點(diǎn)有且只有一個(gè)直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。可以看出，樹的定義用到了遞歸的方法，即用樹來定義樹，這種方法在后面樹（特別是二叉樹）的遍歷、建立等算法中經(jīng)常用到。

第3頁，課件共53頁，創(chuàng)作于2023年2月7.1.1何謂樹從圖中樹T可知，節(jié)點(diǎn)A為樹T的根節(jié)點(diǎn)(root)，B,C,D….,M則為節(jié)點(diǎn)A的子節(jié)點(diǎn)，若包含其下?lián)碛械乃凶庸?jié)點(diǎn)，則為Tree—T的子樹(subtree)。例如B是A的子節(jié)點(diǎn)，P、Q皆是B的子節(jié)點(diǎn)，而B、P、Q為樹T的子樹。第4頁，課件共53頁，創(chuàng)作于2023年2月7.1.2樹的相關(guān)名稱及意義(1) 根節(jié)點(diǎn)(rootnode)： 一棵樹中沒有前驅(qū)節(jié)點(diǎn)的節(jié)點(diǎn)，稱為根節(jié)點(diǎn)。(6) 分支度(度)(degree)：節(jié)點(diǎn)的分支度為每個(gè)節(jié)點(diǎn)所擁有的子節(jié)點(diǎn)個(gè)數(shù)。而一棵樹中最大的分支度值，即為該樹的分支度。(2) 葉節(jié)點(diǎn)(leafnode)或終端節(jié)點(diǎn)(terminalmode)：一棵樹中沒有子節(jié)點(diǎn)的節(jié)點(diǎn)，稱為葉節(jié)點(diǎn)。葉節(jié)點(diǎn)的分支度為0。(3) 非終端節(jié)點(diǎn)(nonterminalmode)除了葉節(jié)點(diǎn)以外的其它節(jié)點(diǎn)，稱為非終端節(jié)點(diǎn)。(4) 父節(jié)點(diǎn)(parent)和子節(jié)點(diǎn)(child)：若節(jié)點(diǎn)x有一個(gè)以節(jié)點(diǎn)y為樹根(root)的子樹，則x為y的父節(jié)點(diǎn)，而y為x的子節(jié)點(diǎn)。節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)稱為該節(jié)點(diǎn)的父節(jié)點(diǎn)。樹中一個(gè)節(jié)點(diǎn)的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)。第5頁，課件共53頁，創(chuàng)作于2023年2月7.1.2樹的相關(guān)名稱及意義(5) 兄弟(sibling)：同一個(gè)父節(jié)點(diǎn)之節(jié)點(diǎn)，稱為兄弟。如圖，B、C、D的父節(jié)點(diǎn)均為A，故B、C、D互為兄弟。(9) 祖先(ancestor)：某節(jié)點(diǎn)x的祖先是從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)。(7) 節(jié)點(diǎn)的階層（層次）(level)： 階層為節(jié)點(diǎn)之特性值，將根節(jié)點(diǎn)之階層設(shè)為1，其子節(jié)點(diǎn)為2，依此類推。(8) 高度(height)或深度(depth)： 一棵樹中的最大階層值，稱為樹的高度或深度。(10) 樹林(forest)：n≧0個(gè)樹的集合稱為樹林。若將一樹的根節(jié)點(diǎn)移去，所剩這恰是一樹林。第6頁，課件共53頁，創(chuàng)作于2023年2月7.2二叉樹7.2.1何謂二叉樹 二叉樹(Binarytree)是樹的一種，二叉樹中的節(jié)點(diǎn)至多只能有兩個(gè)子節(jié)點(diǎn)。 二叉樹的定義如下：(1) 由有限個(gè)節(jié)點(diǎn)所構(gòu)成之集合，此集合可以為空的。(2) 二叉樹的根節(jié)點(diǎn)下可分成兩個(gè)子樹，稱為左子樹和右子樹，左子樹和右子樹亦稱二叉樹。第7頁，課件共53頁，創(chuàng)作于2023年2月7.2.1何謂二叉樹由二叉樹的定義可知，每個(gè)節(jié)點(diǎn)只能有0、1或2個(gè)子樹，且每個(gè)子樹有左右之分。把位于左邊的叫做左子樹，右邊的叫做右子樹。即使只有一棵子樹時(shí)，也要區(qū)分它是左子樹還是右子樹。第8頁，課件共53頁，創(chuàng)作于2023年2月7.2.3二叉樹的相關(guān)特色二叉樹的性質(zhì)：(1)階層(level)為i的二叉樹，最多有2i-1個(gè)節(jié)點(diǎn)。(2)高度(height)為h的二叉樹，最多有2h－1個(gè)節(jié)點(diǎn)。(3)對(duì)任一個(gè)非空的二叉樹而言，若分支度為i的節(jié)點(diǎn)各有ni個(gè)，則n0=n2+1第9頁，課件共53頁，創(chuàng)作于2023年2月(1) 滿二叉樹(fullbinarytree)一樹中所有葉節(jié)點(diǎn)均在同一階層，而其它非終端節(jié)點(diǎn)(nonterminalnode)之分支度均為2，則此樹為一滿二叉樹。若該樹的高度為h，則此二叉樹的節(jié)點(diǎn)為2h-1。第10頁，課件共53頁，創(chuàng)作于2023年2月(2) 完全二叉樹(completebinarytree)一棵樹扣除掉最大階層那層后為一滿二叉樹，且階層最大那層的節(jié)點(diǎn)均向左靠齊，則該二叉樹稱為完全二叉樹。在一棵深度為k，結(jié)點(diǎn)為n的二叉樹中，對(duì)樹中結(jié)點(diǎn)按從上到下，從左到右的順序編號(hào)，完全二叉樹中編號(hào)為1~n的結(jié)點(diǎn)分別與滿二叉樹中編號(hào)為1~n的結(jié)點(diǎn)位置一一對(duì)應(yīng)。第11頁，課件共53頁，創(chuàng)作于2023年2月7.3二叉樹表示法二叉樹節(jié)點(diǎn)的表示法，常用的有下列3種方法：(1) 二叉樹數(shù)組表示法(2) 二叉樹結(jié)構(gòu)數(shù)組表示法(3) 二叉樹鏈表表示法其中“數(shù)組表示法”和“結(jié)構(gòu)數(shù)組表示法”是屬于靜態(tài)內(nèi)存空間配置，而“鏈表表示法”是利用列表結(jié)構(gòu)的方式，屬于動(dòng)態(tài)內(nèi)存空間配置。第12頁，課件共53頁，創(chuàng)作于2023年2月7.3.1二叉樹數(shù)組表示法對(duì)于一棵滿二叉樹，將其結(jié)點(diǎn)從上到下，從左到右順序編號(hào)，再根據(jù)編號(hào)存入對(duì)應(yīng)下標(biāo)編號(hào)的數(shù)組中。如果該樹不為滿二叉樹，也可對(duì)各節(jié)點(diǎn)編成在滿二叉樹中相同位置之節(jié)點(diǎn)編號(hào)值，再以相同的方式存入數(shù)組中，若某一編號(hào)沒有節(jié)點(diǎn)存在，則不存值于數(shù)組中。假設(shè)一父節(jié)點(diǎn)的編號(hào)為n左子節(jié)點(diǎn)的編號(hào)為：2n，右子節(jié)點(diǎn)的編號(hào)為：2n+1。第13頁，課件共53頁，創(chuàng)作于2023年2月7.3.1二叉樹數(shù)組表示法優(yōu)點(diǎn)：對(duì)于任意一個(gè)節(jié)點(diǎn)都能很容易的找到其父節(jié)點(diǎn)、子節(jié)點(diǎn)及兄弟。缺點(diǎn)：這樣將導(dǎo)致存儲(chǔ)空間的浪費(fèi)，極端的情況是對(duì)于一個(gè)二叉樹，每個(gè)結(jié)點(diǎn)只有右孩子而無左孩子時(shí)，假設(shè)該樹的深度為k，則需要2k-1個(gè)存儲(chǔ)單元，而實(shí)際只利用了其中的k個(gè)存儲(chǔ)單元。第14頁，課件共53頁，創(chuàng)作于2023年2月7.3.3二叉樹鏈表表示法（二叉鏈表）鏈表的節(jié)點(diǎn)結(jié)構(gòu)如下：每個(gè)節(jié)點(diǎn)包含三個(gè)域：數(shù)據(jù)域（Data）：存儲(chǔ)結(jié)點(diǎn)的數(shù)據(jù)內(nèi)容左指針域（left）：指向該節(jié)點(diǎn)的左子樹右指針域（right）：指向該節(jié)點(diǎn)的右子樹由這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)構(gòu)成的二叉樹稱為二叉鏈表。第15頁，課件共53頁，創(chuàng)作于2023年2月7.3.3二叉樹鏈表表示法（二叉鏈表）二叉鏈表結(jié)構(gòu)的聲明如下：strusttree{structtree*left;intdata;structtree*right;}typedefstructtreetreenode;treenode*b_tree;第16頁，課件共53頁，創(chuàng)作于2023年2月7.4二叉樹的遍歷“遍歷”是訪問數(shù)據(jù)結(jié)構(gòu)中的各個(gè)數(shù)據(jù)值，例如：數(shù)組和鏈表可從前端到尾端或從尾端至前端依序訪問各個(gè)數(shù)據(jù)值。而二叉樹是一種特殊的數(shù)據(jù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)其下又各有左、右兩個(gè)分支?！岸鏄涞谋闅v”是以固定的順序，有系統(tǒng)地訪問二叉樹中的各節(jié)點(diǎn)，且每個(gè)節(jié)點(diǎn)均恰好被訪問一次。第17頁，課件共53頁，創(chuàng)作于2023年2月一棵二叉樹由根結(jié)點(diǎn)、左子樹和右子樹三部分組成，若依次遍歷這三部分，也就遍歷了整棵樹。這里用L、D、R分別表示遍歷左子樹、訪問根結(jié)點(diǎn)、遍歷右子樹，。若按照從左到右的順序進(jìn)行遍歷，則有LDR、DLR、LRD三種方式，它們分別稱為中序遍歷、前序遍歷和后序遍歷。第18頁，課件共53頁，創(chuàng)作于2023年2月7.4.1二叉樹的前序遍歷前序遍歷二叉樹的算法為：若二叉樹為空，則遍歷結(jié)束，否則依次執(zhí)行以下操作：（1）訪問根結(jié)點(diǎn)；（2）前序遍歷根結(jié)點(diǎn)的左子樹；（3）前序遍歷根結(jié)點(diǎn)的右子樹。第19頁，課件共53頁，創(chuàng)作于2023年2月其具體算法實(shí)現(xiàn)如下：voidpreorder(b_treepoint){if(point!=NULL)/*遍歷的終止條件*/{printf("%d",point->data);/*處理打印節(jié)點(diǎn)內(nèi)容*/ preorder(point->left); /*處理左子樹*/ preorder(point->right);/*處理右子樹*/}}第20頁，課件共53頁，創(chuàng)作于2023年2月7.4.2二叉樹的中序遍歷中序遍歷二叉樹的算法為：若二叉樹為空，則遍歷結(jié)束，否則依次執(zhí)行以下操作：（1）中序遍歷根結(jié)點(diǎn)的左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷根結(jié)點(diǎn)的右子樹。第21頁，課件共53頁，創(chuàng)作于2023年2月其具體算法實(shí)現(xiàn)如下：voidinorder(b_treepoint){if(point!=NULL) /*遍歷的終止條件*/{inorder(point->left); /*處理左子樹*/printf("%d",point->data); /*處理打印節(jié)點(diǎn)內(nèi)容*/inorder(point->right); /*處理右子樹*/}}第22頁，課件共53頁，創(chuàng)作于2023年2月voidinorder(b_treepoint){if(point==NULL) /*遍歷的終止條件*/return;else{inorder(point->left); /*處理左子樹*/printf("%d",point->data); /*處理打印節(jié)點(diǎn)內(nèi)容*/inorder(point->right); /*處理右子樹*/}}第23頁，課件共53頁，創(chuàng)作于2023年2月7.4.3二叉樹的后序遍歷后序遍歷二叉樹的算法為：若二叉樹為空，則遍歷結(jié)束，否則依次執(zhí)行以下操作：（1）后序遍歷根結(jié)點(diǎn)的左子樹；（2）后序遍歷根結(jié)點(diǎn)的右子樹；（3）訪問根結(jié)點(diǎn)。第24頁，課件共53頁，創(chuàng)作于2023年2月其具體算法實(shí)現(xiàn)如下：voidpostorder(b_treepoint){if(point!=NULL) /*遍歷的終止條件*/{postorder(point->left); /*處理左子樹*/postorder(point->right); /*處理右子樹*/printf("%d",point->data); /*處理打印節(jié)點(diǎn)內(nèi)容*/}}第25頁，課件共53頁，創(chuàng)作于2023年2月【例】有一棵二叉樹的前序遍歷序列為A、C、I、K、N、H、L、M，中序遍歷序列為I、C、N、K、A、L、M、H，試畫出此二叉樹。由于在前序遍歷中首先訪問根節(jié)點(diǎn)，因此，前序序列中的第一個(gè)結(jié)點(diǎn)為二叉樹的根節(jié)點(diǎn)，即A為二叉樹的根節(jié)點(diǎn)。又由于在中序遍歷中訪問根節(jié)點(diǎn)的次序?yàn)榫又?，左子樹的?jié)點(diǎn)居前，右子樹的節(jié)點(diǎn)居后，因此，在中序序列中，以根結(jié)點(diǎn)（A）為分界線，前面的子序列（I、C、N、K）一定在左子樹中，后面的子序列（L、M、H）一定在右子樹中。同樣的道理，對(duì)于已經(jīng)劃分出的每一個(gè)子序列的所有節(jié)點(diǎn)中，位于前序序列最前面的一個(gè)節(jié)點(diǎn)為子樹的根節(jié)點(diǎn)，而在中序序列中位于該根節(jié)點(diǎn)前面的節(jié)點(diǎn)構(gòu)成左子樹的節(jié)點(diǎn)子序列，位于該根節(jié)點(diǎn)后面的節(jié)點(diǎn)構(gòu)成右子樹的節(jié)點(diǎn)子序列。按此規(guī)則不斷循環(huán)下去，直到所有的子序列為單個(gè)節(jié)點(diǎn)為止，其求解過程如圖所示。第26頁，課件共53頁，創(chuàng)作于2023年2月第27頁，課件共53頁，創(chuàng)作于2023年2月7.5二叉樹的建立(遞歸法)給定一個(gè)二叉樹數(shù)組結(jié)構(gòu)，使用遞歸方式建立一棵二叉樹，并以中序遍歷的方式輸出二叉樹節(jié)點(diǎn)內(nèi)容。第28頁，課件共53頁，創(chuàng)作于2023年2月b_treecreate_btree(int*nodelist,intposition){b_treenewnode;/*聲明新節(jié)點(diǎn)指針*/

if(nodelist[position]==0||position>15)/*遞歸的終止條件*/returnNULL;else{/*-----建立新節(jié)點(diǎn)的內(nèi)存空間----*/newnode=(b_tree)malloc(sizeof(treenode));

/*-------------建立節(jié)點(diǎn)內(nèi)容--------------*/newnode->data=nodelist[position];/*------------遞歸建立左子樹------------*/newnode->left=create_btree(nodelist,2*position);/*------------遞歸建立右子樹------------*/newnode->right=create_btree(nodelist,2*position+1);returnnewnode; /*返回復(fù)制樹的位置*/}}第29頁，課件共53頁，創(chuàng)作于2023年2月7.8二叉樹的復(fù)制使用遞歸方式建立二叉樹，再復(fù)制原來的二叉樹，并輸出原本的二叉樹和備份二叉樹的節(jié)點(diǎn)內(nèi)容。第30頁，課件共53頁，創(chuàng)作于2023年2月b_treecopy_btree(b_treeroot){b_treenewnode;/*聲明新節(jié)點(diǎn)指針*/

if(root==NULL) /*遞歸的終止條件*/returnNULL;else{/*-----建立新節(jié)點(diǎn)的內(nèi)存空間----*/newnode=(b_tree)malloc(sizeof(treenode));/*-------------建立節(jié)點(diǎn)內(nèi)容--------------*/newnode->data=root->data;/*------------遞歸建立左子樹------------*/newnode->left=copy_btree(root->left);/*------------遞歸建立右子樹------------*/newnode->right=copy_btree(root->right);returnnewnode; /*返回復(fù)制樹的位置*/}}第31頁，課件共53頁，創(chuàng)作于2023年2月7.6二叉查找樹二叉查找樹(Binarysearchtree)的條件：每個(gè)節(jié)點(diǎn)的數(shù)據(jù)要大于左子節(jié)點(diǎn)的數(shù)據(jù)，且要小于右子節(jié)點(diǎn)的數(shù)據(jù)。具體來說：（1）若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值；（2）若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值；（3）左、右子樹本身也分別為二叉查找樹；第32頁，課件共53頁，創(chuàng)作于2023年2月二叉查找樹的性質(zhì)：（1）二叉查找樹中任一結(jié)點(diǎn)x，其左(右)子樹中任一結(jié)點(diǎn)y(若存在)的關(guān)鍵字必小(大)于x的關(guān)鍵字；（2）二叉查找樹中，各結(jié)點(diǎn)關(guān)鍵字是惟一的（3）按中序遍歷該樹所得到的中序序列是一個(gè)遞增有序序列。第33頁，課件共53頁，創(chuàng)作于2023年2月7.6二叉查找樹(二叉查找樹的插入)二叉查找樹的插入：以第一個(gè)元素為根節(jié)點(diǎn)依序?qū)⒃刂蹬c根節(jié)點(diǎn)做比較若元素值大于根節(jié)點(diǎn)值，則將該元素值往根節(jié)點(diǎn)之右子節(jié)點(diǎn)移動(dòng)，若此右子節(jié)點(diǎn)為空，則將元素值存入，否則就重復(fù)比較，直到找到適當(dāng)?shù)目展?jié)點(diǎn)為止。若元素值小于根節(jié)點(diǎn)值，則將該元素值往根節(jié)點(diǎn)之左子節(jié)點(diǎn)移動(dòng)，若此左子節(jié)點(diǎn)為空，則將元素值存入，否則就重復(fù)比較，直到找到適當(dāng)?shù)目展?jié)點(diǎn)為止。第34頁，課件共53頁，創(chuàng)作于2023年2月b_treeinsert_node(b_treeroot,intnode){/*聲明樹根指針*//*聲明目前節(jié)點(diǎn)指針*//*聲明父節(jié)點(diǎn)指針*//*建立新節(jié)點(diǎn)的內(nèi)存空間*/newnode=(b_tree)malloc(sizeof(treenode));/*存入節(jié)點(diǎn)內(nèi)容*//*設(shè)置右指針初值*//*設(shè)置左指針初值*/if(root==NULL)returnnewnode;/*返回新節(jié)點(diǎn)的位置*/else{currentnode=root;/*存儲(chǔ)目前節(jié)點(diǎn)指針*/while(currentnode!=NULL){parentnode=currentnode;/*存儲(chǔ)父節(jié)點(diǎn)指針*/if(currentnode->data>node)/*比較節(jié)點(diǎn)的數(shù)值大小*/ currentnode=currentnode->left;/*左子樹*/elsecurrentnode=currentnode->right;/*右子樹*/}if(parentnode->data>node)/*將父節(jié)點(diǎn)和子節(jié)點(diǎn)做連結(jié)*/parentnode->left=newnode;/*子節(jié)點(diǎn)為父節(jié)點(diǎn)之左子樹*/elseparentnode->right=newnode;/*子節(jié)點(diǎn)為父節(jié)點(diǎn)之右子樹*/}returnroot;/*返回根節(jié)點(diǎn)之指針*/}第35頁，課件共53頁，創(chuàng)作于2023年2月二叉查找樹的生成二叉查找樹的生成，是從空的二叉查找樹開始，每輸入一個(gè)結(jié)點(diǎn)數(shù)據(jù)，就調(diào)用一次插入算法將它插入到當(dāng)前已生成的二叉查找樹中。第36頁，課件共53頁，創(chuàng)作于2023年2月二叉查找樹的生成算法b_treecreate_btree(int*data,intlen){b_treeroot=NULL; /*根節(jié)點(diǎn)指針*/inti;for(i=0;i<len;i++) /*建立樹狀結(jié)構(gòu)*/root=insert_node(root,data[i]);returnroot;}第37頁，課件共53頁，創(chuàng)作于2023年2月7.6.2二叉樹的查找方法在二叉查找樹上進(jìn)行查找是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判斷是否相等的過程。即當(dāng)二叉查找樹非空時(shí)，將給定值和根結(jié)點(diǎn)關(guān)鍵值比較：若相等，則查找成功，返回找到結(jié)點(diǎn)的地址；否則根據(jù)給定值與根結(jié)點(diǎn)關(guān)鍵字之間的大小關(guān)系，分別在左子樹或右子樹上繼續(xù)查找，直到左子樹或右子樹空為止，此時(shí)查找失敗，返回空值。第38頁，課件共53頁，創(chuàng)作于2023年2月b_treebtree_traversal_search(b_treepoint,intfindnode){while(point!=NULL){if(point->data==findnode)/*找到了欲尋找的節(jié)點(diǎn)*/returnpoint;/*返回找到節(jié)點(diǎn)的指針*/elseif(point->data>findnode) point=point->left; /*往左子樹找*/else point=point->right; /*往右子樹找*/}returnNULL;/*該節(jié)點(diǎn)不在此二叉樹中*/}第39頁，課件共53頁，創(chuàng)作于2023年2月7.7二叉樹(二叉查找樹)的節(jié)點(diǎn)刪除對(duì)于一個(gè)二叉樹，若欲刪除其節(jié)點(diǎn)，應(yīng)先尋找欲刪除的節(jié)點(diǎn)是否存在于該二叉樹中。關(guān)于二叉樹的節(jié)點(diǎn)查找，前面已有詳細(xì)的介紹，本節(jié)將說明如何將節(jié)點(diǎn)從二叉樹中刪除。由于我們?cè)趧h除一個(gè)節(jié)點(diǎn)后，必須要維持滿足二叉查找樹數(shù)據(jù)排列的原則：左子節(jié)點(diǎn)<節(jié)點(diǎn)<右子節(jié)點(diǎn)。而刪除節(jié)點(diǎn)的處理可分4種情況，我們將對(duì)各種情況做詳細(xì)的說明。第40頁，課件共53頁，創(chuàng)作于2023年2月7.7.1節(jié)點(diǎn)無左子樹，無右子樹當(dāng)欲刪除一無左子樹也無右子樹的節(jié)點(diǎn)時(shí)，需要考慮到兩種情況：(1)為根節(jié)點(diǎn)如欲刪除無左、右子樹的根節(jié)點(diǎn)，只需將根節(jié)點(diǎn)指針root指向NULL即可。(2)非根節(jié)點(diǎn)若一節(jié)點(diǎn)為無左、右子樹的非根節(jié)點(diǎn)，那么該節(jié)點(diǎn)必為葉節(jié)點(diǎn)。如果節(jié)點(diǎn)為父節(jié)點(diǎn)的左子節(jié)點(diǎn)，則將父節(jié)點(diǎn)的左指針指向NULL，相同地，若節(jié)點(diǎn)為父節(jié)點(diǎn)的右子節(jié)點(diǎn)，則將父節(jié)點(diǎn)的右指針指向NULL。第41頁，課件共53頁，創(chuàng)作于2023年2月7.7.2節(jié)點(diǎn)有左子樹，無右子樹當(dāng)欲刪除一有左子樹但無右子樹的節(jié)點(diǎn)時(shí)，也需去考慮兩種情況：(1)為根節(jié)點(diǎn)欲刪除有左子樹，無右子樹之根節(jié)點(diǎn)，只需將根節(jié)點(diǎn)指針root指向其左子樹。(2)非根節(jié)點(diǎn)一節(jié)點(diǎn)為左子樹，無右子樹的非根節(jié)點(diǎn)，若節(jié)點(diǎn)為父節(jié)點(diǎn)的左子節(jié)點(diǎn)，則將父節(jié)點(diǎn)的左指針指向節(jié)點(diǎn)的左子節(jié)點(diǎn)，相同地，若節(jié)點(diǎn)為父節(jié)點(diǎn)的右子節(jié)點(diǎn)，則將父節(jié)點(diǎn)的右指針指向節(jié)點(diǎn)的左子節(jié)點(diǎn)。第42頁，課件共53頁，創(chuàng)作于2023年2月7.7.3節(jié)點(diǎn)無左子樹，有右子樹如圖中節(jié)點(diǎn)8。第43頁，課件共53頁，創(chuàng)作于2023年2月7.7.4節(jié)點(diǎn)有左子樹，有右子樹需要找一個(gè)替代的節(jié)點(diǎn)值，以免大量的移動(dòng)節(jié)點(diǎn)找節(jié)點(diǎn)左子樹的最右邊的點(diǎn)找節(jié)點(diǎn)右子樹最左邊的點(diǎn)第44頁，課件共53頁，創(chuàng)作于2023年2月7.12引線二叉樹(線索二叉樹)具有n個(gè)結(jié)點(diǎn)的二叉樹，其二叉鏈表中共有2n個(gè)指針域。由于除根結(jié)點(diǎn)外，對(duì)于每個(gè)結(jié)點(diǎn)都有一個(gè)指針指向該結(jié)點(diǎn)，因此實(shí)際只有n-1個(gè)指針域被使用，而另外n+1個(gè)指針域是空的，可以利用這n+1個(gè)空指針存放某種遍歷方式下指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針，這種附加的指針稱為“引線”，加上了引線的二叉樹稱為引線二叉樹。第45頁，課件共53頁，創(chuàng)作于2023年2月Lchild是指針，指向結(jié)點(diǎn)的左子結(jié)點(diǎn)Lchild是引線，指向結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)Rchild是指針，指向結(jié)點(diǎn)的右子結(jié)點(diǎn)Rchild是印線，指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)第46頁，課件共53頁，創(chuàng)作于2023年2月structthread_tree{intdata;/*節(jié)點(diǎn)數(shù)據(jù)*/structthread_tree*Lchild;/*左指針*/structthread_tree*Rchild;/*右指針*/intLthread;/*標(biāo)示是否為左引線*/intRthread;/*標(biāo)示是否為右引線*/};typedefstructthread_treetreenode;/*定義新類型樹狀結(jié)構(gòu)*/typedeftreenode*t_btree;第47頁，課件共53頁，創(chuàng)作于2023年2月引線二叉樹的建立方式了解引線二叉樹的節(jié)點(diǎn)結(jié)構(gòu)及聲明方法后，則要進(jìn)一步說明引線二叉樹的建立方式。事實(shí)上，引線二叉樹的建立方式和一般二叉樹相同，只是要額外考慮指針字段和引線字段的內(nèi)容，規(guī)則如下：if左指針為空then Lchild指到在該樹中序遍歷的前一個(gè)節(jié)點(diǎn) 將Lthread設(shè)為1if右指針為空then