第06章-樹、二叉樹.ppt

《第06章-樹、二叉樹.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第六章樹、二叉樹6.1樹的定義和基本術(shù)語6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.6赫夫曼樹及其應(yīng)用6.1樹的定義和基本術(shù)語樹(Tree)是n(n>0)個(gè)結(jié)點(diǎn)的有限集T，非空樹滿足以下條件:有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn);(2)除根結(jié)點(diǎn)外的其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2...Tm,其中,每一個(gè)集合本身又是一棵樹,并且稱為根的子樹(subtree)樹的定義6.1樹的定義和基本術(shù)語樹的定義(b)是只有一個(gè)根結(jié)點(diǎn)的樹;(a)是有13個(gè)結(jié)點(diǎn)的樹,其中A是根,其余結(jié)點(diǎn)分成三個(gè)互不相交的子樹；6.1樹的定義和基本術(shù)語樹的

2、基本術(shù)語樹的結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干個(gè)指向其子樹的分支結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)樹的度：樹內(nèi)各結(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)的層次和樹的深度：有序樹和無序樹：森林：是m棵互不相交的樹的集合6.2二叉樹二叉樹的定義度不大于2的樹稱為二叉樹。相關(guān)術(shù)語左子結(jié)點(diǎn)、右子結(jié)點(diǎn)(a)空二叉樹A(b)根和空的左右子樹AB(c)根和左子樹AB(d)根和右子樹ACB(e)根和左右子樹二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i>=1)性質(zhì)2：深度為k的二

3、叉樹至多有2k-1個(gè)結(jié)點(diǎn)性質(zhì)3：對(duì)于任何一棵二叉樹T，如果其葉子數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1滿二叉樹：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹完全二叉樹：深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)6.2二叉樹二叉樹的性質(zhì)6.2二叉樹性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為└log2n┘+1性質(zhì)5：如果對(duì)一棵n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任意結(jié)點(diǎn)i(1≤i≤n)，有(1)當(dāng)i=1時(shí)，該結(jié)點(diǎn)為根，它無雙親結(jié)點(diǎn)；(2)當(dāng)i>1時(shí)，該結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為└i/2┘；(3)當(dāng)2i

4、

5、僅被訪問一次。其中常見的有三種情況：分別稱之為先(根)序遍歷，中(根)序遍歷和后(根)序遍歷。先序(Preorder)遍歷若遍歷的二叉樹為空，執(zhí)行空操作；否則(1)訪問根結(jié)點(diǎn)；(2)先序遍歷左子樹；(3)先序遍歷右子樹。中序(Inorder)遍歷若遍歷的二叉樹為空，執(zhí)行空操作；否則(1)中序遍歷左子樹；(2)訪問根結(jié)點(diǎn)；(3)中序遍歷右子樹。后序(Postorder)遍歷若遍歷的二叉樹為空，執(zhí)行空操作；否則(1)后序遍歷左子樹；(2)后序遍歷右子樹；(3)訪問根結(jié)點(diǎn)。二叉樹的遍歷abdcegjkhfidbajgkehcfidbjkgheifca后序遍歷：左子樹

6、右子樹根中序遍歷：左子樹根右子樹前序遍歷：根左子樹右子樹6.3遍歷二叉樹和線索二叉樹層次遍歷：從上到下從左到右abcdefghijk6.3遍歷二叉樹和線索二叉樹二叉樹的遍歷遍歷序與二叉樹的對(duì)應(yīng)前序遍歷序+中序遍歷序唯一確定二叉樹后序遍歷序+中序遍歷序唯一確定二叉樹前序遍歷序：abdceghfi中序遍歷序：dbagehcfi線索二叉樹定義6.3遍歷二叉樹和線索二叉樹lchildLTagdataRTagrchild其中：Ltag=0lchild域指示結(jié)點(diǎn)的左孩子1lchild域指示結(jié)點(diǎn)的前驅(qū)Rtag=0rchild域指示結(jié)點(diǎn)的右孩子1rchild域指示結(jié)點(diǎn)的后繼以

7、這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu),叫做線索鏈表,其中指向結(jié)點(diǎn)前驅(qū)與后繼的指針叫做線索.加上線索的二叉樹稱之為線索二叉樹.對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化.線索二叉樹例：6.3遍歷二叉樹和線索二叉樹線索二叉樹中序線索二叉樹的遍歷6.3遍歷二叉樹和線索二叉樹后繼的尋找方法:若結(jié)點(diǎn)右標(biāo)志為1,則右鏈為線索,指示其后繼;否則遍歷右子樹時(shí)訪問的第一個(gè)結(jié)點(diǎn)為其后繼,即右子樹中最左下的結(jié)點(diǎn)。前驅(qū)的尋找方法:若結(jié)點(diǎn)左標(biāo)志為1,則左鏈為線索,指示其前驅(qū);否則遍歷左子樹時(shí)最后訪問的一個(gè)結(jié)點(diǎn)為其前驅(qū)。二叉樹的線索化線索化的過程即為在遍歷的過程中修改

8、空指針的過程.6.3遍歷二叉樹和線索二