數(shù)據(jù)結(jié)構(gòu)樹與二叉樹詳細(xì)解析

1、1.樹二叉樹遍歷的概念引出了二叉樹和森林哈夫曼樹。第四章樹和二叉樹。2.樹形結(jié)構(gòu)是一種廣泛使用的非線性結(jié)構(gòu)。例如：管理組織、磁盤目錄、家譜等。3。磁盤目錄，4。樹木和森林的概念。樹的定義樹是由n (n 0)個節(jié)點組成的有限集合。如果n=0，它被稱為空樹。如果n為0，則有一個特定的節(jié)點稱為根，它只有直接后繼，但沒有直接前驅(qū)；除了根之外的其他節(jié)點被分成m(m 0)個不相交的有限集合t0，t1，TM-1，并且每個集合是一棵樹，這被稱為根的子樹。5、樹特征，每個子樹的根節(jié)點都有一個且只有一個直接的前置節(jié)點，但可以有0個或更多的直接后續(xù)節(jié)點。，A，C，G，B，D，E，F(xiàn)，K，L，H，M，I，J，6，例5

2、.1: Tree=(D，R) D=Book，C1，C2，C3，C3，Tree是一個層次結(jié)構(gòu)。7.基本術(shù)語：主要來自家譜和樹木。父母，孩子：如果R，據(jù)說A是B and B的父母，是A的孩子；節(jié)點度：節(jié)點擁有的子節(jié)點數(shù)；葉：0度的節(jié)點；分支節(jié)點：度數(shù)大于0的節(jié)點；樹的度：樹的最大節(jié)點度；8，節(jié)點所在的層：根在第一層，其他節(jié)點所在的層是它的父層，加1；深度或高度：節(jié)點所在層的最大層數(shù)；兄弟：父母相同的節(jié)點稱為兄弟；表親：父母雙方在同一個層面上稱對方為非兄弟節(jié)點上的表親；9，祖先：節(jié)點是其所有子樹中節(jié)點的祖先，這些節(jié)點是其后代；路徑：它是節(jié)點序列n1、N2、n3、NK，前一個節(jié)點是后一個節(jié)點的父節(jié)點；

3、它的長度是k-1；有序樹：每個節(jié)點的子節(jié)點從左到右依次排列；否則它就是一棵亂樹；10，節(jié)點A、b和c的度數(shù)分別是3、2和1，葉是k、l、F、G、m、I和j，節(jié)點A的子節(jié)點是b、c和d，節(jié)點b的子節(jié)點是e和F，節(jié)點I的父節(jié)點是d，節(jié)點l的父節(jié)點是e，節(jié)點b、c和e。節(jié)點A是節(jié)點F、G、11的祖先，是33，360m(m 0)不相交樹的集合。12、二叉樹、五種不同形式的二叉樹、13和屬性1。如果二叉樹的級別從1開始，那么二叉樹的I級最多有2i -1。(1)通過數(shù)學(xué)歸納法證明了深度為k的二叉樹最多有2k-1個節(jié)點。(h 1)證明對于任何二叉樹，如果有n0個葉節(jié)點和n2個非葉節(jié)點的度為2，那么就有n0n

4、21來證明如果有n1個節(jié)點的度為1，匯總點數(shù)為n，邊的總數(shù)為e，根據(jù)二叉樹的定義，n=n0n 1n 2e=2n n1=n-1。因此，有2n2n 1=n0n 1 N2-1n 2=n0-1n 0=n21，15。定義1個完整二叉樹和2個完整二叉樹。如果二叉樹的高度是h，則有h 1層。除了h層，其他層(0 h-1)的節(jié)點數(shù)都達到最大，h層從右到左連續(xù)缺少幾個節(jié)點，是一個完整的二叉樹。(功能)，16，葉節(jié)點只出現(xiàn)在兩個最大的級別。對于任何節(jié)點，如果它的右子樹的高度是L，那么它的左子樹的高度是L或1，17，并且在屬性4中具有n (n 0)個節(jié)點的完整二叉樹的高度是log2(n 1) -1。證明了完全二叉樹

5、的高度為H，則2h-1 n 2h 1-1是變形的2h n 1 2h 1取log2 (n 1) h 1有l(wèi)og2(n 1)=h 1 h=log2(n 1) -1，并且H層上層的節(jié)點數(shù)，包括H層的最大節(jié)點數(shù)，18，性質(zhì)5，如把一個完全二叉樹從上到下放n個節(jié)點， 如果在同一層中節(jié)點從左到右連續(xù)編號為0、1、2和n-1，則存在以下關(guān)系：如果i=0，則我沒有父母，則我的父母是(i -1)/2，如果2*i 1 n，則我的左孩子是2*i 1，如果2*i 2 n，則我的右孩子是2 * i2if=0，則它的左兄弟是i -1，如果我是奇數(shù)，則我！=n-1，那么它的右兄弟是i 1。節(jié)點I的級別是log2(i 1)，

6、19，這是一個二叉樹的抽象數(shù)據(jù)類型。數(shù)據(jù)是一組有限的節(jié)點。當(dāng)D不為空時，有一個節(jié)點T，其他節(jié)點被分成T的左子樹和右子樹。操作構(gòu)造器進程：建立一個空的二叉樹。刪除進程：刪除二叉樹，20，空進程：判斷二叉樹是否為空。如果二叉樹為空，輸出：返回真。否則，返回false Size進程：計算二叉樹的節(jié)點數(shù)大小輸出：大小高度進程：計算二叉樹的高度高度輸出：高度根進程：取二叉樹的根節(jié)點值x Output333。60個根節(jié)點x，21，Parent Input:節(jié)點的值是二叉樹中的一個節(jié)點。進程：找到節(jié)點的父p。如果節(jié)點是根，P為空，輸出：p創(chuàng)建二進制樹輸入：一個定義進程：根據(jù)這個定義構(gòu)造一個二叉樹，生成樹輸入

7、：數(shù)據(jù)是根節(jié)點值，左是左子樹，右是右子樹進程：創(chuàng)建的二叉樹，數(shù)據(jù)是根節(jié)點值，左是其左子樹，右是其右子樹，22，BreakTree進程3360拆分二叉樹，數(shù)據(jù)是根節(jié)點數(shù)據(jù)，左右是右子樹輸出：數(shù)據(jù)，左、右是前序輸入：訪問()是節(jié)點訪問函數(shù)Process:它調(diào)用Visit()一次，根據(jù)Visit()對二叉樹中的每個節(jié)點只調(diào)用一次。 按照前序遍歷序列得到的結(jié)果是，節(jié)點訪問函數(shù)Process:調(diào)用visit()一次，根據(jù)Visit()對二叉樹中的每個節(jié)點只調(diào)用一次，按照中間順序遍歷序列得到的結(jié)果是23。Postorderinput3360Visit()是節(jié)點訪問函數(shù)Process:調(diào)用Visit()一次

8、，根據(jù)visit()對二叉樹中的每個節(jié)點只調(diào)用一次。遍歷序列得到結(jié)果等級順序輸入：訪問()是節(jié)點訪問函數(shù)進程：根據(jù)訪問()對二叉樹中的每個節(jié)點調(diào)用一次訪問()并且只調(diào)用一次，然后遍歷序列得到結(jié)果。/二叉樹，24，一個完整的二叉樹通常由二叉樹的序列來表示。25.在極端情況下：只有正確的單個二叉樹，26。二叉樹鏈表，27。二叉樹鏈表，28。二叉樹鏈表的例子。二叉樹的二進制鏈表。二進制鏈表中的節(jié)點定義如下：二進制綠色節(jié)點*左子節(jié)點，*右子節(jié)點；/左指針，右指針public:二叉樹節(jié)點(datatype/二叉樹節(jié)點，二叉樹的鏈表實現(xiàn)，30，類二叉樹二叉樹二叉樹節(jié)點*根；/根節(jié)點指針public:二叉樹

9、()根=null/創(chuàng)建一個空的二叉樹bool IsEmpty()；/如果二叉樹為空，返回真；否則，返回false bool Root(DataType /通過擴展二叉樹的遍歷序列來創(chuàng)建二叉樹。二進制鏈表的定義如下：31，空生成樹(DataType /逐層遍歷，/其中訪問是遍歷的過程參數(shù)，負(fù)責(zé)訪問節(jié)點。，32，void delete(二叉樹節(jié)點*，33，boolroot(datatype/創(chuàng)建一個新的二叉樹，34，遍歷二叉樹，遍歷二叉樹是以一定的順序訪問樹中的節(jié)點，要求每個節(jié)點只訪問一次。假設(shè)訪問根節(jié)點表示為V，遍歷根的左子樹表示為L，遍歷根的右子樹表示為R，35，可能的遍歷順序，前序VLR鏡像

10、LVR鏡像RVL后序LRV鏡像RLV，36，以及前序遍歷：如果BT不為空，則為：1。訪問根；2.遍歷序言中的左子樹；3.按照前面的順序遍歷右子樹；中間順序遍歷：如果BT不為空，則為：1。左子樹的中間順序遍歷；2.訪問根3。以中間順序遍歷右子樹；后序遍歷：如果BT不是空的，那么：1。左子樹的后序遍歷；2.依次遍歷右子樹；3.訪問根，遍歷算法，37。遍歷結(jié)果的遍歷順序：a b * c-d-e/f前言：-a * b-c d/e f后置：a b c d-* e f/-，38，練習(xí)3360，給出二叉樹的前序、中序和后序的遍歷順序。前言遍歷序列：ABDGCEFH中序遍歷序列：DGBAECHF逆序遍歷序列：

11、GDBEHFCA，39，二叉樹遞歸算法的前綴遍歷空二叉樹：3360的前序(二叉樹節(jié)點*，40，二叉樹遞歸空二叉樹：的中序遍歷算法的順序(二叉樹節(jié)點*，41)，后序遍歷算法的空二叉樹33603360的后序(二叉樹節(jié)點*，42)，計算二叉樹的節(jié)點數(shù)int Size (BinaryTreeNode *，二叉樹遍歷的一個例子，43)，int Depth (BinaryTreeNode *，通過使用二叉樹的順序遍歷計算二叉樹的高度，44，并遞歸地構(gòu)建二叉樹。 遞歸退出：當(dāng)遇到時，它是空的。建立一個根節(jié)點。建立左子樹和右子樹。二叉樹用根字符序列和左右子樹的字符序列表示，而空樹用空格(或某個字符)表示。例如

12、，“或“-1”用于表示字符序列或正整數(shù)序列的空節(jié)點。二叉樹是通過二叉樹的預(yù)序遍歷建立的，45。如圖所示，二叉樹的前序遍歷序列是A B C D E G F序列，它是擴展二叉樹的前序遍歷序列。是一個擴展的葉節(jié)點，它表示一個空指針。，46，建立二叉樹的算法(二進制鏈表):無效創(chuàng)建二進制樹(二進制樹節(jié)點*創(chuàng)建二進制樹，47，遍歷二叉樹的非遞歸算法，讓我們首先觀察三種路徑預(yù)遍歷。，否則：將頂部元素堆疊成p；拜訪p。p指的是正確的孩子；4.結(jié)束，52。思考：非遞歸序遍歷算法？中序遍歷二叉樹算法思想：建立棧；p指向根；當(dāng)p不為空或堆棧不為空時重復(fù)：如果p不為空，則p被放入堆棧；p指向左邊的孩子；否則：將頂部

13、元素堆疊成p；拜訪p。p指的是正確的孩子；4.最后，序言中遍歷二叉樹的非遞歸算法思想：建立棧；p指向根；當(dāng)p不為空或堆棧不為空時，重復(fù)執(zhí)行：如果p不為空，訪問p并將其放在堆棧上；p指向左邊的孩子；否則：將頂部元素堆疊成p；p指的是正確的孩子；結(jié)束，53，例如，堆棧堆棧；/在(p |！堆棧。IsEmpty()而(p)堆棧。推動(p)。coutp-數(shù)據(jù)；p=p-LeftChild；/向左走，否則p=stack。pop()；p=p-right child；/向右/當(dāng)/InOrder，76時，算法思想是非遞歸的，然后遍歷。1.建立棧棧；2.p指向根；3.當(dāng)P不為空或堆棧不為空時重復(fù)：如果P不為空：(P，L)堆棧；向左走一步；否則：將頂部元素堆疊成p和標(biāo)記；如果標(biāo)簽=R :訪問p