資料結構導論之第四章樹-有解無憂

一、樹的基本概念

　　樹型結構是一類重要的非線性結構，樹型結構是結點之間有分支，并且具有層次關系的結構，它非常類似于自然界中的樹，樹結構在客觀世界中是大量存在的，例如家譜、行政組織機構都可用樹形象地表示；樹在計算機領域中也有著廣泛的應用，例如在編譯程式中，用樹來表示源程式的語法結構；在資料庫系統中，可用樹來組織資訊；在分析演算法的行為時，可用樹來描述其執行程序等等，

遞回是樹的固有特性；

樹：是n(n>=0)個結點的有限集T，滿足：

(1)當n=0時，稱為空樹；
(2)當n>0時，有且僅有一個特定的稱為根的結點；其余的結點可分為m(m>=0)個互不相交的子集T1,T2,T3…Tm，其中每個子集 Ti 又是一棵樹，并稱其為子樹，

●結點：由一個資料元素及若干指向其它結點的分支所組成，
●度：結點的度：所擁有的子樹的數目;樹的度：樹中所有結點的度的最大值
●葉子（終端結點）：度為0的結點
●非終端結點：度不為0的結點，
●孩子（子結點）：結點的子樹的根稱為該結點的孩子，
●雙親（父結點）：一個結點稱為該結點所有子樹根的雙親
●祖先結點：祖先指根到此結點的一條路徑上的所有結點，
●子孫結點：從某結點到葉結點的分支上的所有結點稱為該結點的子孫，
●兄弟結點：同一雙親的孩子之間互稱兄弟，（父結點相同的結點）
●結點的層次：從根開始算起，根的層次為1,其余結點的層次為其雙親的層次加1，
●堂兄弟：其雙親在同一層的結點，
●樹的深度（高度）：一棵樹中所有結點層次數的最大值，
●有序樹：若樹中各結點的子樹從左到右是有次序的，不能互換，稱為有序樹，
●無序樹：若樹中各結點的子樹是無次序的，可以互換，則成為無序樹，
●森林：是m（≥0）棵樹的集合，

對于任何一棵樹：節點數=分支數+1

例如：在一顆度為3的樹中，度為3的結點有4個，度為2的結點有2個，度為1的結點有3個，，則度為0的節點有幾個

節點數=分支數+1=》4+2+3+n=3*4+2*2+1*3+0*n+1=》n=11

樹的基本運算

? 求根Root(T):求樹T的根結點；
? 求雙親Parent(T,X):求結點X在樹T上的雙親；若X是樹T的根或X不在T上，則結果為一特殊標志；
? 求孩子Child(T,X,i):求樹T上結點X的第i個孩子結點；若X不在T上或X沒有第i個孩子，則結果為一特殊標志；
? 建樹Create(X,T1,…,Tk),k>1:建立一棵以X為根，以T1,…,Tk為第1,…,k棵子樹的樹；
? 剪枝Delete(T,X,i):洗掉樹T上結點X的第i棵子樹；若T無第i棵子樹，則為空操作；
? 遍歷TraverseTree(T):遍歷樹，即訪問樹中每個結點，且每個結點僅被訪問一次，

二、二叉樹

二叉樹在樹結構的應用中起著非常重要的作用，因為二叉樹有許多良好的性質和簡單的物理表示，而任何樹都可以與二叉樹相互轉換，這樣就解決了樹的存盤結構及其運算中存在的復雜性

二叉樹是n(n>=0)個結點的有限集合，它或為空(n=0)，或是由一個根及兩棵互不相交的左子樹和右子樹組成，且中左子樹和右子樹也均為二叉樹，二叉樹可以是空集合，左子樹可以為空、右子樹也可以為空，

二叉樹的特點：

①二叉樹可以是空的，稱空二叉樹；
②每個結點最多只能有兩個孩子；
③子樹有左、右之分且次序不能顛倒，

二叉樹結點的子樹要區分左子樹和右子樹，即使只有一棵子樹也要進行區分，說明它是左子樹，還是右子樹，這是二叉樹與樹的最主要的差別，二叉樹有5種基本形態

二叉樹的基本運算操作：

初始化Initiate(BT):建立一棵空二叉樹，BT=∅ ∅，
求雙親Parent(BT,X):求出二叉樹BT上結點X的雙親結點，若X是BT的根或X根本不是BT上的結點，運算結果為NULL，
求左孩子Lchild(BT,X)和求右孩子Rchild(BT,X)：分別求出二叉樹BT上結點X的左、右孩子；若X為BT的葉子或X補在BT上，運算結果為NULL，
建二叉樹Create(BT):建立一棵二叉樹BT，
先序遍歷PreOrder(BT):按先序對二叉樹BT進行遍歷，每個結點被訪問一次且僅被訪問一次，若BT為空，則運算為空操作
中序遍歷InOrder(BT):按中序對二叉樹BT進行遍歷，每個結點被訪問一次且僅被訪問一次，若BT為空，則運算為空操作，
后序遍歷PostOrder(BT):按后序對二叉樹BT進行遍歷，每個結點被訪問一次且僅被訪問一次，若BT為空，則運算為空操作，
層次遍歷LevelOrder(BT):按層從上往下，同一層中結點按從左往右的順序，對二叉樹進行遍歷，每個結點被訪問一次且僅被訪問一次，若BT為空，則運算為空操作

二叉樹具有下列重要性質：

1、性質1：在二叉樹的第i(i>=1)層上至多有2^(i-1)個結點，

2、性質2：深度為k(k>=1)的二叉樹至多有(2^k) -1個結點，最少有k個節點

3、性質3：對任何一棵二叉樹，如果其終端結點數為n0(葉子節點n0個)，度為2的結點數為n2，則n0＝n2＋1，即：葉結點數n0=度為2的結點數n2+1

滿二叉樹：深度為k(k>=1)且有(2^k) -1個結點的二叉樹;滿二叉樹中結點順序編號：即從第一層結點開始自上而下，從左到右進行連續編號，

完全二叉樹：深度為K的二叉樹中，K-1層結點數是滿的2^(k-2)，K層結點是左連續的(即結點編號是連續的)；高度為h(h>=2)的完全二叉樹至少有2^(h-2)個葉子結點，

假設高度為h二叉樹中只有度為2和度為0這兩種型別的結點，則該類二叉樹中結點個數至多為(2^h)-1、至少為 2h-1

若一棵二又樹中只有葉結點和左右子樹皆非空的結點，設二叉樹葉結點個數為s，則左右子樹皆非空的結點個數是s-1

若一棵二叉樹的前序、中序、后序遍歷的結果序列均相同，則該二叉樹一定是空二叉樹或是只有一個根結點的二叉樹

三、二叉樹的存盤結構

二叉樹通常有兩類存盤結構：順序存盤結構和鏈式存盤結構，鏈式存盤結構在插入洗掉結點時較方便，在某些情況下，二叉樹的順序存盤結構也很有用

1、二叉樹的順序存盤：

完全二叉樹的順序存盤：

●節省記憶體
●結點位置確定方便

2、二叉樹的鏈式存盤結構

在三叉鏈表中如果含有n個節點則有3n個指標域，2n-2個指標指向父節點以及左右節點，n+2個指標是空指標

四、二叉樹的遍歷

遍歷二叉樹：是指按某種次序訪問二叉樹上的所有結點，使每個結點被訪問一次且僅被訪問一次，

L —— 遍歷左子樹
D —— 訪問根結點
R —— 遍歷右子樹

1、先序遍歷DLR ——首先訪問根結點，其次遍歷根的左子樹，最后遍歷根右子樹，對每棵子樹同樣按這三步（先根、后左、再右）進行，
2、中序遍歷LDR ——首先遍歷根的左子樹，其次訪問根結點，最后遍歷根右子樹，對每棵子樹同樣按這三步（先左、后根、再右）進行，
3、后序遍歷LRD ——首先遍歷根的左子樹，其次遍歷根的右子樹，最后訪問根結點，對每棵子樹同樣按這三步（先左、后右、最后根）進行，

1、先序遍歷：ABDECFG

void preorder ( Bintree bt ) {
    /* 先序遍歷以 以bt 為根的二叉樹*/
    if (bt ！=NULL){
        visit(bt); /* 訪問根結點*/
        preorder ( bt->lchild ) ； ；
        preorder ( bt->rchild ) ;
    }
}

2、中序遍歷：DBEAFCG

void inorder (Bintree bt ) {
    /* 中序遍歷以bt 為根的二叉樹*/
    if (bt ！=NULL){
        inorder ( bt->lchild ) ； ；
        visit(bt); /* 訪問根結點*/
        inorder (bt->rchild ) ; 
    } /*…….*/
}

3、后序遍歷：DEBFGCA

void postorder (Bintree bt ) {
    /* 后序遍歷以bt 為根的二叉樹*/
    if (bt ！=NULL){
        postorder ( bt->lchild ) ； ；
        /* 后序遍歷以r 的左孩子為根的左子樹*/
        postorder ( bt->rchild ) ； ；
        visit(bt);
    }  /* 訪問根結點*/
}

二叉樹的層次遍歷：從二叉樹的根結點的這一層開始，逐層向下遍歷，在每一層上按從左到右的順序對結點逐個訪問；上圖層次遍歷：ABCDEFGH

若一棵具有n(n>0)個結點的二叉樹的先序序列與后序序列正好相反，則該二叉樹一定是高度為n的二叉樹(任何節點都沒左子樹或者任何節點都沒右子樹)

若一棵具有n(n>0)個結點的二叉樹的先序序列與中序序列正好相反，則每個結點的右子樹為空

任意一棵二叉樹的前序和后序遍歷的結果序列中，各葉子結點之間的相對次序關系是都相同

五、遍歷二叉樹的應用

① 求二叉樹中結點的個數；
② 求二叉樹中葉子結點的個數；
③ 求二叉樹中度為1 的結點個數；
④ 求二叉樹中度為2 2 的結點個數；
⑤ 求二叉樹中非終端結點個數；
⑥交換結點左右孩子；
⑦判定結點所在層次；

六、樹和森林

樹的存盤結構

一般樹轉二叉樹

二叉樹轉換為森林

假如一棵二叉樹的根節點有右孩子，則這棵二叉樹能夠轉換為森林，否則將轉換為一棵樹，

（1）從根節點開始，若右孩子存在，則把與右孩子結點的連線洗掉，再查看分離后的二叉樹，若其根節點的右孩子存在，則連線洗掉…，直到所有這些根節點與右孩子的連線都洗掉為止，

（2）將每棵分離后的二叉樹轉換為樹，

七、樹和森林的遍歷

森林的遍歷（注意只有兩種）

?先序遍歷森林：訪問森林中第一棵樹的根結點；先序遍歷森林中第一棵樹的根結點的子樹組成的森林；先序遍歷除去第一棵樹之外其余的樹組成的森林，對下圖中森林進行先序遍歷的序列為：ABCDEFGHJI
?中序遍歷森林：中序訪問森林中第一棵樹的根結點的子樹組成的森林；訪問第一棵樹的根結點；中序遍歷除去第一棵樹之外其余的樹組成的森林；對下圖中森林進行先序遍歷的序列為：BCDAFEJHIG

八、判定樹和哈夫曼樹

路徑：在一棵樹中，一個結點到另一個結點之間的通路，稱為路徑，圖 1 中，從根結點到結點 a 之間的通路就是一條路徑，
路徑長度：在一條路徑中，每經過一個結點，路徑長度都要加 1 ，例如在一棵樹中，規定根結點所在層數為1層，那么從根結點到第 i 層結點的路徑長度為 i - 1 ，圖 1 中從根結點到結點 c 的路徑長度為 3，
結點的權：給每一個結點賦予一個新的數值，被稱為這個結點的權，例如，圖 1 中結點 a 的權為 7，結點 b 的權為 5，
結點的帶權路徑長度：指的是從根結點到該結點之間的路徑長度與該結點的權的乘積，例如，圖 1 中結點 b 的帶權路徑長度為 2 * 5 = 10 ，
樹的帶權路徑長度為樹中所有葉子結點的帶權路徑長度之和，通常記作 “WPL” ，例如圖 1 中所示的這顆樹的帶權路徑長度為：WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

什么是哈夫曼樹

當用 n 個結點（都做葉子結點且都有各自的權值）試圖構建一棵樹時，如果構建的這棵樹的帶權路徑長度最小，稱這棵樹為“最優二叉樹”，有時也叫“赫夫曼樹”或者“哈夫曼樹”，
在構建哈弗曼樹時，要使樹的帶權路徑長度最小，只需要遵循一個原則，那就是：權重越大的結點離樹根越近，在圖 1 中，因為結點 a 的權值最大，所以理應直接作為根結點的孩子結點，

哈夫曼樹不存在度為1的節點，樹形結構不唯一，左右子樹沒有順序要求

構建哈夫曼樹的程序

對于給定的有各自權值的 n 個結點，構建哈夫曼樹有一個行之有效的辦法：
在 n 個權值中選出兩個最小的權值，對應的兩個結點組成一個新的二叉樹，且新二叉樹的根結點的權值為左右孩子權值的和；
在原有的 n 個權值中洗掉那兩個最小的權值，同時將新的權值加入到 n–2 個權值的行列中，以此類推；
重復 1 和 2 ，直到所以的結點構建成了一棵二叉樹為止，這棵樹就是哈夫曼樹，

哈夫曼編碼：得到哈夫曼樹后，自頂向下按路徑編號，指向左節點的邊編號0，指向右節點的邊編號1，從根到葉節點的所有邊上的0和1連接起來，就是葉子節點中字符的哈夫曼編碼，

對應的哈夫曼編碼分別為：

A：111
B：10
C：110
D：0

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/79542.html

標籤：其他

上一篇：RESTful API 設計指南

下一篇：【Jenkins】使用 Jenkins REST API 配合清華大學鏡像站更新 Jenkins 插件