noip普及講座5-樹的基礎知識

《noip普及講座5-樹的基礎知識》由會員分享，可在線閱讀，更多相關《noip普及講座5-樹的基礎知識（44頁珍藏版）》請在技術文庫上搜索。

1、樹的基礎知識 江蘇省華羅庚中學江蘇省華羅庚中學 楊志軍楊志軍 樹的基本概念01 二叉樹的基本知識02 二叉樹的應用03 特殊二叉樹04 Table of Contents 內容大綱 樹的基本概念 （1）樹的定義 樹是n（n0）個結點的有窮集合，滿足： 有且僅有一個稱為根的結點； 其余結點分為m（m0）個互不相交的非空集合T1，T2 ，Tm，這些集合中的每一個都是一棵樹，稱為根的子 樹。 樹的基本概念 （2）樹的表示方法 圖示表示： 廣義表表示： =（T） =（1（T1，T2 ，T3 ） =（1（2（T11，T12），3，4（T31） =（1（2（5，6），3，4（7（T311，T312） =（

2、1（2（5，6），3，4（7（8，9） 樹的基本概念 （3）樹的基本術語 結點的度和樹的度 結點的度：每個結點具有的子樹的個數或者說其后繼結點 的個數被定義為該結點的度。 樹的度：所有結點的度的最大值定義為該樹的度。 樹的基本概念 （3）樹的基本術語 分支結點和葉子結點 度大于0的結點稱為分支結點或非終端結點，度為0的結點 稱為葉子結點。 樹的基本概念 （3）樹的基本術語 孩子結點、雙親結點和兄弟結點 每個結點的后繼結點被稱為該結點的孩子結點，相應的該 結點被稱為雙親結點或父親結點。具有同一雙親結點的孩 子結點互稱為兄弟結點。 樹的基本概念 （3）樹的基本術語 樹的深度和寬度 樹中的結點的最大

3、層數稱為樹的深度或高度。 整棵樹中某一層中最多的結點數稱為樹的寬度。 二叉樹的基本知識 （1）二叉樹的基本概念 二叉樹是一種特殊的樹型結構，它是度數最多為2的樹， 即二叉樹的每個結點最多有兩個子結點。 二叉樹的基本知識 （2）二叉樹的性質 性質1：在二叉樹的第i層上至多有2i-1個結點（i1）。 性質2：深度為h的二叉樹至多有2h-1個結點（h1）。 一棵深度為k且有2k-1個結點的二叉樹稱為滿二叉樹。 二叉樹的基本知識 （2）二叉樹的性質 性質3：對任何一棵二叉樹，如果其葉結點數n0，度為2的結 點數為n2，則一定滿足：n0=n2+1。 性質4：具有n個結點的完全二叉樹的深度為trunc(l

4、og2n)+1 。 完全二叉樹的定義：深度為k，有n個結點的二叉樹當且僅當其每 一個結點都與深度為k的滿二叉樹中編號從1到n的結點一一對應 時，稱為完全二叉樹。 二叉樹的基本知識 （2）二叉樹的性質 性質5：對于一棵n個結點的完全二叉樹，對任一個結點（編號為i） 如果i=1，則結點i為根，無父結點；如果i1，則其父結點編號為 trunc(i/2)。 如果2in，則結點i無左孩子，即結點i為葉結點；否則左孩子編號為2i。 如果2i+1n，則結點i無右孩子，否則右孩子編號為2i+1。 二叉樹的基本知識 （3）二叉樹的存儲結構 順序存儲 對一個完全二叉樹的所有結點按層編號，將編號為i的結 點存入一維

5、數組的第i個單元。 123456789101112 ABICFJLDEGHK 二叉樹的基本知識 （3）二叉樹的存儲結構 順序存儲 對一個完全二叉樹的所有結點按層編號，將編號為i的結 點存入一維數組的第i個單元。 L D C P F EHN M 12345678910111213 LDPCFM#EH#N 二叉樹的基本知識 （3）二叉樹的存儲結構 鏈式存儲 type node=record data:char; left,right:longint; end; var a:array1n of node; 二叉樹的基本知識 （3）二叉樹的存儲結構 鏈式存儲 struct node char dat

6、a; int left,right; ; node a1001; 二叉樹的基本知識 （3）二叉樹的存儲結構 L D C P F EHN M 123456789 dataLDPCFMEHN left246070000 right350089000 二叉樹的基本知識 （4）二叉樹的建立（順序存儲） s:string; s:=“LDPCFM#EH#N” L D C P F EHN M 12345678910111213 LDPCFM#EH#N 二叉樹的基本知識 （4）二叉樹的建立（順序存儲） string s; s=“LDPCFM#EH#N” L D C P F EHN M 012345678910

7、1112 LDPCFM#EH#N 二叉樹的基本知識 （4）二叉樹的建立（鏈式存儲） L 2 3 D 4 5 P 6 0 C 0 0 F 7 8 M 0 9 E 0 0 H 0 0 N 0 0 L D C P F EHN M 123456789 dataLDPCFMEHN left246070000 right350089000 二叉樹的基本知識 （5）二叉樹的基本運算 1、二叉樹的輸出運算（采用廣義表）： 設標記flag=0 如果當前結點不為空，則輸出該結點； 如果當前結點的左子樹不為空，則輸出“（”， flag=1，遞歸其左子樹； 如果當前結點的右子樹不為空，若flag=0，則輸出“ （”，

8、flag=1，否則輸出“，”，遞歸其右子樹； 如果flag=1，則輸出“）”。 二叉樹的基本知識 （5）二叉樹的基本運算 2、二叉樹的遍歷運算（先序、中序、后序） 先序遍歷的操作定義如下： 若二叉樹為空，則空操作，否則 訪問根結點 先序遍歷左子樹 先序遍歷右子樹 A，B，C，D，E，F，G，H 二叉樹的基本知識 （5）二叉樹的基本運算 2、二叉樹的遍歷運算（先序、中序、后序） 中序遍歷的操作定義如下： 若二叉樹為空，則空操作，否則 中序遍歷左子樹 訪問根結點 中序遍歷右子樹 C，B，A，F，E，G，D，H 二叉樹的基本知識 （5）二叉樹的基本運算 2、二叉樹的遍歷運算（先序、中序、后序） 后序

9、遍歷的操作定義如下： 若二叉樹為空，則空操作，否則 后序遍歷左子樹 后序遍歷右子樹 訪問根結點 C，B，F，G，E，H，D，A 二叉樹的基本知識 （5）二叉樹的基本運算 3、求二叉樹的深度 若二叉樹為空，則深度為0 否則，深度=左子樹與右子樹中最大深度+1 二叉樹的應用 【例1】已知一棵二叉樹的先序遍歷和中序遍歷的結果，請 你編程輸出這棵二叉樹的后序遍歷結果。 【樣例輸入】 ABDEGKHCFI DBKGEHAFIC 【樣例輸出】 DKGHEBIFCA 二叉樹的應用 【分析】 先序：A B D E G K H C F I 中序：D B K G E H A F I C 因為二叉樹的先序遍歷是先訪

10、問根結點A，再遍歷左子 樹，最后遍歷右子樹。而中序遍歷是先遍歷左子樹，再訪 問根結點A，最后遍歷右子樹，所以結點A把中序遍歷的字 符串分成了兩個部分，A之前的是左子樹上的結點，A之后 的是右子樹上的結點。依此類推，便可得到整個二叉樹。 二叉樹的應用 【分析】 先序：A B D E G K H C F I 中序：D B K G E H A F I C A B D E G K H C F I 二叉樹的應用 【分析】 先序：A B D E G K H C F I 中序：D B K G E H A F I C A B D E G K H C F I B D E G K H 先序：A B D E G K

11、 H C F I 中序：D B K G E H A F I C procedure try(l1,r1,l2,r2:longint); var m:longint; begin m:=pos(s1l1,s2); if ml2 then try(l1+1,l1+m-l2,l2,m-1); if ml2)p(l1+1,l1+m-l2,l2,m-1); if (m0)個結點的二叉樹可以看成 是由一個根結點、一棵具有i個結點的左子樹、和一棵具 有n-1-i個結點的右子樹組成，其中0=i=n-1,i=0表示無 左子樹，i=n-1表示無右子樹，根據乘法原理可以得出具 有n個結點的不同形態的二叉樹有Fn棵。

12、 i個結點 n-1-i個結點 二叉樹的應用 【分析】 F0=1 F1=1 F2=F0*F1+F1*F0=1*1+1*1=2 F3=F0*F2+F1*F1+F2*F0=1*2+1*1+2*1=5 Fn=F0*Fn-1+F1*Fn-2+Fn-2*F1+Fn-1*F0 特殊二叉樹 （1）二叉排序樹 1、定義 二叉排序樹具有這樣的性質：任何結點的值都大于它 左子樹上結點的值，小于右子樹上結點的值，然后采用中 序遍歷就可以生成一個有序序列。 3 14 26 5 特殊二叉樹 （1）二叉排序樹 2、建立二叉排序樹 先生成一個結點，加入到樹中，如果不是根結點，再 根據大小決定這個結點是插在某個節點的左子樹上還

13、是右 子樹上，如此重復。 例：3 1 2 4 6 5 3 14 26 5 特殊二叉樹 （1）二叉排序樹 3、二叉排序樹的查找 從根結點開始，如果要查找的數與該結點不相等，則 根據與該結點的值比較，選擇查找左子樹，還是右子樹， 直到沒有結點。 例：查找2 例：查找7 3 14 26 5 P P P P P P P 特殊二叉樹 （2）哈夫曼樹 1、定義 樹的帶權路徑長度為樹中所有葉子結點的帶權路徑長度 之和，也稱WPL。 哈夫曼樹又稱為最優二叉樹，它是n個帶權葉子結點構成 的二叉樹中WPL最小的二叉樹。 4 2 5 9 9 5 24 5924 WPL=5*2+4*2+2*3+9*3=51WPL=9

14、*1+5*2+2*3+4*3=37 WPL=2*2+4*2+5*2+9*2=40 特殊二叉樹 （2）哈夫曼樹 2、構造哈夫曼樹 根據給定的n個權值w1,w2,wn，構造n棵二叉樹的 集合F=T1,T2,Tn，其中每棵二叉樹中均只含一個帶 權值為wi的根結點，其左、右子樹為空樹； 在F中選取其根結點的權值為最小的兩棵二叉樹，分別 作為左、右子樹構造一棵新的二叉樹，并置這棵新的二叉 樹根結點的權值為其左、右子樹根結點的權值之和； 從F中刪去這兩棵樹，同時加入剛生成的新樹； 重復和 兩步，直到F中只含一棵樹為止。 特殊二叉樹 （2）哈夫曼樹 例：對權值分別是3,1,4,5,1,3的結點構造哈夫曼樹。

15、 2 11 3145135 32 11 7 435 32 11 5 10 5 32 11 5 107 43 17 初賽試題 （noip2014普及組選擇題第16題） 1、一棵具有5層的滿二叉樹中結點數為（ ）。 A. 31B. 32C. 33D. 16 （noip2015提高組問題求解第2題） 2、結點數為5的不同形態的二叉樹一共有 種。 （結點數為2的二叉樹一共有2種：一種是根結點和左兒 子，另一種是根結點和右兒子。） 初賽試題 （noip2016普及組選擇題第11題） 3、一棵二叉樹如右圖所示，若采用順序存儲結構，即用 一維數組元素存儲該二叉樹中的結點（根結點的下標為1 ，若某結點的下標為

16、i，則其左孩子位于下標2i處、右孩 子位于下標(2i+1)處），則圖中所有結點的最大下標為 （ ）。 A. 6B. 10C. 12D. 15 初賽試題 （noip2015普及組選擇題第17題、提高組選擇題第8題） 4、如果根的高度為1，具有61個結點的完全二叉樹的高度 為（ ）。 A. 5B. 6C. 7D. 8 (noip2016普及組問題求解第2題） 5、約定二叉樹的根節點高度為1。一棵結點數為2016的二 叉樹最少有 個葉子結點；一棵結點數為2016的二 叉樹最小的高度值是 。 初賽試題 (noip2016提高組選擇題第7題） 6、一棵二叉樹如右圖所示，若采用二叉樹鏈表存儲該二 叉樹（各個結點包括結點的數據、左孩子指針、右孩子指 針）。如果沒有左孩子或者右孩子，則對應的為空指針。 那么該鏈表中空指針的數目為（ ）。 A. 6B. 7C. 12D. 14