高中二年級(jí)下學(xué)期信息科技《用抽象數(shù)據(jù)類型表示二叉樹(shù)》教學(xué)課件

選擇性必修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》4.3用抽象數(shù)據(jù)類型表示二叉樹(shù)|一、樹(shù)tree|樹(shù)tree|線性關(guān)系：即每一個(gè)數(shù)據(jù)元素通常只有一個(gè)前驅(qū)（除第一個(gè)元素外）和一個(gè)后繼（除最后一個(gè)元素外）；如：隊(duì)列，棧非線性結(jié)構(gòu)：至少存在一個(gè)結(jié)點(diǎn)（數(shù)據(jù)元素）有多于一個(gè)前驅(qū)或后繼的數(shù)據(jù)結(jié)構(gòu)；如：樹(shù)，圖樹(shù)tree|在我們?nèi)粘Ｉ钪?，?shù)形結(jié)構(gòu)廣泛存在。王貴王永勝王家莉王永前王家棟王家梁王家輝家族成員關(guān)系樹(shù)樹(shù)tree1.樹(shù)的定義樹(shù)是n(n>0)個(gè)結(jié)點(diǎn)的有限集，在任意一棵非空樹(shù)中：①有且僅有一個(gè)特定的結(jié)點(diǎn)稱為根；②當(dāng)n>1時(shí)，其余結(jié)點(diǎn)分為m(m>0)棵互不相交的有限子樹(shù)，每棵子樹(shù)又是一棵樹(shù)。樹(shù)tree2.結(jié)點(diǎn)的分類

①根結(jié)點(diǎn)：沒(méi)有父親的結(jié)點(diǎn)。在樹(shù)中有且僅有一個(gè)根結(jié)點(diǎn)。②分支結(jié)點(diǎn)：除根結(jié)點(diǎn)外，有孩子的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。③葉結(jié)點(diǎn)：沒(méi)有孩子的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)。如w,h,e等為葉結(jié)點(diǎn)3.有關(guān)度的定義①結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹(shù)數(shù)目稱為該結(jié)點(diǎn)的度。如圖中結(jié)點(diǎn)i度為3，結(jié)點(diǎn)t的度為2，結(jié)點(diǎn)b的度為1，所有樹(shù)葉的度為0。②樹(shù)的度：所有結(jié)點(diǎn)中最大的度稱為該樹(shù)的度(也叫樹(shù)的寬度），圖中樹(shù)的度為3。樹(shù)tree4.樹(shù)的深度（高度）樹(shù)是分層次的。結(jié)點(diǎn)所在的層次是從根算起的。根結(jié)點(diǎn)在第一層，根的兒子在第二層，其余各層依次類推。同一父結(jié)點(diǎn)的所有結(jié)點(diǎn)構(gòu)成兄弟關(guān)系樹(shù)的層數(shù)稱為樹(shù)的深度(也稱為樹(shù)的高度)。上圖中樹(shù)的深度為55.森林所謂森林，是指若干棵互不相交的樹(shù)構(gòu)成的集合。如圖去掉根結(jié)點(diǎn)r，其原來(lái)的三棵子樹(shù)Ta，Tb，Tc就構(gòu)成了森林，如圖(c)二、二叉樹(shù)Binarytree||二叉樹(shù)Binarytree二叉樹(shù)是一種很重要的樹(shù)結(jié)構(gòu)特點(diǎn)：每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，且其子樹(shù)有左右之分（稱為有序樹(shù)，其次序不能任意顛倒）1256743|二叉樹(shù)Binarytree1.二叉樹(shù)的遞歸定義和基本形態(tài)二叉樹(shù)是以結(jié)點(diǎn)為元素的有限集，可為空，或者滿足以下條件：⑴有一個(gè)特定的結(jié)點(diǎn)稱為根；⑵余下的結(jié)點(diǎn)分為互不相交的兩個(gè)子集L和R，其中L是根的左子樹(shù)；R是根的右子樹(shù)；L和R分別又是一棵二叉樹(shù)；由上述定義可以看出，二叉樹(shù)和樹(shù)是兩個(gè)不同的概念，其區(qū)別為：⑴樹(shù)的每一個(gè)結(jié)點(diǎn)可以有任意多個(gè)后繼，而二叉樹(shù)中每個(gè)結(jié)點(diǎn)的后繼不能超過(guò)2個(gè)⑵樹(shù)的子樹(shù)可以不分次序（除有序樹(shù)外）；而二叉樹(shù)的子樹(shù)有左右之分。我們稱二叉樹(shù)中結(jié)點(diǎn)的左后繼為左兒子，右后繼為右兒子。1256743|二叉樹(shù)Binarytree下圖列出二叉樹(shù)的五種基本形態(tài)：空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)只有左子樹(shù)的二叉樹(shù)只有右子樹(shù)的二叉樹(shù)左、右子樹(shù)均有的二叉樹(shù)|二叉樹(shù)Binarytree2.常見(jiàn)的兩種二叉樹(shù)⑴滿二叉樹(shù)：如果一棵深度為K的二叉樹(shù)，共有2K-1個(gè)結(jié)點(diǎn)，即第i層有2i-1的結(jié)點(diǎn)，則稱為滿二叉樹(shù)⑵完全二叉樹(shù)：如果一棵二叉樹(shù)最多只有最下面兩層結(jié)點(diǎn)度數(shù)可以小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則稱為完全二叉樹(shù)注意：滿二叉樹(shù)一定是完全二叉樹(shù)，但是完全二叉樹(shù)不一定是滿二叉樹(shù)136754213675428910三、二叉樹(shù)的抽象數(shù)據(jù)類型Abstractdatatypeofbinarytree|二叉樹(shù)的抽象數(shù)據(jù)類型Abstractdatatypeofbinarytree|二叉樹(shù)的抽象數(shù)據(jù)類型的數(shù)據(jù)部分為一棵用任一種方式表示的二叉樹(shù)操作部分包括初始化二叉樹(shù)、建立二叉樹(shù)、遍歷二叉樹(shù)、查找二叉樹(shù)、輸出二叉樹(shù)和清除二叉樹(shù)等常用操作。下面給出二叉樹(shù)的抽象數(shù)據(jù)類型的參考定義:二叉樹(shù)的抽象數(shù)據(jù)類型Abstractdatatypeofbinarytree|四、二叉樹(shù)的基本操作方法Basicoperationmethodofbinarytree|二叉樹(shù)的基本操作方法Basicoperationmethodofbinarytree|二叉樹(shù)的基本操作較多，下面以遍歷為例，了解二叉樹(shù)的基本操作方法。遍歷是二叉樹(shù)的一種基本操作，是指按一定的次序訪問(wèn)樹(shù)中所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)的值僅被訪問(wèn)一次的過(guò)程。由于二叉樹(shù)是非線性結(jié)構(gòu)，因此二叉樹(shù)的遍歷實(shí)質(zhì)上是將二叉樹(shù)的所有結(jié)點(diǎn)轉(zhuǎn)換成一個(gè)線性序列的過(guò)程。根據(jù)二叉樹(shù)的遞歸定義，一棵非空二叉樹(shù)由根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)所組成。因此，遍歷一棵非空二叉樹(shù)的問(wèn)題可分解為三個(gè)子問(wèn)題：訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹(shù)、遍歷右子樹(shù)。若用L、D、R分別表示遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)和遍歷右子樹(shù)，則對(duì)一棵二叉樹(shù)的遍歷有DLR、LDR、LRD、DRL、RDL、RLD六種情況，若限定先左后右，則只有前三種情況，分別稱為前序遍歷(或先根遍歷)、中序遍歷(或中根遍歷)、后序遍歷(或后根遍歷)。二叉樹(shù)的基本操作方法Basicoperationmethodofbinarytree|（1）前序遍歷：根左右。即先遍歷根結(jié)點(diǎn)，再遍歷左子樹(shù)，最后遍歷右子樹(shù)acfhgedbabdegcfh（2）中序遍歷：左根右。即先遍歷左子樹(shù)，再遍歷根結(jié)點(diǎn)，最后遍歷右子樹(shù)dbgeafhc（3）后序遍歷：左右根。即先遍歷左子樹(shù)，再遍歷右子樹(shù)，最后遍歷根結(jié)點(diǎn)dgebhfca課后任務(wù)|【表達(dá)式樹(shù)】：我們可以分別用先序、中序、后序的遍歷方法得出完全不同的遍歷結(jié)果，如對(duì)于右圖3種遍歷結(jié)果如下，它們正好對(duì)應(yīng)著表達(dá)式的3種表示方法。①-+a*b-cd/ef(前綴表示、波蘭式)②a+b*c-d