數(shù)據(jù)結(jié)構(gòu)二叉樹ppt

1、第第6 6章章 樹與二叉樹樹與二叉樹校長校長一一系系二二系系三三系系六六系系教教務務處處科科研研處處總總務務處處601 602教教務務科科603A B CD張張三三李李四四王王五五例例1工工廠廠(根目錄) f1f2f3fnd1d2dm例例2f11f12f1kd11d12 例例31 樹的基本概念樹的基本概念2 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)3 二叉樹二叉樹4 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)5 二叉樹的遍歷二叉樹的遍歷6 線索二叉樹線索二叉樹 6.1 樹的基本概念樹的基本概念 樹樹是由是由n 0 個結(jié)點組成的有窮集合個結(jié)點組成的有窮集合( (不妨用不妨用D表示表示) )以及結(jié)點之間關(guān)系組成的集合構(gòu)成的

2、結(jié)構(gòu)。以及結(jié)點之間關(guān)系組成的集合構(gòu)成的結(jié)構(gòu)。 當當n=0 時，稱該樹為空樹；時，稱該樹為空樹； 在任何一棵非空的樹中，有一個特殊的結(jié)點在任何一棵非空的樹中，有一個特殊的結(jié)點t D，稱之為該樹的根結(jié)點；其余結(jié)點稱之為該樹的根結(jié)點；其余結(jié)點Dt被分割成被分割成m0個個不相交的子集不相交的子集D1, D2, ,Dm, ,其中每一個子集其中每一個子集Di又為一棵又為一棵樹，分別稱之為樹，分別稱之為t 的的子樹子樹。遞歸定義遞歸定義一一. . 樹的定義樹的定義JIHGFEACXBA的第1棵子樹A的第3棵子樹A的第2棵子樹二二. . 樹樹( (邏輯上邏輯上) )的特點的特點1. . 有且僅有一個結(jié)點沒有前

3、驅(qū)結(jié)點有且僅有一個結(jié)點沒有前驅(qū)結(jié)點, ,該結(jié)點為樹的根結(jié)點。該結(jié)點為樹的根結(jié)點。2. . 除了根結(jié)點外除了根結(jié)點外, ,每個結(jié)點有且僅有一個直接前驅(qū)結(jié)點。每個結(jié)點有且僅有一個直接前驅(qū)結(jié)點。3. . 包括根結(jié)點在內(nèi)，每個結(jié)點可以有多個后繼結(jié)點。包括根結(jié)點在內(nèi)，每個結(jié)點可以有多個后繼結(jié)點。JIHGFEACXB4. 樹形表示法樹形表示法 借助自然界中一棵倒置的樹的形狀來表示數(shù)借助自然界中一棵倒置的樹的形狀來表示數(shù)據(jù)元素之間層次關(guān)系的方法。據(jù)元素之間層次關(guān)系的方法。1. 結(jié)點的度：結(jié)點的度：2. 樹的度：樹的度：3. 葉結(jié)點：葉結(jié)點：4. 分支結(jié)點分支結(jié)點: :5. 層次的定義層次的定義: :JIHG

4、FEACXB該結(jié)點擁有的子樹的數(shù)目。該結(jié)點擁有的子樹的數(shù)目。樹中結(jié)點度的最大值樹中結(jié)點度的最大值。度為度為0 的結(jié)點的結(jié)點. .度非度非0 的結(jié)點的結(jié)點. . 根結(jié)點為第一層根結(jié)點為第一層, ,若某結(jié)點在第若某結(jié)點在第i 層層, , 則其孩子結(jié)點則其孩子結(jié)點( (若存在若存在) )為第為第i+1層層. .四四. . 基本名詞術(shù)語基本名詞術(shù)語第第1層層第第2層層第第3層層7. 樹林樹林( (森林森林): ): m 0 棵不相交的樹組成的樹的集合棵不相交的樹組成的樹的集合. .8. 樹的有序性樹的有序性: :6. 樹的深度樹的深度: :樹中結(jié)點所處的最大層次數(shù)樹中結(jié)點所處的最大層次數(shù). 若樹中結(jié)點

5、的子樹的相對位置不能若樹中結(jié)點的子樹的相對位置不能 隨意改變隨意改變, , 則稱該樹為則稱該樹為有序樹有序樹，否，否 則稱該樹為則稱該樹為無序樹無序樹。JIHGFEACXB深度為深度為3的樹的樹二叉樹的基本形態(tài)：二叉樹的基本形態(tài)：(空空)根根根根左左子子樹樹根根右右子子樹樹根根左左子子樹樹右右子子樹樹 6.2 二叉樹二叉樹二二. . 兩種特殊形態(tài)的二叉樹兩種特殊形態(tài)的二叉樹 若一棵二叉樹中的結(jié)點若一棵二叉樹中的結(jié)點, ,或者為葉結(jié)點，或者為葉結(jié)點， 或者具有兩或者具有兩棵非空子樹棵非空子樹, ,并且葉結(jié)點都集并且葉結(jié)點都集中在二叉樹的最下面一層中在二叉樹的最下面一層. .這這樣的二叉樹為滿二叉

6、樹樣的二叉樹為滿二叉樹. .1. . 滿二叉樹滿二叉樹 若一棵二叉樹中只有最下若一棵二叉樹中只有最下面兩層的結(jié)點的度可以小于面兩層的結(jié)點的度可以小于2, ,并且最下面一層的結(jié)點并且最下面一層的結(jié)點( (葉結(jié)葉結(jié)點點) )都依次排列在該層從左至都依次排列在該層從左至右的位置上。這樣的二叉樹為右的位置上。這樣的二叉樹為完全二叉樹完全二叉樹. .2. .完全二叉樹完全二叉樹1. . 一棵非空二叉樹的第一棵非空二叉樹的第i 層最多有層最多有2i1個結(jié)點個結(jié)點( (i 1) )。三三. . 二叉樹的性質(zhì)二叉樹的性質(zhì)2. . 深度為深度為h 的非空二叉樹最多有的非空二叉樹最多有2h -1-1個結(jié)點個結(jié)點.

7、 .3. . 若非空二叉樹有若非空二叉樹有n0個葉結(jié)點個葉結(jié)點, ,有有n2個度為個度為2的結(jié)點的結(jié)點, , 則則 n0=n2+1 4. . 具有具有n個結(jié)點的完全二叉樹的深度個結(jié)點的完全二叉樹的深度h= log2n +1. . 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)一一. .二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu)12345678910ABCDEFGHIJBT1:151 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B C D E F G H I J 根據(jù)完全二叉樹的性質(zhì)根據(jù)完全二叉樹的性質(zhì) , ,對于深度為對于深度為h 的完全二叉樹的完全二叉樹, , 將樹中所有結(jié)點的數(shù)據(jù)

8、信息按照編號的順序依次存儲到一將樹中所有結(jié)點的數(shù)據(jù)信息按照編號的順序依次存儲到一維數(shù)組維數(shù)組BT1:2h-1中中, ,由于編號與數(shù)組的下標一一對應由于編號與數(shù)組的下標一一對應, 該該數(shù)組就是該完全二叉樹的順序存儲結(jié)構(gòu)數(shù)組就是該完全二叉樹的順序存儲結(jié)構(gòu). . 1. 完全二叉樹的順序存儲結(jié)構(gòu)完全二叉樹的順序存儲結(jié)構(gòu)12345678910ABCDEFGHIJ111213BT1:151 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B C D E F G H J IABCDEFGHIJ 2. . 一般二叉樹的順序存儲結(jié)構(gòu)一般二叉樹的順序存儲結(jié)構(gòu) 對于一般二叉樹對于一般二叉樹,

9、只須在二叉樹中只須在二叉樹中“添加添加”一些實際一些實際上上二叉樹中并不存在的二叉樹中并不存在的“虛結(jié)點虛結(jié)點” ( 可以認為這些結(jié)點的數(shù)可以認為這些結(jié)點的數(shù)據(jù)據(jù)信息為空信息為空), 使其在形式上成為一棵使其在形式上成為一棵“完全二叉樹完全二叉樹”, 然然后后按照完全二叉樹的順序存儲結(jié)構(gòu)的構(gòu)造方法將所有結(jié)點的按照完全二叉樹的順序存儲結(jié)構(gòu)的構(gòu)造方法將所有結(jié)點的數(shù)據(jù)信息依次存放于數(shù)組數(shù)據(jù)信息依次存放于數(shù)組BT1: 2h -1中。中。二二. .二叉樹的鏈式存儲結(jié)構(gòu)二叉樹的鏈式存儲結(jié)構(gòu)( (二叉鏈表二叉鏈表) )鏈結(jié)點的構(gòu)造為鏈結(jié)點的構(gòu)造為lchilddatarchild 其中其中, data 為數(shù)據(jù)

10、域為數(shù)據(jù)域 lchild 與與rchild 分別為指向左、右子樹的指針域分別為指向左、右子樹的指針域.ABCDEFGIJABCDEFGJIT6.3.3 二叉樹的遍歷二叉樹的遍歷二二. .前序遍歷前序遍歷三三. .中序遍歷中序遍歷四四. .后序遍歷后序遍歷ABCDKFGIJEH前序遍歷序列前序遍歷序列: : A, B, D, K, J, G, C, F, I, E, H中序遍歷序列中序遍歷序列: : D, B, G, J, K, A, F, I, E, C, H后序遍歷序列后序遍歷序列: : D, G, J, K, B, E, I, F, H, C, A按層次遍歷序列按層次遍歷序列: : A,

11、B, C, D, K, F, H, J, I, G, E例例6.3.2 6.3.2 線索二叉樹線索二叉樹1.1.何謂線索二叉樹？何謂線索二叉樹？ 遍歷結(jié)果是求得結(jié)點的一個線性序列。指向遍歷結(jié)果是求得結(jié)點的一個線性序列。指向該線性序列該線性序列“前驅(qū)前驅(qū)”和和“后繼后繼”的指針，稱的指針，稱“線線索索”；包含；包含“線索線索”的存儲結(jié)構(gòu)，稱為的存儲結(jié)構(gòu)，稱為“線索鏈線索鏈表表”；與其相應的二叉樹，稱為；與其相應的二叉樹，稱為“線索二叉樹線索二叉樹”；對二叉樹以某種次序遍歷，使其變?yōu)榫€索二叉樹對二叉樹以某種次序遍歷，使其變?yōu)榫€索二叉樹的過程，稱為的過程，稱為“線索化線索化”。2.2.線索鏈表中結(jié)點

12、的結(jié)構(gòu)線索鏈表中結(jié)點的結(jié)構(gòu)標志域標志域lchildLTagdataRTag rchild其中：其中：LTag =LTag =0 lchild 0 lchild 域指示結(jié)點的左孩子域指示結(jié)點的左孩子1 lchild 1 lchild 域指示結(jié)點的前驅(qū)域指示結(jié)點的前驅(qū)RTag =RTag =0 rchild 0 rchild 域指示結(jié)點的右孩子域指示結(jié)點的右孩子1 rchild 1 rchild 域指示結(jié)點的后繼域指示結(jié)點的后繼二叉樹二叉線索存儲表示二叉樹二叉線索存儲表示typedef enum Link, Thread PointerThr; typedef enum Link, Thread

13、PointerThr; / Link=0:/ Link=0:指針，指針，Thread=1:Thread=1:線索線索typedef struct BiThrNodetypedef struct BiThrNode TElemType data; TElemType data; Struct BiThrNode Struct BiThrNode * *lchild, lchild, * *rchild;rchild; / / 左右孩子指針左右孩子指針 PointerThr LTag, RTag; PointerThr LTag, RTag; / / 左右標志左右標志 BiThrNode, BiT

14、hrNode, * *BiThrTree;BiThrTree;3.3.線索二叉樹圖例線索二叉樹圖例 線索二叉樹及其存儲結(jié)構(gòu)線索二叉樹及其存儲結(jié)構(gòu) （a a）中序線索二叉樹）中序線索二叉樹 （b b）中序線索鏈表）中序線索鏈表12345670 1 00 2 01 3 11 4 10 5 01 6 11 7 1thrt0 1如何在線索樹中找結(jié)點的后繼？如何在線索樹中找結(jié)點的后繼？結(jié)合中序線索樹結(jié)合中序線索樹 若其右標志為若其右標志為“1 1”，右鏈是線索，右鏈直接指，右鏈是線索，右鏈直接指示了結(jié)點的后繼；示了結(jié)點的后繼； 若其右標志為若其右標志為“0 0”，右鏈是指針，其后繼為右，右鏈是指針，其后

15、繼為右子樹中最左下的結(jié)點。子樹中最左下的結(jié)點。1234567如何在線索樹中找結(jié)點的前驅(qū)？如何在線索樹中找結(jié)點的前驅(qū)？結(jié)合中序線索樹結(jié)合中序線索樹 若其左標志為若其左標志為“1 1”，左鏈為線索，直接指示，左鏈為線索，直接指示其前驅(qū)；其前驅(qū)； 若其左標志為若其左標志為“0 0”，左子樹中最右下的結(jié)點，左子樹中最右下的結(jié)點為其前驅(qū)。為其前驅(qū)。1234567線索鏈表的中序遍歷算法線索鏈表的中序遍歷算法Status IOTraver_T( BiThrTree T,Status (Status IOTraver_T( BiThrTree T,Status (* *Visit)(TElemType e)

16、)Visit)(TElemType e) ) /T/T指向頭結(jié)點，頭結(jié)點的左鏈指向頭結(jié)點，頭結(jié)點的左鏈lchildlchild指向根結(jié)點，中序遍歷指向根結(jié)點，中序遍歷 /二叉線索樹二叉線索樹T T的非遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)的非遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)VisitVisit。 p = T-lchild; p = T-lchild; /p/p指向根結(jié)點指向根結(jié)點 while (p != T) while (p != T) /空樹或遍歷結(jié)束時，空樹或遍歷結(jié)束時，p = = Tp = = T while (p-LTag while (p-LTag=Link) p = p-lchild;

17、 Link) p = p-lchild; if (!Visit(p-data) return ERROR; if (!Visit(p-data) return ERROR; /訪問其左子樹為空的結(jié)點訪問其左子樹為空的結(jié)點 while (p-RTagwhile (p-RTag=Thread & p-rchild!=T) Thread & p-rchild!=T) p = p-rchild; Visit(p-data); p = p-rchild; Visit(p-data); /訪問后繼結(jié)點訪問后繼結(jié)點 p = p-rchild; p = p-rchild; return OK;

18、 return OK; / IOTraver_T/ IOTraver_T0 1 00 2 01 3 11 4 10 5 01 6 11 7 1T0 1 16.4.2 6.4.2 森林和二叉樹的轉(zhuǎn)換森林和二叉樹的轉(zhuǎn)換1. 1. 樹和二叉樹的對應關(guān)系樹和二叉樹的對應關(guān)系 由于二叉樹和樹都可用二叉鏈表作為存儲結(jié)由于二叉樹和樹都可用二叉鏈表作為存儲結(jié)構(gòu)，則以二叉鏈表作為媒介可導出樹與二叉樹之構(gòu)，則以二叉鏈表作為媒介可導出樹與二叉樹之間的一個對應關(guān)系。間的一個對應關(guān)系。樹轉(zhuǎn)換為二叉樹方法：樹轉(zhuǎn)換為二叉樹方法：1 1）對每個孩子進行從左到右的排序；）對每個孩子進行從左到右的排序；2 2）在兄弟之間加一條連

19、線；）在兄弟之間加一條連線；3 3）對每個結(jié)點，除了左孩子外，去除其與其余）對每個結(jié)點，除了左孩子外，去除其與其余孩子之間的聯(lián)系；孩子之間的聯(lián)系； 4 4）以根結(jié)點為軸心，將整個樹順時針轉(zhuǎn)）以根結(jié)點為軸心，將整個樹順時針轉(zhuǎn)4545。ABCDEGHFIa aABCDEGHFIb bABCDEGHFIc cABCDEGHFId d2. 2. 森林和二叉樹的對應關(guān)系森林和二叉樹的對應關(guān)系 從樹的二叉鏈表表示的定義可知，任何一棵從樹的二叉鏈表表示的定義可知，任何一棵和樹對應的二叉樹，其和樹對應的二叉樹，其右子樹必空右子樹必空。 若把森林中第二棵樹的根結(jié)點看成是第一棵若把森林中第二棵樹的根結(jié)點看成是第一

20、棵樹的根結(jié)點的兄弟，則同樣可導出森林和二叉樹樹的根結(jié)點的兄弟，則同樣可導出森林和二叉樹的對應關(guān)系。的對應關(guān)系。BCDEGHFIa aBCDEGHFIb bBCDEGHFIc cBCDEGHFId d已知條件：森林和二叉樹的對應關(guān)系設已知條件：森林和二叉樹的對應關(guān)系設 森森 林林 F = ( TF = ( T1 1, T, T2 2, , , T, Tn n ); ); T T1 1 = (root = (root，t t1111, t, t1212, , , t, t1m1m); ); 二叉樹二叉樹 B =( LBT, Node(root), RBT );B =( LBT, Node(root

21、), RBT );由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為: :若若 F = F = ，則，則 B = ;B = ;否則，由否則，由 Root( TRoot( T1 1 ) ) 對應得到對應得到 Node(root);Node(root); 由由 (t(t1111, t, t1212, , , t, t1m1m ) ) 對應得到對應得到 LBT;LBT; 由由 (T(T2 2, T, T3 3, , T, Tn n ) ) 對應得到對應得到 RBTRBT。由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為: :若若 B = , B = , 則則 F = ;F =

22、;否則，由否則，由 Node(root) Node(root) 對應得到對應得到 Root( TRoot( T1 1 ); ); 由由LBT LBT 對應得到對應得到 ( t( t1111, t, t1212, , ，t t1m1m);T);T1 1除根以外所除根以外所 構(gòu)成的森林構(gòu)成的森林 由由RBT RBT 對應得到對應得到 (T(T2 2, T, T3 3, , , T, Tn n) )；除；除T T1 1之外的森林之外的森林6.4.3 6.4.3 樹和森林的遍歷樹和森林的遍歷1. 1. 樹的遍歷樹的遍歷：有三條搜索路徑：有三條搜索路徑先根先根( (序序) )遍歷：遍歷：若樹不空，則先訪

23、問根結(jié)點，若樹不空，則先訪問根結(jié)點， 然后依次先根遍歷各棵子樹。然后依次先根遍歷各棵子樹。后根后根( (序序) )遍歷：遍歷：若樹不空，則先依次后根遍歷若樹不空，則先依次后根遍歷 各棵子樹，然后訪問根結(jié)點。各棵子樹，然后訪問根結(jié)點。按層次遍歷：按層次遍歷： 若樹不空，則自上而下自左至若樹不空，則自上而下自左至 右訪問樹中每個結(jié)點。右訪問樹中每個結(jié)點。例例對樹進行先根遍歷，獲得的先根序列是：對樹進行先根遍歷，獲得的先根序列是：對樹進行后根遍歷，獲得的后根序列是：對樹進行后根遍歷，獲得的后根序列是：ABCDEGHFIA B E F C D G H IA B E F C D G H IE F B C G H I D AE F B C G H I D A2.2.森林的遍歷森林的遍歷先序遍歷先序遍歷( (對森林中的每一