數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)課件章節(jié)5

第5章樹與二叉樹5.1樹5.1.1樹的定義樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n(n≥0)個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。空集合也是樹，稱為空樹。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：每個(gè)結(jié)點(diǎn)有零個(gè)或多個(gè)子結(jié)點(diǎn)；沒有父結(jié)點(diǎn)的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；每一個(gè)非根結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)；除了根結(jié)點(diǎn)外，每個(gè)子結(jié)點(diǎn)可以分為多個(gè)不相交的子樹。樹是由根結(jié)點(diǎn)和若干顆子樹構(gòu)成的。樹是由一個(gè)集合以及在該集合上定義的一種關(guān)系構(gòu)成的。集合中的元素稱為樹的結(jié)點(diǎn)，所定義的關(guān)系稱為父子關(guān)系。父子關(guān)系在樹的結(jié)點(diǎn)之間建立了一個(gè)層次結(jié)構(gòu)。在這種層次結(jié)構(gòu)中有一個(gè)結(jié)點(diǎn)具有特殊的地位，這個(gè)結(jié)點(diǎn)稱為該樹的根結(jié)點(diǎn)，或稱為樹根。5.1.2樹的基本術(shù)語下面根據(jù)下圖來介紹關(guān)于樹的基本術(shù)語和概念。孩子結(jié)點(diǎn)或子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)含有的子樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)含有的子結(jié)點(diǎn)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。葉結(jié)點(diǎn)或終端結(jié)點(diǎn)：度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)。非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。雙親結(jié)點(diǎn)或父結(jié)點(diǎn)：若一個(gè)結(jié)點(diǎn)含有子結(jié)點(diǎn)，則這個(gè)結(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)的層次：從根開始定義起，根為第1層，根的子結(jié)點(diǎn)為第2層，以此類推。樹的高度或深度：樹中結(jié)點(diǎn)的最大層次。堂兄弟結(jié)點(diǎn)：雙親在同一層的結(jié)點(diǎn)互為堂兄弟。結(jié)點(diǎn)的祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。子孫：以某結(jié)點(diǎn)為根的子樹中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。有序樹：如果樹中各棵子樹的次序是有先后次序，則稱該樹為有序樹。無序樹：如果樹中各棵子樹的次序沒有先后次序，則稱該樹為無序樹。森林：由各棵互不相交的樹的集合稱為森林。路徑和路徑長度：樹中兩個(gè)結(jié)點(diǎn)之間的路徑是由這兩個(gè)結(jié)點(diǎn)之間所經(jīng)過的結(jié)點(diǎn)序列構(gòu)成的，而路徑長度是路徑上所經(jīng)過邊的個(gè)數(shù)。5.1.3樹的種類無序樹：樹中任意結(jié)點(diǎn)的子結(jié)點(diǎn)之間沒有順序關(guān)系，這種樹稱為無序樹,也稱為自由樹。有序樹：樹中任意結(jié)點(diǎn)的子結(jié)點(diǎn)之間有順序關(guān)系，這種樹稱為有序樹。二叉樹：每個(gè)結(jié)點(diǎn)最多含有兩個(gè)子樹的樹稱為二叉樹。滿二叉樹：葉結(jié)點(diǎn)除外的所有結(jié)點(diǎn)均含有兩個(gè)子樹的樹被稱為滿二叉樹。完全二叉樹：除最后一層外，所有層都是滿結(jié)點(diǎn)，且最后一層缺右邊連續(xù)結(jié)點(diǎn)的二叉樹稱為完全二叉樹。哈夫曼樹（最優(yōu)二叉樹）：帶權(quán)路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹。5.1.4樹的性質(zhì)樹具有如下最基本的性質(zhì)：1）樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加上1。2）度為m的樹中第i層上至多有mi-1個(gè)結(jié)點(diǎn)（i≥1）。3）高度為h的m叉樹至多有(mh-1)/(m-1)個(gè)結(jié)點(diǎn)。4）具有n個(gè)結(jié)點(diǎn)的m叉樹的最小高度為?logm(n(m-1)+1)?。5.2二叉樹5.2.1二叉樹的定義及特性1．二叉樹的定義二叉樹（Binarytree）是樹形結(jié)構(gòu)的一個(gè)重要類型。許多實(shí)際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹形式，即使是一般的樹也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹，而且二叉樹的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此二叉樹顯得特別重要。二叉樹特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹，且有左右之分，如圖所示。二叉樹是n個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根（root）的元素及兩個(gè)不相交的、被分別稱為左子樹和右子樹的二叉樹組成，是有序樹。當(dāng)集合為空時(shí)，稱該二叉樹為空二叉樹。在二叉樹中，一個(gè)元素也稱作一個(gè)結(jié)點(diǎn)。不能把二叉樹與度為2的有序樹等同起來。它們之間有如下幾個(gè)區(qū)別：①度為2的有序樹至少有3個(gè)結(jié)點(diǎn)，而二叉樹可以為空。②度為2的有序樹的左右次序是相對(duì)另一個(gè)孩子而言的，若某個(gè)結(jié)點(diǎn)只有一個(gè)孩子，則這個(gè)孩子就不需要區(qū)分左右次序；而二叉樹無論其孩子數(shù)是否為2，都需要確認(rèn)其左右次序，二叉樹的結(jié)點(diǎn)次序是確定的。2．幾種特殊二叉樹二叉樹還有以下幾種特殊類型：1）滿二叉樹：如果一棵二叉樹只有度為0的結(jié)點(diǎn)和度為2的結(jié)點(diǎn)，并且度為0的結(jié)點(diǎn)在同一層上，則這棵二叉樹為滿二叉樹。一顆高度為h的滿二叉樹含有2h–1個(gè)結(jié)點(diǎn)，即樹中的每一層都含有最多的結(jié)點(diǎn)，如圖(a)所示。2）完全二叉樹：高度為h，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與高度為h的滿二叉樹中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹，如圖(b)所示。3）二叉排序樹：左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字；右子樹上所有結(jié)點(diǎn)的關(guān)鍵字均大于根結(jié)點(diǎn)的關(guān)鍵字；左子樹和右子樹又各是一棵二叉排序樹，如圖所示。4）平衡二叉樹：根上任一結(jié)點(diǎn)的左子樹和右子樹的深度之差不超過1，如圖所示。3．二叉樹性質(zhì)性質(zhì)1：二叉樹的第i層上至多有2i-1（i≥1）個(gè)結(jié)點(diǎn)。性質(zhì)2：深度為h（h≥1）的二叉樹中至多含有2h-1個(gè)結(jié)點(diǎn)。性質(zhì)3：若在任意一棵二叉樹中，有n0個(gè)葉子結(jié)點(diǎn)，有n2個(gè)度為2的結(jié)點(diǎn)，則必有n0=n2+1。證明：設(shè)度為0，1和2的結(jié)點(diǎn)個(gè)數(shù)分別為n0，n1和n2，結(jié)點(diǎn)總數(shù)n=n0+n1+n2。在二叉樹的分支數(shù)中，除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)分支進(jìn)入，設(shè)A為分支總數(shù)，則n=A+1。由于這些分支都是由度為1或2的結(jié)點(diǎn)射出的，所有A=n1+2n2。于是可得n0+n1+n2=n1+2n2+1，化簡(jiǎn)后得n0=n2+1。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹高度為?log2(n+1)?或?log2n?+1。性質(zhì)5：若對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹進(jìn)行順序編號(hào)（0≤i＜n），那么，對(duì)于編號(hào)為i（i≥0）的結(jié)點(diǎn)：當(dāng)i=0時(shí)，該結(jié)點(diǎn)為根，它無雙親結(jié)點(diǎn)。當(dāng)i>0時(shí)，該結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為?(i–1)/2?。若2i+1＜n，則有編號(hào)為2i+1的左結(jié)點(diǎn)，否則沒有左結(jié)點(diǎn)。若2i+2＜n，則有編號(hào)為2i+2的右結(jié)點(diǎn)，否則沒有右結(jié)點(diǎn)。5.2.2二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹一般都采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用鏈表結(jié)點(diǎn)來存儲(chǔ)二叉樹中的每個(gè)結(jié)點(diǎn)。在二叉樹中，結(jié)點(diǎn)結(jié)構(gòu)通常包括若干數(shù)據(jù)域和若干指針域，二叉鏈表至少包含3個(gè)域：數(shù)據(jù)域data，左指針域lchild和右指針域rchild，如圖所示。二叉樹結(jié)點(diǎn)類的存儲(chǔ)結(jié)構(gòu)描述如下：二叉樹類的存儲(chǔ)結(jié)構(gòu)描述如下：5.2.3二叉樹的遍歷遍歷是對(duì)樹的一種最基本的運(yùn)算，所謂遍歷二叉樹，就是按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被訪問一次，而且只被訪問一次。由于二叉樹是非線性結(jié)構(gòu)，因此，樹的遍歷實(shí)質(zhì)上是將二叉樹的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列來表示。1．先序遍歷先序遍歷（PreOrder）的操作過程如下：若二叉樹為空，則什么也不做，否則，

1）訪問根結(jié)點(diǎn)；

2）先序遍歷左子樹；

3）先序遍歷右子樹。先序遍歷的遞歸算法如下：在圖中所表示的二叉樹中，先序遍歷所得到的結(jié)點(diǎn)序列為124563。2．中序遍歷中序遍歷（InOrder）的操作過程如下：若二叉樹為空，則什么也不做，否則，

1）中序遍歷左子樹；

2）訪問根結(jié)點(diǎn)；3）中序遍歷右子樹。中序遍歷的遞歸算法如下：在圖中所表示的二叉樹中，中序遍歷所得到的結(jié)點(diǎn)序列為426513。3．后序遍歷后序遍歷（PostOrder）的操作過程如下：若二叉樹為空，則什么也不做，否則，

1）后序遍歷左子樹；

2）后序遍歷右子樹；

3）訪問根結(jié)點(diǎn)。后序遍歷的遞歸算法如下：在圖中所表示的二叉樹中，后序遍歷所得到的結(jié)點(diǎn)序列為465231。4．層次遍歷二叉樹的層次遍歷，按照層次順序?qū)Χ鏄涞母鱾€(gè)結(jié)點(diǎn)進(jìn)行訪問，如圖。用一個(gè)隊(duì)列保存被訪問的當(dāng)前結(jié)點(diǎn)的左右孩子以實(shí)現(xiàn)層序遍歷。在進(jìn)行層次遍歷的時(shí)候，設(shè)置一個(gè)隊(duì)列結(jié)構(gòu)，遍歷從二叉樹的根結(jié)點(diǎn)開始，首先將根結(jié)點(diǎn)指針入隊(duì)列，然后從隊(duì)頭取出一個(gè)元素，每取一個(gè)元素，執(zhí)行下面兩個(gè)操作：1、訪問該元素所指向的結(jié)點(diǎn)2、若該元素所指結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)非空，則將該元素所指結(jié)點(diǎn)的左孩子指針和右孩子指針順序入隊(duì)。此過程不斷進(jìn)行，當(dāng)隊(duì)列為空時(shí)，二叉樹的層次遍歷結(jié)束。二叉樹的層次遍歷算法如下：5．由遍歷序列構(gòu)造二叉樹由二叉樹的先序序列和中序序列可以唯一地確定一棵二叉樹。由二叉樹的后序序列和中序序列可以唯一地確定一棵二叉樹。只知道二叉樹的先序序列和后序序列無法唯一確定一棵二叉樹。5.2.4二叉排序樹（BST）1．二叉排序樹的定義二叉排序樹（BinarySortTree），又稱二叉查找樹（BinarySearchTree），亦稱二叉搜索樹。是數(shù)據(jù)結(jié)構(gòu)中的一類。在一般情況下，查詢效率比鏈表結(jié)構(gòu)要高。二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；3）左、右子樹也分別為二叉排序樹；4）沒有鍵值相等的結(jié)點(diǎn)。根據(jù)二叉排序樹的定義，左子樹結(jié)點(diǎn)值＜根結(jié)點(diǎn)值＜右子樹結(jié)點(diǎn)值，所以對(duì)二叉排序樹進(jìn)行中序遍歷會(huì)得到一個(gè)遞增的有序序列。如圖所示，該二叉排序樹的中序遍歷序列為135679。2．二叉排序樹的查找二叉排序樹的查找從根結(jié)點(diǎn)開始，沿某個(gè)分支逐層向下比較的過程。若二叉排序樹非空，先將給定值與根結(jié)點(diǎn)的關(guān)鍵字比較，若相等，則查找成功；若不相等，如果小于根結(jié)點(diǎn)的關(guān)鍵字，則在根結(jié)點(diǎn)的左子樹上查找，否則在根結(jié)點(diǎn)的右子樹上查找。二叉排序樹的查找算法如下：二叉樹排序樹的查找效率主要取決于樹的高度。若二叉排序樹的左、右子樹的高度之差的絕對(duì)值不超過1，則這樣的二叉排序樹成為平衡二叉樹，它的平均查找長度為O(log2n)。若二叉排序樹是一個(gè)只有右（左）孩子的單支樹，則其平均查找長度為O(n)。3．二叉排序樹的插入二叉排序樹是一種動(dòng)態(tài)樹表。其特點(diǎn)是：樹的結(jié)構(gòu)通常不是一次生成的，而是在查找過程中，當(dāng)樹中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。插入結(jié)點(diǎn)的過程如下：首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)；判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子；將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。若二叉樹為空，則首先單獨(dú)生成根結(jié)點(diǎn)。二叉排序樹的插入操作算法如下：4．二叉排序樹的構(gòu)造從一棵空數(shù)開始，依次輸入元素，把它們插入到二叉排序樹的合適位置。構(gòu)造二叉排序樹的算法如下：5.2.5平衡二叉樹平衡二叉樹（BalanceBinaryTree），由前蘇聯(lián)的數(shù)學(xué)家Adelse-Velskil和Landis在1962年提出的高度平衡的二叉樹，根據(jù)科學(xué)家的英文名也稱為AVL樹。它具有如下幾個(gè)性質(zhì)：1）可以是空樹。2）假如不是空樹，任何一個(gè)結(jié)點(diǎn)的左子樹與右子樹都是平衡二叉樹，并且高度之差的絕對(duì)值不超過1。定義結(jié)點(diǎn)左子樹和右子樹的高度差為該結(jié)點(diǎn)的平衡因子，則平衡二叉樹結(jié)點(diǎn)的平衡因子值只可能為-1、0或1，如圖所示。5.2.6哈夫曼樹1．哈夫曼樹的定義給定N個(gè)權(quán)值作為N個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(HuffmanTree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點(diǎn)離根較近。哈夫曼樹是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度為葉結(jié)點(diǎn)的層數(shù)）。樹的路徑長度是從樹根到每一結(jié)點(diǎn)的路徑長度之和，記為WPL（WeightedPathLengthofTree）=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N個(gè)權(quán)值Wi（i=1,2,...n）構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹，相應(yīng)的葉結(jié)點(diǎn)的路徑長度為Li（i=1,2,...n）。例如右圖的哈夫曼樹中，該樹的WPL=8*1+5*2+2*3+3*3=33。同時(shí)該樹的WPL在所有帶這4個(gè)結(jié)點(diǎn)的二叉樹中里為最小值。2.哈夫曼樹的構(gòu)造假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)。n個(gè)權(quán)值分別設(shè)為w1、w2、…、wn，則哈夫曼樹的構(gòu)造規(guī)則為：1）將w1、w2、…、wn看成是有n棵樹的森林(每棵樹僅有一個(gè)結(jié)點(diǎn))；2）在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點(diǎn)權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和；3）從森林中刪除選取的兩棵樹，并將新樹加入森林；4）重復(fù)（2）、（3）步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹，如圖所示。構(gòu)造哈夫曼樹的算法如下：3．哈夫曼編碼在數(shù)據(jù)通信中，需要將傳送的文字轉(zhuǎn)換成二進(jìn)制的字符串，用0，1碼的不同排列來表示字符。例如，需傳送的報(bào)文為“AFTERDATAEARAREARTAREA”，這里用到的字符集為“A，E，R，T，F(xiàn)，D”，各字母出現(xiàn)的次數(shù)為{8，4，5，3，1，1}?，F(xiàn)要求為這些字母設(shè)計(jì)編碼。要區(qū)別6個(gè)字母，最簡(jiǎn)單的二進(jìn)制編碼方式是等長編碼，固定采用3位二進(jìn)制，可分別用000、001、010、011、100、101對(duì)“A，E，R，T，F(xiàn)，D”進(jìn)行編碼發(fā)送，當(dāng)對(duì)方接收?qǐng)?bào)文時(shí)再按照三位一分進(jìn)行譯碼。顯然編碼的長度取決報(bào)文中不同字符的個(gè)數(shù)。若報(bào)文中可能出現(xiàn)26個(gè)不同字符，則固定編碼長度為5。然而，傳送報(bào)文時(shí)總是希望總長度盡可能短。在實(shí)際應(yīng)用中，各個(gè)字符的出現(xiàn)頻度或使用次數(shù)是不相同的，如A、B、C的使用頻率遠(yuǎn)遠(yuǎn)高于X、Y、Z，自然會(huì)想到設(shè)計(jì)編碼時(shí)，讓使用頻率高的用短碼，使用頻率低的用長碼，以優(yōu)化整個(gè)報(bào)文編碼。為使不等長編碼為前綴編碼（即要求一個(gè)字符的編碼不能是另一個(gè)字符編碼的前綴），可用字符集中的每個(gè)字符作為葉子結(jié)點(diǎn)生成一棵編碼二叉樹，為了獲得傳送報(bào)文的最短長度，可將每個(gè)字符的出現(xiàn)頻率作為字符結(jié)點(diǎn)的權(quán)值賦予該結(jié)點(diǎn)上，顯然字使用頻率越小權(quán)值越小，權(quán)值越小葉子就越靠下，于是頻率小編碼長，頻率高編碼短，這樣就保證了此樹的最小帶權(quán)路徑長度效果上就是傳送報(bào)文的最短長度。因此，求傳送報(bào)文的最短長度問題轉(zhuǎn)化為求由字符集中的所有字符作為葉子結(jié)點(diǎn)，由字符出現(xiàn)頻率作為其權(quán)值所產(chǎn)生的哈夫曼樹的問題。利用哈夫曼樹來設(shè)計(jì)二進(jìn)制的前綴編碼，既滿足前綴編碼的條件，又保證報(bào)文編碼總長最短，如圖。5.3樹與森林5.3.1樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)方式有多種，既能采用順序存儲(chǔ)結(jié)構(gòu)，也能采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，但無論采用哪種存儲(chǔ)方式，都必須要滿足能夠唯一地反映樹中各結(jié)點(diǎn)之間的邏輯關(guān)系，下面介紹3種常用的存儲(chǔ)結(jié)構(gòu)。1．雙親表示法雙親表示法采用順序存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)，采用一組連續(xù)空間才存儲(chǔ)每個(gè)結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)增設(shè)一個(gè)變量，該變量值為其雙親結(jié)點(diǎn)在列表中的索引位置，如圖所示。該存儲(chǔ)結(jié)構(gòu)利用了每個(gè)結(jié)點(diǎn)（除根節(jié)點(diǎn)外）只有唯一一個(gè)雙親的性質(zhì)，可以很快得到每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)，但求結(jié)點(diǎn)的孩子時(shí)則需要遍歷整個(gè)順序表。2．孩子表示法孩子表示法是將每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)都用單鏈表鏈接起來形成一個(gè)線性結(jié)構(gòu)，此時(shí)n個(gè)結(jié)點(diǎn)就有n個(gè)孩子鏈表（葉子結(jié)點(diǎn)的孩子鏈表為空表）。使用孩子表示法來表示圖(a)中的樹，如圖所示。孩子表示法尋找子女的操作非常直接，但尋找雙親的操作需要遍歷n個(gè)結(jié)點(diǎn)中的孩子鏈表指針域所指向的n個(gè)孩子鏈表。3．孩子兄弟表示法 孩子兄弟表示法又稱二叉樹表示法，即以二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)。孩子兄弟表示法中，每個(gè)結(jié)點(diǎn)包括三個(gè)部分內(nèi)容：結(jié)點(diǎn)值、指向結(jié)點(diǎn)第一個(gè)孩子結(jié)點(diǎn)的指針和指向結(jié)點(diǎn)下一個(gè)兄弟結(jié)點(diǎn)的指針。用孩子兄弟表示法來表示圖