樹和二叉樹副本知識(shí)講解.ppt

《樹和二叉樹副本知識(shí)講解.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、樹和二叉樹副本樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)。樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種組織機(jī)構(gòu)都可以用樹來形象表示。族譜組織機(jī)構(gòu)定義定義：樹(tree)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集T，在任意一棵非空樹中：有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹的根(root)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,……Tm，其中每一個(gè)集合本身又是一棵樹，稱為根的子樹(subtree)特點(diǎn)：樹中有一個(gè)結(jié)點(diǎn)——根樹中各子樹是互不相交的集合5.1樹的定義和基本術(shù)語A只有根結(jié)點(diǎn)的樹ABCDEFGHIJ

2、KLM有子樹的樹根子樹T1T2T32021年9月8日5.1樹的定義和基本術(shù)語樹是n個(gè)結(jié)點(diǎn)的有限集T1T2T3有子樹的樹和線性結(jié)構(gòu)的比較線性結(jié)構(gòu)??????????????樹結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素(無前驅(qū))根結(jié)點(diǎn)(無前驅(qū))最后一個(gè)數(shù)據(jù)元素(無后繼)多個(gè)葉子結(jié)點(diǎn)(無后繼)其它數(shù)據(jù)元素??????????????樹中其它結(jié)點(diǎn)(一個(gè)前驅(qū)、一個(gè)后繼)??????(一個(gè)前驅(qū)、多個(gè)后繼)2021年9月8日ADTTree{數(shù)據(jù)對(duì)象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTTree若D為空集，則稱為空樹；//允許n=0若D中僅含一個(gè)數(shù)據(jù)元素，則R為空集；其他情

3、況下的R存在二元關(guān)系：①root唯一//關(guān)于根的說明②Dj∩Dk=Φ//關(guān)于子樹不相交的說明③……//關(guān)于數(shù)據(jù)元素的說明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有15個(gè)樹的抽象數(shù)據(jù)類型定義2021年9月8日凹入表示嵌套集合廣義表樹的其它表示方式2021年9月8日根葉子森林——即根結(jié)點(diǎn)(沒有前驅(qū))——即終端結(jié)點(diǎn)(沒有后繼)——指m棵不相交的樹的集合(例如刪除A后的子樹個(gè)數(shù))基本術(shù)語基本術(shù)語——即樹的數(shù)據(jù)元素——結(jié)點(diǎn)掛接的子樹數(shù)結(jié)點(diǎn)結(jié)點(diǎn)的度結(jié)點(diǎn)的層次終端結(jié)點(diǎn)分支結(jié)點(diǎn)樹的度樹的深度(或高度)——從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）——即

4、度為0的結(jié)點(diǎn)，即葉子——即度不為0的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)）——所有結(jié)點(diǎn)度中的最大值——指所有結(jié)點(diǎn)中最大的層數(shù)層次1234——即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū))——即下層結(jié)點(diǎn)的子樹的根(直接后繼)——同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）——即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）——即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)——即該結(jié)點(diǎn)下層子樹中的任一結(jié)點(diǎn)雙親孩子兄弟堂兄弟祖先子孫基本術(shù)語有序樹：若從樹中結(jié)點(diǎn)的各個(gè)子樹看是從左到右有序的（不可互換），則稱為有序樹，否則為無序樹。ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉

5、子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先2021年9月8日5.2二叉樹普通樹（多叉樹）若不轉(zhuǎn)化為二叉樹，則運(yùn)算很難實(shí)現(xiàn)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”的樹？二叉樹的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；可以證明，所有樹都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹，不失一般性。二叉樹的定義二叉樹是n(n?0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分

6、別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成特點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹(結(jié)點(diǎn)的度小于等于2）有序樹：二叉樹的子樹有左、右之分，且其次序不能任意顛倒2021年9月8日二叉樹的五種不同形態(tài)2021年9月8日具有3個(gè)結(jié)點(diǎn)的二叉樹可能有幾種不同形態(tài)？普通樹呢？練習(xí)5種/2種2021年9月8日ADTBinaryTree{數(shù)據(jù)對(duì)象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTBinaryTree若D=Φ，則R=Φ；若D≠Φ，則R={H}；存在二元關(guān)系：①root唯一//關(guān)于根的說明②Dj∩Dk=Φ//關(guān)于子樹不相交的說明③……//關(guān)于數(shù)據(jù)元素的說明④……/

7、/關(guān)于左子樹和右子樹的說明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有20個(gè)二叉樹的抽象數(shù)據(jù)類型定義2021年9月8日性質(zhì)1:在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)二叉樹的性質(zhì)提問：第i層上至少有個(gè)結(jié)點(diǎn)？1證明：用歸納法證明之?i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，是對(duì)的?假設(shè)對(duì)所有j(1?j

8、結(jié)點(diǎn)提問：深度為k時(shí)至少有個(gè)結(jié)點(diǎn)？k證明：由性質(zhì)1，可得深度為k的二叉樹最大結(jié)點(diǎn)數(shù)是2021年9月8日性質(zhì)3:對(duì)于任何一棵二叉樹，若2度的結(jié)點(diǎn)數(shù)有n2個(gè)，則葉子數(shù)n0必定為n2＋1（即n0=n2+1）性質(zhì)3：對(duì)任何一棵二叉樹T，如果其