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

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

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

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

/*-------------建立節(jié)點內(nèi)容--------------*/newnode->data=nodelist[position];/*------------遞歸建立左子樹------------*/newnode->left=create_btree(nodelist,2*position);/*------------遞歸建立右子樹------------*/newnode->right=create_btree(nodelist,2*position+1);returnnewnode; /*返回復(fù)制樹的位置*/}}第二十九頁，共五十三頁，編輯于2023年，星期四7.8二叉樹的復(fù)制使用遞歸方式建立二叉樹，再復(fù)制原來的二叉樹，并輸出原本的二叉樹和備份二叉樹的節(jié)點內(nèi)容。第三十頁，共五十三頁，編輯于2023年，星期四b_treecopy_btree(b_treeroot){b_treenewnode;/*聲明新節(jié)點指針*/

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