歡迎來到技術文庫! | 幫助中心 管理技術提升個人能力?。▏鴥韧艘圮娙耸讋撝R共享平臺)
                    技術文庫
                    全部分類
                  1. 化工機械>
                    石油標準 機械標準 閥門標準
                  2. 國外標準>
                    JIS標準 BS標準 ASME標準
                  3. 行業標準>
                    煤礦能源 鐵路標準 船舶標準
                  4. 管理文獻>
                    經營企劃 財務管理 生產管理
                  5. 建筑標準>
                    通用標準 建筑機械 建材標準
                  6. 書簽 分享 收藏 舉報 版權申訴 / 44

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

                  7. 上傳人:sk****8
                  8. 文檔編號:21435861
                  9. 上傳時間:2019-05-02
                  10. 格式:PPT
                  11. 頁數:44
                  12. 大?。?.22MB
                  13. 配套講稿:

                    如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。

                    特殊限制:

                    部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設計者僅對作品中獨創性部分享有著作權。

                    關 鍵  詞:
                    noip 普及 講座 基礎知識
                    資源描述:

                    《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

                    展開閱讀全文
                    提示  技術文庫所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
                    關于本文
                    本文標題:noip普及講座5-樹的基礎知識
                    鏈接地址:http://www.roomav.net/p-21435861.html
                    關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服 - 聯系我們
                    手機版 | MIP | 粵公網安備 44060602000677號 | 經營許可證(粵ICP備16048919號)| 本站法律顧問陳鑫輝律師(13807302170)
                    技術文庫(國內退役軍人首創知識共享平臺)?2008-2022 by Guangdong Foushan Jswku.com Inc. All Rights Reserved.
                    本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。平臺僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對上載內容本身不做任何修改或編輯。若文檔所含內容侵犯了您的版權或隱私,請立即通知技術文庫,我們立即給予刪除!


                     

                    收起
                    下載幫助
                    侵權處理
                    上傳問題
                    展開
                    她握着他的巨大坐了下去