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

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

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

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

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