西安交通大學數(shù)據(jù)結(jié)構(gòu)復習資料-文庫吧資料
2025-04-23 12:21本頁面
【正文】 對應的數(shù)據(jù)元素，left和right分別表示左指針域和右指針域，用以分別存儲左孩子和右孩子結(jié)點的存貯位置（即指針）v 鏈接存儲的另一種方法是：在上面的結(jié)點結(jié)構(gòu)中再增加一個parent指針域，用來指向其雙親結(jié)點。v 顯然，理想平衡樹包含滿二叉樹和完全二叉樹。 特點: v 除最后一層，第 i層有2i1個結(jié)點； v 葉子只可能出現(xiàn)在最后兩層；v 結(jié)點右子樹深度為i時，左子樹深度為i或i+1。 第i層有2i1個結(jié)點；全部分支結(jié)點度為2。log2nlog2(n+1)249。 此性質(zhì)可以從樹的相應性質(zhì)中直接導出，也可以進行如下證明。log2nlog2(n+1)249。此點也適合于一般二叉樹。n/2 (3) 若編號為i的結(jié)點有左孩子，則左孩子結(jié)點的編號為2i；若編號為i的結(jié)點有右孩子，則右孩子結(jié)點的編號為2i+1，即遵循對一般二叉樹的編號規(guī)則。表示對x進行向下取整。表達式235。n/2 由于在二叉樹中，任一結(jié)點的度數(shù)小于或等于2，所以其結(jié)點總數(shù)n為: n = n0 + n1 + n2 (n0 :終端結(jié)點。性質(zhì)3：若二叉樹的葉子結(jié)點數(shù)為n0，度為2的結(jié)點有n2個,則有：n0=n2+1證明: (1)v 性質(zhì)1：在二叉樹第i 層上最多有2i1個結(jié)點( i≥1)。它是一種樹結(jié)構(gòu),在計算機領域有著廣泛地應用。 表示對x進行向上取整熟悉二叉樹的定義及基本性質(zhì)，并能根據(jù)這些性質(zhì)進行相關推理和計算。注： 233。因此得到具有n個結(jié)點的一般k叉樹的最小深度為： 233。 證明：設k叉樹的最小深度為h，則： 前h1層滿的 k叉樹結(jié)點數(shù) n≤ h層都滿的k叉樹結(jié)點數(shù)，因此有： 上式可變換為： kh1 n (k1)+1 ≤ kh 以k為底取對數(shù)可得： h1 logk( n(k1)+1) ≤h 即： logk( n(k1)+1) ≤h logk( n(k1)+1)+1因k只能為整數(shù)，所以： h=233。logk(n(k1)+1)249。 證明：利用性質(zhì) 2來證明，k 叉樹的最大結(jié)點數(shù)為每一層最大結(jié)點數(shù)之和，則有： 當一棵k叉樹上的結(jié)點數(shù)等于 時，則稱該樹為滿k叉樹。 對于第i層，最多結(jié)點數(shù)為：= ki1 命題得證。 用數(shù)學歸納法證明： 對于 i=1, ki1 =k0 =1 命題成立。 證明：根據(jù)定義：除根結(jié)點外，每個結(jié)點有一個分支指向。 無序樹：結(jié)點的子樹順序任意。也即樹T中各子樹T1，T2，…，Tn的相對次序是有意義的。v 子孫結(jié)點：每個結(jié)點的所有子樹中的結(jié)點被稱為該結(jié)點的子孫結(jié)點v 祖先結(jié)點：從整個（子）樹的根結(jié)點到達該結(jié)點的路徑上經(jīng)過的所有分支結(jié)點v 結(jié)點層次：從根結(jié)點開始，根結(jié)點為第1層，根結(jié)點的孩子為第2層，依此類推 1 A ………..第1層 2 B 3 C 4 D …. 第2層 5 E 6 F G 7 ……... 第3層樹的深度：樹中結(jié)點的最大層次。v 兄弟結(jié)點(sibling)：同一個雙親的孩子之間互為兄弟。v 孩子結(jié)點(child) ：某結(jié)點子樹的根或者說某個結(jié)點的后繼被稱為該結(jié)點的孩子結(jié)點。 v 葉子結(jié)點：度為零的結(jié)點稱葉子結(jié)點或終端結(jié)點。 v 結(jié)點的度：樹中每個結(jié)點具有的非空子樹數(shù)或者說后繼結(jié)點數(shù)被定義為該結(jié)點的度（degree）。v 由于隊列的插入和刪除操作分別是在各自的一端進行的，每個元素必然按照進入的次序離隊，所以又把隊列稱為先進先出表（first in first out, 簡稱FIFO）。v 我們把進行插入的一端稱作隊尾(rear)，進行刪除的一端稱作隊首(front)。第四章 棧和隊列了解棧的定義及性質(zhì)棧（stack）又稱堆棧，它是一種運算受限的線性表，其限制是僅允許在表的一端進行插入和刪除運算。動態(tài)鏈表是順序存儲結(jié)構(gòu)，表中的任一結(jié)點都需要從頭指針起順鏈掃描才能取得，時間復雜度為O(n)(n為表長)。 了解線性表的順序與鏈式存儲在不同操作場合下的時間復雜度指標順序表是隨機存儲結(jié)構(gòu)，表中任一數(shù)據(jù)元素都可以通過計算直接得到地址進行存取，時間復雜度為O(1)。當頭結(jié)點的指針域為“空”時，單鏈表為空鏈表熟悉單鏈表中結(jié)點的定位、插入、刪除、查詢的算法思想和操作程序了解線性表的順序與鏈式存儲各自的優(yōu)點、不足與它們適用場合。頭結(jié)點數(shù)據(jù)域可以不存儲任何信息，也可以存儲如線性表的長度等類的附加信息；頭結(jié)點指針域存儲指向第一個結(jié)點的指針(即第一個元素的存儲位置)。若 L 為“空”(L = NULL)，則所表示的線性表為“空”表，其長度為“零”。循環(huán)鏈表的特點：只要知道表中任何一個結(jié)點的地址，就能查詢到表中的任何一個結(jié)點。循環(huán)鏈表。如果這一鏈表中每個結(jié)點只有一個指針域，則稱該鏈表為線性鏈表或單鏈表，否則則稱為雙向鏈表。v 長度可以任意擴充，存儲效率較高；v 物理存儲可以是不連續(xù)的；v 數(shù)據(jù)元素的邏輯次序可以與其存儲的物理次序不一致。v 在鏈式存儲方式中，要求每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域（或稱為信息域）；另一部分用于存放指針，稱為指針域。線性表的順序存
教學教案相關推薦
鄂ICP備17016276號-1