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

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