西安交通大學數(shù)據(jù)結構復習資料(已改無錯字)
2023-05-18 12:21:46 本頁面
【正文】 特點: v 除最后一層，第 i層有2i1個結點； v 葉子只可能出現(xiàn)在最后兩層；v 結點右子樹深度為i時，左子樹深度為i或i+1。理想平衡二叉樹：在一棵二叉樹中，若除最后一層外，其余層都是滿的，而最后一層上的結點可以任意分布，則稱此樹為理想平衡二叉樹,簡稱理想平衡樹或理想二叉樹。v 顯然，理想平衡樹包含滿二叉樹和完全二叉樹。完全二叉樹中深度h和結點數(shù)n之間的關系，在理想平衡樹中同樣成立，了解二叉樹的鏈接存儲結構根據(jù)二叉樹的特性，任何一個結點最多有左、右兩棵子樹，所以每個結點至少設有三個域：數(shù)據(jù)域和左、右指針域。其結點結構為：Leftdataright其中data表示值域，用于存儲對應的數(shù)據(jù)元素，left和right分別表示左指針域和右指針域，用以分別存儲左孩子和右孩子結點的存貯位置（即指針）v 鏈接存儲的另一種方法是：在上面的結點結構中再增加一個parent指針域，用來指向其雙親結點。這種存儲結構既便于查找孩子結點，也便于查找雙親結點，當然也帶來存儲空間的相應增加。lchilddataparentrchild熟悉二叉樹的4種遍歷方法，能按任何一種遍歷方法來寫出給定樹的遍歷序列(1) 先序遍歷：若二叉樹為空，則空操作；否則① 訪問根結點； ② 先序遍歷左子樹； { 先訪問左子樹根節(jié)點；再遍歷左子樹根節(jié)點的左子樹，再遍歷左子樹根節(jié)點的右子樹；……直至遍歷完所有左子樹的節(jié)點}③ 先序遍歷右子樹。 { 先訪問右子樹根節(jié)點；再遍歷右子樹根節(jié)點的左子樹，再遍歷右子樹根節(jié)點的右子樹；……直至遍歷完所有右子樹的節(jié)點}(2) 中序遍歷： 若二叉樹為空，則空操作；否則 ① 中序遍歷左子樹。 （遍歷的過程與先根級的遞歸遍歷類似） ② 訪問根結點； ③ 中序遍歷右子樹 （遍歷過程與先根級的遞歸遍歷相同）(3) 后序遍歷：若二叉樹為空，則空操作；否則 ① 后序遍歷左子樹； ② 后序遍歷右子樹。 ③ 訪問根結點；（4）按層遍歷二叉樹：① 訪問根結點；②遍歷左子樹根結點；③遍歷右子樹根結點。熟悉樹的遍歷序列與樹結構之間的關系，并能由特定的遍歷序列來恢復樹結構和寫出另外的遍歷序列熟悉樹與二叉樹的共性和差異之處熟悉樹的幾種遍歷算法能根據(jù)樹的定義（包括結點類型的定義）編程實現(xiàn)樹的一些基本運算第六章 二叉樹的應用了解二叉搜索樹的定義，性質并能根據(jù)定義由給定序列構造二叉搜索樹v 二叉搜索樹(Binany Searching Tree)又稱做二叉排序樹(Binary Sorting Tree)，它或者是一棵空樹，或者是一棵具有如下特性的非空二叉樹。 (1) 若它的左子樹非空，則左子樹上所有結點的關鍵字均小于樹根結點的關鍵字； (2) 若它的右子樹非空，則右子樹上所有結點的關鍵字均大于樹根結點的關鍵字； (3) 左、右子樹本身又各是一棵二叉搜索樹。 在一個二叉搜索樹中，當每個結點的元素類型為簡單類型時，則結點的關鍵字就為該結點的值；當結點的元素類型為記錄類型時，則結點的關鍵字為該結點的某一個域的值。v 由二叉搜索樹的定義可知，在一棵非空的二叉搜索樹中，其結點的關鍵字是按照左子樹、根和右子樹有序的，所以對它進行中序遍歷得到的結點序列必然是一個有序序列。了解二叉搜索樹應用于查找時的特性及指標v 在二叉搜索樹上進行查找的過程中，給定值item同樹中結點比較的次數(shù)最少為一次（即樹根結點就是待查的結點)，最多為樹的深度，所以平均查找次數(shù)要小于等于樹的深度。v 若二叉搜索樹是一棵理想平衡樹或接近理想平衡樹，則進行查找的時間復雜度為O(log2n)，v 若為一棵單支樹(這是最極端和最差的情況)，則其時間復雜度為O(n)，v 一般情況而言，其時間復雜度可大致可看做為O(log2n)。 由此可知，在二叉搜索樹上查找比在集合或線性表上進行順序查找的時間復雜度O(n)要小得多，這正是構造二叉搜索樹的優(yōu)勢所在。二叉搜索樹查找的遞歸算法的空間復雜度平均情況為O(log2n)，最差情況為O(n)，非遞歸算法的空間復雜度為O(1)。了解堆的定義和性質堆(Heap)分為小根堆和大根堆兩種，對于一個小根堆，它是具有如下特性的一棵完全二叉樹。(1) 若樹根結點存在左孩子，則樹根結點的值小于等于左孩子結點的值；(2) 若樹根結點存在右孩子，則樹根結點的值小于等于右孩子結點的值；(3) 以左、右孩子為根的子樹又同樣各是一個堆。 大根堆的定義與上述類似，只要把小于等于改為大于等于就得到了。v 若一棵完全二叉樹是堆，則該樹中以每個結點為根的子樹也都是一個堆。v 堆頂結點具有最小值(——對應于小根堆）或最大值（—— 對應于大根堆)。能采用給定的數(shù)據(jù)序列來生成一個堆（大根堆或小根堆）了解樹的帶權路徑，以及哈夫曼樹（最優(yōu)二叉樹）的概念和性質(1) 路徑和路徑長度若在一棵樹中存在著一個結點序列k1,k2,…,kj，使得ki是ki+1的雙親(1≤ij)，則稱此結點序列是從k1到kj的路徑。也就是說，在二叉樹中，一個結點到另一個結點之間的分支構成這兩個結點之間的路徑。因樹中每個結點只有一個雙親結點，所以它也是這兩個結點之間的惟一路徑。從k1到kj所經過的分支數(shù)稱為這兩點之間的路徑長度，它等于路徑上的結點數(shù)減1。 (2) 結點的權和帶權路徑長度 在許多應用中，常常將樹中的結點賦予一個有著某種意義的實數(shù)，我們稱此實數(shù)為該結點的權。結點的帶權路徑長度規(guī)定
教學教案相關推薦
鄂ICP備17016276號-1