1、第第6章章 特殊二叉樹特殊二叉樹Slide 2 of 66第5章 樹2021-7-7DS主要內容主要內容二叉搜索樹二叉搜索樹1堆堆2哈夫曼樹哈夫曼樹3線索二叉樹線索二叉樹4平衡二叉樹平衡二叉樹5Slide 3 of 66第5章 樹2021-7-7DS6.1 二叉搜索樹二叉搜索樹v6.1.1 二叉搜索樹的定義二叉搜索樹的定義v6.1.2 二叉搜索樹的抽象數據類型二叉搜索樹的抽象數據類型v6.1.3 二叉搜索樹的運算二叉搜索樹的運算Slide 4 of 66第5章 樹2021-7-7DS6.1.1 6.1.1 二叉搜索樹的定義二叉搜索樹的定義v定義定義：又稱做又稱做二叉排序樹二叉排序樹(Binar

2、y Sorting Tree)，它或者是一棵空樹，或者是一棵具有如下特性的非空它或者是一棵空樹，或者是一棵具有如下特性的非空二叉樹。二叉樹。 (1) 若它的左子樹非空，則左子樹上所有結點的關若它的左子樹非空，則左子樹上所有結點的關鍵字均小于樹根結點的關鍵字；鍵字均小于樹根結點的關鍵字； (2) 若它的右子樹非空，則右子樹上所有結點的關若它的右子樹非空，則右子樹上所有結點的關鍵字均大于樹根結點的關鍵字；鍵字均大于樹根結點的關鍵字； (3) 左、右子樹本身又各是一棵二叉搜索樹。左、右子樹本身又各是一棵二叉搜索樹。v二叉搜索樹的定義是遞歸的，所以。對它進行的各種二叉搜索樹的定義是遞歸的，所以。對它進

3、行的各種運算的算法通常也是遞歸的。運算的算法通常也是遞歸的。 Slide 5 of 66第5章 樹2021-7-7DS在一棵非空的二叉搜索樹中，其結點的關鍵字是按照左子樹、在一棵非空的二叉搜索樹中，其結點的關鍵字是按照左子樹、根和右子樹有序的，所以對它進行中序遍歷得到的結點序列必然根和右子樹有序的，所以對它進行中序遍歷得到的結點序列必然是一個有序序列。是一個有序序列。 122315523074182663右圖所示就是一棵二叉搜右圖所示就是一棵二叉搜索樹。對此樹進行中序遍索樹。對此樹進行中序遍歷得到的結點序列為：歷得到的結點序列為： 12，15，18，23，26，30，52，63，74 可見此序

4、列是一個有序可見此序列是一個有序序列。序列。6.1.1 6.1.1 二叉搜索樹的定義二叉搜索樹的定義Slide 6 of 66第5章 樹2021-7-7DS6.1.2 二叉搜索樹的抽象數據類型二叉搜索樹的抽象數據類型v二叉搜索樹的抽象數據類型包括數據和操作兩個二叉搜索樹的抽象數據類型包括數據和操作兩個部分。部分。n數據部分為一棵二叉搜索樹，它可以具有同一數據部分為一棵二叉搜索樹，它可以具有同一般二叉樹一樣的任何存儲結構般二叉樹一樣的任何存儲結構 。n操作部分除了已經討論過的對一般二叉樹的操操作部分除了已經討論過的對一般二叉樹的操作外，還具有對二叉搜索樹的一些常用操作，即作外，還具有對二叉搜索樹

5、的一些常用操作，即查找、更新、插入和刪除元素的操作查找、更新、插入和刪除元素的操作 。Slide 7 of 66第5章 樹2021-7-7DS6.1.2 二叉搜索樹的抽象數據類型二叉搜索樹的抽象數據類型v對二叉搜索樹對二叉搜索樹BST的查找、更新、插入和刪除元素的查找、更新、插入和刪除元素的操作聲明如下：的操作聲明如下：vbool Find(BTreeNode* BST, ElemType& item);vbool Update(BTreeNode*& BST, const ElemType& item);vvoid Insert(BTreeNode*& BST, const ElemType

6、& item);vbool Delete(BTreeNode*& BST, const ElemType& item);Slide 8 of 66第5章 樹2021-7-7DS6.1.3 6.1.3 二叉搜索樹的運算二叉搜索樹的運算1. 查找查找v若二叉搜索樹為空，則表明查找失敗，應返回假若二叉搜索樹為空，則表明查找失敗，應返回假v若若item等于當前樹根結點的值，則表明查找成功，等于當前樹根結點的值，則表明查找成功，應由引用參數應由引用參數item帶回根結點的完整值并返回真帶回根結點的完整值并返回真v若若item小于當前樹根結點的值，則繼續在它的左子小于當前樹根結點的值，則繼續在它的左子樹上

7、查找樹上查找v若若item 大于當前樹根結點的值，則繼續它的右子樹大于當前樹根結點的值，則繼續它的右子樹上查找上查找 Slide 9 of 66第5章 樹2021-7-7DS1. 查找查找-遞歸算法遞歸算法bool Find(BTreeNode* BST, ElemType& item) if(BST=NULL) return false; /查找失敗返回假查找失敗返回假 else if(item=BST-data) /若查找成功則帶回元素值并返回真若查找成功則帶回元素值并返回真 item=BST-data; return true; else if(itemdata) /向左子樹繼續查找向左

8、子樹繼續查找 return Find(BST-left, item); else /向右子樹繼續查找向右子樹繼續查找 return Find(BST-right, item); Slide 10 of 66第5章 樹2021-7-7DS1. 查找查找-非遞歸算法非遞歸算法bool Find1(BTreeNode* BST, ElemType& item) /二叉搜索樹查找的非遞歸算法二叉搜索樹查找的非遞歸算法 while(BST!=NULL) if(item=BST-data) item=BST-data; return true; else if(itemdata) BST=BST-left

9、; else BST=BST-right; return false ; Slide 11 of 66第5章 樹2021-7-7DS6.1.3 6.1.3 二叉搜索樹的運算二叉搜索樹的運算122315523074182663查找查找23查找查找48Slide 12 of 66第5章 樹2021-7-7DS6.1.3 6.1.3 二叉搜索樹的運算二叉搜索樹的運算2. 更新：更新：更新算法與查找算法基本相同，區別僅有更新算法與查找算法基本相同，區別僅有兩點：兩點：v一是一是在更新算法中當查找到待更新的元素時，應在更新算法中當查找到待更新的元素時，應將將item的值賦給該元素，而在查找算法中是將該的

10、值賦給該元素，而在查找算法中是將該元素的值賦給元素的值賦給item帶回；帶回；v二是二是在更新算法中參數在更新算法中參數item可以為變參可以為變參(即引用即引用參數參數)，也可以為值參，而在查找算法中，也可以為值參，而在查找算法中item參參數只能為變參，因為需要它帶回結點的完整值。數只能為變參，因為需要它帶回結點的完整值。 Slide 13 of 66第5章 樹2021-7-7DS6.1.3 6.1.3 二叉搜索樹的運算二叉搜索樹的運算3. 插入插入v若當前二叉樹為空，則由若當前二叉樹為空，則由item元素生成的新結點元素生成的新結點將作為樹根結點插入將作為樹根結點插入v若若item 小于

11、當前樹根結點的值，則將新結點插小于當前樹根結點的值，則將新結點插入到它的左子樹上入到它的左子樹上v若若item大于當前樹根結點的值，則將新結點插入大于當前樹根結點的值，則將新結點插入到它的右子樹上到它的右子樹上Slide 14 of 66第5章 樹2021-7-7DS3. 插入插入void Insert(BTreeNode*& BST, const ElemType& item) if(BST=NULL) /把值為把值為item的新結點鏈接到已找到的插入位置的新結點鏈接到已找到的插入位置 BTreeNode* p=new BTreeNode; p-data=item; p-left=p-rig

12、ht=NULL; BST=p; else if(itemdata) /向左子樹中插入元素向左子樹中插入元素 Insert(BST-left, item); else /向右子樹中插入元素向右子樹中插入元素 Insert(BST-right, item);Slide 15 of 66第5章 樹2021-7-7DS3. 插入插入v首先查找插入位置，然后再進行插入首先查找插入位置，然后再進行插入n從樹根結點開始，若樹根指針為空，則新結點就是樹根結點從樹根結點開始，若樹根指針為空，則新結點就是樹根結點n若若item小于當前樹根結點的值，則沿著它的左指針在左子樹小于當前樹根結點的值，則沿著它的左指針在左

13、子樹上繼續查找插入位置上繼續查找插入位置n若若item大于當前樹根結點的值，則沿著它的右指針在右子樹大于當前樹根結點的值，則沿著它的右指針在右子樹上繼續查找插入位置上繼續查找插入位置v當查找到一個結點當查找到一個結點(假定由假定由parent指針所指向指針所指向)的左指針或右的左指針或右指針為空時，則這個空的指針位置就是新元素結點的鏈接到二指針為空時，則這個空的指針位置就是新元素結點的鏈接到二叉搜索樹中的位置。叉搜索樹中的位置。 Slide 16 of 66第5章 樹2021-7-7DS3. 插入插入void Insert1(BTreeNode*& BST, const ElemType& i

14、tem) BTreeNode* t=BST, *parent=NULL; while(t!=NULL) parent=t; if(itemdata) t=t-left; else t=t-right; BTreeNode* p=new BTreeNode; p-data=item; p-left=p-right=NULL; if(parent=NULL) BST=p; else if(itemdata) parent-left=p; else parent-right=p;Slide 17 of 66第5章 樹2021-7-7DS122315523074182663插入插入2424Slide

15、18 of 66第5章 樹2021-7-7DSv利用插入算法，可以建立一棵二叉搜索樹。利用插入算法，可以建立一棵二叉搜索樹。v設生成二叉搜索樹的設生成二叉搜索樹的n個元素由數組個元素由數組a提供，則算提供，則算法描述為：法描述為：void CreateBSTree(BTreeNode*& BST, ElemType a, int n) BST=NULL; /從空樹開始建立從空樹開始建立 for(int i=0; in; i+) Insert(BST, ai); 6.1.3 二叉搜索樹的運算二叉搜索樹的運算Slide 19 of 66第5章 樹2021-7-7DS假定待建立二叉搜索樹的一組元素的

16、關鍵字為：假定待建立二叉搜索樹的一組元素的關鍵字為： 38，26，62，94，35，50，28，55按照上述算法，每插入一個結點后得到的二叉搜索樹如下圖所示。按照上述算法，每插入一個結點后得到的二叉搜索樹如下圖所示。Slide 20 of 66第5章 樹2021-7-7DS6.1.3 6.1.3 二叉搜索樹的運算二叉搜索樹的運算4. 刪除刪除（1）刪除葉子結點：將其雙親結點鏈接到它的指針去掉。）刪除葉子結點：將其雙親結點鏈接到它的指針去掉。 刪除刪除A，F，P，WSlide 21 of 66第5章 樹2021-7-7DS6.1.3 6.1.3 二叉搜索樹的運算二叉搜索樹的運算4. 刪除刪除（2

17、）刪除單支結點：將其后繼指針鏈接到它所在的鏈接位）刪除單支結點：將其后繼指針鏈接到它所在的鏈接位置。置。刪除刪除G和和MSlide 22 of 66第5章 樹2021-7-7DS6.1.3 6.1.3 二叉搜索樹的運算二叉搜索樹的運算4. 刪除刪除（3）刪除雙支結點：）刪除雙支結點：方法一：首先把它的右子樹鏈接到它的中序前驅結點的右指針域，方法一：首先把它的右子樹鏈接到它的中序前驅結點的右指針域，此中序前驅結點必是它的左子樹中此中序前驅結點必是它的左子樹中“最右下最右下”的一個右指針為空的一個右指針為空的結點。的結點。沿沿p左子樹的根左子樹的根C的右子樹分支找到的右子樹分支找到S，S的右子樹為

18、空的右子樹為空 法法1：令令*p的左子樹為的左子樹為 *f的左子樹，的左子樹，*p的右子樹為的右子樹為*s的右子樹；的右子樹；FPCPRCLFCPRCLSSSlide 23 of 66第5章 樹2021-7-7DS6.1.3 6.1.3 二叉搜索樹的運算二叉搜索樹的運算4. 刪除刪除（3）刪除雙支結點：）刪除雙支結點：方法二：首先把它的中序前驅結點的值賦給該結點的值域，然方法二：首先把它的中序前驅結點的值賦給該結點的值域，然后再刪除它的中序前驅結點。后再刪除它的中序前驅結點。令令*s代替代替*p ，將將S的左子樹成為的左子樹成為S的雙親的雙親Q的右子樹，用的右子樹，用S取代取代pFPCPRCL

19、QQLSSLFSCPRCLQQLSLSlide 24 of 66第5章 樹2021-7-7DS刪除刪除LSlide 25 of 66第5章 樹2021-7-7DS6.2 堆堆v6.2.1 堆的定義堆的定義v6.2.2 堆的抽象數據類型堆的抽象數據類型v6.2.3 堆的存儲結構堆的存儲結構v6.2.4 堆的運算堆的運算Slide 26 of 66第5章 樹2021-7-7DS6.2.1 6.2.1 堆的定義堆的定義v定義定義：堆堆(Heap)分為分為小根堆小根堆和和大根堆大根堆兩種，對于一兩種，對于一個小根堆，它是具有如下特性的一棵完全二叉樹。個小根堆，它是具有如下特性的一棵完全二叉樹。 (1)

20、 若樹根結點存在左孩子，則樹根結點的值小于若樹根結點存在左孩子，則樹根結點的值小于等于左孩子結點的值；等于左孩子結點的值； (2) 若樹根結點存在右孩子，則樹根結點的值小于若樹根結點存在右孩子，則樹根結點的值小于等于右孩子結點的值；等于右孩子結點的值； (3) 以左、右孩子為根的子樹又同樣各是一個堆。以左、右孩子為根的子樹又同樣各是一個堆。 大根堆的定義與上述類似，只要把小于等于改為大大根堆的定義與上述類似，只要把小于等于改為大于等于就得到了。于等于就得到了。v由堆的定義可知，若一棵完全二叉樹是堆，則該樹中由堆的定義可知，若一棵完全二叉樹是堆，則該樹中以每個結點為根的子樹也都是一個堆。以每個結

21、點為根的子樹也都是一個堆。 Slide 27 of 66第5章 樹2021-7-7DS舉例舉例圖圖(a)是一個小根堆，堆中的最小值為堆頂結點的值是一個小根堆，堆中的最小值為堆頂結點的值18圖圖(b)是一個大根堆，堆中的最大值為堆頂結點的值是一個大根堆，堆中的最大值為堆頂結點的值74。253653427420182273482635186035(a)(b)6.2.1 6.2.1 堆的定義堆的定義Slide 28 of 66第5章 樹2021-7-7DS6.2.2 堆的抽象數據類型堆的抽象數據類型v堆的抽象數據類型包括數據和操作兩個部分。堆的抽象數據類型包括數據和操作兩個部分。n數據部分為是按任一

22、種存儲結構表示的堆，假定數據部分為是按任一種存儲結構表示的堆，假定用標識符用標識符HBT表示，其存儲類型用標識符表示，其存儲類型用標識符HeapType表示表示 。n操作部分通常包括向堆中插入一個元素，從堆中操作部分通常包括向堆中插入一個元素，從堆中刪除堆頂元素，初始化一個堆，清除一個堆，判刪除堆頂元素，初始化一個堆，清除一個堆，判斷一個堆是否為空等斷一個堆是否為空等 。Slide 29 of 66第5章 樹2021-7-7DS6.2.2 堆的抽象數據類型堆的抽象數據類型ADT HEAP is Data: 具有具有HeapType類型的一個堆類型的一個堆HBT Operations: void

23、 InitHeap(HeapType& HBT); void ClearHeap(HeapType& HBT); bool EmptyHeap(HeapType& HBT); void InsertHeap(HeapType& HBT, ElemType item); ElemType DeleteHeap(HeapType& HBT); end HEAPSlide 30 of 66第5章 樹2021-7-7DS6.2.3 6.2.3 堆的存儲結構堆的存儲結構v使用存儲方式：順序存儲。由于堆是一棵完全二叉樹，這樣能使用存儲方式：順序存儲。由于堆是一棵完全二叉樹，這樣能夠充分利用其存儲空間夠充分

24、利用其存儲空間v編號：堆中結點的編號從編號：堆中結點的編號從0而不是從而不是從1 開始，當然編號次序仍開始，當然編號次序仍然按照從上到下、同一層從左到右進行，若堆中含有然按照從上到下、同一層從左到右進行，若堆中含有n個結點，個結點，則編號范圍為則編號范圍為0 n-1n分支結點： 0至 n/2-1n葉子結點：n/2 至n-1nn為奇數：每個分支結點既有左孩子又有右孩子nn為偶數：編號最大的一個分支結點只有左孩子沒有右孩子n編號為i的分支結點：左孩子結點的編號為2i+1，右孩子結點的編號為2i+2，雙親結點的編號為 (i-1)/2Slide 31 of 66第5章 樹2021-7-7DS6.2.3

25、 6.2.3 堆的存儲結構堆的存儲結構253653427420182273482635186035(a)(b)Slide 32 of 66第5章 樹2021-7-7DS6.2.3 6.2.3 堆的存儲結構堆的存儲結構當一個堆采用順序存儲結構時，需要定義一個元素類型為當一個堆采用順序存儲結構時，需要定義一個元素類型為ElemType、長度為、長度為MaxSize的一個數組來存儲堆中的的一個數組來存儲堆中的所有元素，還需要定義一個整型變量，用以存儲堆的長度，所有元素，還需要定義一個整型變量，用以存儲堆的長度，即堆中當前包含的結點數。即堆中當前包含的結點數。 類型定義為：類型定義為： struct

26、Heap /定義堆的順序存儲類型定義堆的順序存儲類型 ElemType* heap; /定義指向動態數組空間的指針定義指向動態數組空間的指針 int len; /定義保存堆長度的變量定義保存堆長度的變量 int MaxSize; /用于保存初始化時所給的動態數用于保存初始化時所給的動態數組空間的大小組空間的大小 ;Slide 33 of 66第5章 樹2021-7-7DS6.2.4 6.2.4 堆的運算堆的運算 1初始化堆初始化堆 void InitHeap(Heap& HBT) HBT.MaxSize=10; HBT.heap=new ElemTypeHBT.MaxSize; if(!HBT

27、.heap) cout用于動態分配的內存空間用完，退出運用于動態分配的內存空間用完，退出運行行!endl; exit(1); HBT.len=0;Slide 34 of 66第5章 樹2021-7-7DS6.2.4 6.2.4 堆的運算堆的運算 2清除堆清除堆 void ClearHeap(Heap& HBT) if(HBT.heap!=NULL) delete HBT.heap; HBT.heap=NULL; HBT.len=0; HBT.MaxSize=0; Slide 35 of 66第5章 樹2021-7-7DS6.2.4 6.2.4 堆的運算堆的運算 3檢查一個堆是否為空檢查一個堆是

28、否為空 bool EmptyHeap(Heap& HBT) return HBT.len=0;Slide 36 of 66第5章 樹2021-7-7DS6.2.4 6.2.4 堆的運算堆的運算 4向堆中插入一個元素向堆中插入一個元素v插入方法：首先將該元素寫入到堆尾，然后經調整插入方法：首先將該元素寫入到堆尾，然后經調整為一個新堆。為一個新堆。v調整的方法：若新元素小于雙親結點的值，就讓它調整的方法：若新元素小于雙親結點的值，就讓它們互換位置；新元素換到雙親位置后，使得以該位置們互換位置；新元素換到雙親位置后，使得以該位置為根的子樹成為堆，但新元素可能還小于此位置的雙為根的子樹成為堆，但新元素

29、可能還小于此位置的雙親結點的值，從而使以上一層的雙親結點為根的子樹親結點的值，從而使以上一層的雙親結點為根的子樹不為堆，還需要按上述方法繼續調整，這樣持續傳遞不為堆，還需要按上述方法繼續調整，這樣持續傳遞上去，直到以新位置的雙親結點為根的子樹仍為一個上去，直到以新位置的雙親結點為根的子樹仍為一個堆或者調整到堆頂為止，此時得到的整個樹又成為了堆或者調整到堆頂為止，此時得到的整個樹又成為了一個堆。一個堆。 Slide 37 of 66第5章 樹2021-7-7DS插入插入50插入插入30插入插入15Slide 38 of 66第5章 樹2021-7-7DS6.2.4 6.2.4 堆的運算堆的運算

30、5從堆中刪除元素從堆中刪除元素從堆中刪除元素就是刪除堆頂元素并使之返回。堆頂元素從堆中刪除元素就是刪除堆頂元素并使之返回。堆頂元素被刪除后，留下的堆頂位置應由堆尾元素來填補，這樣既被刪除后，留下的堆頂位置應由堆尾元素來填補，這樣既保持了順序存儲結構又不需要移動其他任何元素。把堆尾保持了順序存儲結構又不需要移動其他任何元素。把堆尾元素移動到堆頂位置后，它可能不小于左、右孩子結點，元素移動到堆頂位置后，它可能不小于左、右孩子結點，使整個二叉樹不為堆，所以需要一個調整過程，使之變為使整個二叉樹不為堆，所以需要一個調整過程，使之變為含有含有n-1個元素的堆。個元素的堆。調整過程首先從樹根結點開始，若樹

31、根結點的值大于兩個調整過程首先從樹根結點開始，若樹根結點的值大于兩個孩子結點中的最小值，就將它與具有最小值的孩子結點互孩子結點中的最小值，就將它與具有最小值的孩子結點互換位置，使得根結點的值小于兩個孩子結點的值；原樹根換位置，使得根結點的值小于兩個孩子結點的值；原樹根結點被對調到一個孩子位置后，可能使以該位置為根的子結點被對調到一個孩子位置后，可能使以該位置為根的子樹又不為堆，因而又需要使新元素向孩子一層調整，如此樹又不為堆，因而又需要使新元素向孩子一層調整，如此調整下去，直到以調整后的位置為根的子樹成為一個堆或調整下去，直到以調整后的位置為根的子樹成為一個堆或調整到葉子結點為止。調整到葉子結

32、點為止。 Slide 39 of 66第5章 樹2021-7-7DS刪除刪除18堆尾元素堆尾元素60替代替代18的位置的位置調整調整Slide 40 of 66第5章 樹2021-7-7DS6.3 哈夫曼樹哈夫曼樹v6.3.1 基本術語基本術語v6.3.2 構造哈夫曼樹構造哈夫曼樹v6.3.3 哈夫曼編碼哈夫曼編碼Slide 41 of 66第5章 樹2021-7-7DS6.3.1 6.3.1 基本術語基本術語v1.路徑和路徑長度路徑和路徑長度n在一棵樹中，從一個結點往下可以達到的孩子或子孫結點之間的通路，稱為路徑。n通路中分支的數目稱為路徑長度。n若規定根結點的層數為1，則從根結點到第L層結

33、點的路徑長度為L-1。v2.結點的權和帶權路徑長度結點的權和帶權路徑長度n若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。n結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。 Slide 42 of 66第5章 樹2021-7-7DS3樹的帶權路徑長度樹的帶權路徑長度樹的帶權路徑長度規定為所有葉子結點的帶權路徑長樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為度之和，記為wpl= ，其中其中n 為葉子結點數目，為葉子結點數目，wi為第為第i 個葉子結點的權值，個葉子結點的權值，li 為第為第i 個葉子結點的路徑長度。個葉子結點的路徑長度。nii

34、ilw16.3.1 6.3.1 基本術語基本術語Slide 43 of 66第5章 樹2021-7-7DS6.3.1 6.3.1 基本術語基本術語v4.哈夫曼樹哈夫曼樹n又稱做最優二叉樹，它是n個帶權葉子結點構成的所有二叉樹中，帶權路徑長度WPL最小的二叉樹。Slide 44 of 66第5章 樹2021-7-7DS例例 有有4個結點，權值分別為個結點，權值分別為7，5，2，4，構造有，構造有4個個葉子結點的二叉樹葉子結點的二叉樹abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3

35、+4*3=35nkKKLWWPL1Slide 45 of 66第5章 樹2021-7-7DS6.3.2 構造哈夫曼樹構造哈夫曼樹v構造Huffman樹的方法Huffman算法n假設有假設有n個權值，則構造出的哈夫曼樹有個權值，則構造出的哈夫曼樹有n個葉子結點。個葉子結點。 n個個權值分別設為權值分別設為 w1,w2,wn,則哈夫曼樹的則哈夫曼樹的構造規則構造規則為為u根據給定的根據給定的n個權值個權值w1,w2,wn，構造構造n棵只有根結棵只有根結點的二叉樹，令起權值為點的二叉樹，令起權值為wju在森林中選取兩棵根結點權值最小的樹作左右子樹，構造在森林中選取兩棵根結點權值最小的樹作左右子樹，構

36、造一棵新的二叉樹，置新二叉樹根結點權值為其左右子樹根結一棵新的二叉樹，置新二叉樹根結點權值為其左右子樹根結點權值之和點權值之和u在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中中u重復上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹重復上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹Slide 46 of 66第5章 樹2021-7-7DS例例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118n 個權值構造哈夫曼樹需個權值構造哈夫曼樹需n-1次合并，每次合并，森林中的次合并，每次合并，森林中的樹數目減樹數目減1，

37、最后森林中只剩，最后森林中只剩下一棵樹，即為我們求得的哈下一棵樹，即為我們求得的哈夫曼樹。夫曼樹。Slide 47 of 66第5章 樹2021-7-7DS例例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100Slide 48 of 66第5章 樹2021-7-7DSHuffman樹應用樹

38、應用-最佳判定樹最佳判定樹等級分數段比例ABCDE05960697079 8089 901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060aright為P的后繼結點n若P結點的右線索標志域為假，則表明p-right指向右孩子結點，P的中序后繼結點必是其右子樹中第一個中序遍歷得到的結點。因此從p的右孩子開始，沿左指針鏈往下查找，直到找到一個沒有左孩子（即左線索標志域為1）的結點為止，該結點是p的右子樹中“最左下”的結點，它就是p的中序后繼結點。Slide 56 of 66第5章 樹2021-7-

39、7DS6.5 平衡二叉樹平衡二叉樹v6.5.1 平衡二叉樹的定義平衡二叉樹的定義v6.5.2 平衡二叉樹的調整平衡二叉樹的調整Slide 57 of 66第5章 樹2021-7-7DS6.5.1 平衡二叉樹的定義平衡二叉樹的定義v背景：為了實現二叉排序樹的平均查找長度和背景：為了實現二叉排序樹的平均查找長度和 log n 等數量級，需要對二叉排序樹進行等數量級，需要對二叉排序樹進行“平衡化平衡化”處理，處理，即構造即構造平衡二叉樹。平衡二叉樹。v定義：簡稱平衡樹，是由定義：簡稱平衡樹，是由AdelsonVelskiiLandis首先提出，所以又稱為首先提出，所以又稱為AVL樹。平衡二叉樹樹。平

40、衡二叉樹或者是一棵空樹，或者是具有下列性質的二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉排序樹:n其左子樹和右子樹的深度之差的絕對值不超過 1 n其左子樹和右子樹都是平衡二叉樹 Slide 58 of 66第5章 樹2021-7-7DS6.5.1 平衡二叉樹的定義平衡二叉樹的定義ABCDABCDEFGABCDEFABCDFGESlide 59 of 66第5章 樹2021-7-7DS6.5.1 平衡二叉樹的定義平衡二叉樹的定義v結點的平衡因子結點的平衡因子: 該結點的左子樹的深度減去右該結點的左子樹的深度減去右子樹的深度。子樹的深度。v由于平衡二叉樹要求左右子樹深度之差的絕對值由于平衡二叉樹要求左右子樹深度之差的絕對值不大于不大于 1 ，故結點的平衡因子只可能為，故結點的平衡因子只可能為 -1 、0 、1 。v可以證明平衡二叉樹的深度與可以證明平衡二叉樹的深度與 log n 同數量級。同數量級。Slide 60 of 66第5章 樹2021-7-7DS6.5.2 平衡二叉樹的調整平衡二叉樹的調整vLL型型: 新結點加入到左子樹的左子樹中。新結點加入到左子樹的左子樹中。v調整規則調整規則: 右旋右旋，以失去