下面是范文網(wǎng)小編收集的年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》各章復(fù)習(xí)要點(diǎn)總結(jié)3篇 數(shù)據(jù)結(jié)構(gòu)第一章知識(shí)點(diǎn)總結(jié)，以供借鑒。
年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》各章復(fù)習(xí)要點(diǎn)總結(jié)1
2010年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》各章復(fù)習(xí)要點(diǎn)總結(jié)(3)龍耒為你整理：
第五章 多維數(shù)組和廣義表
數(shù)組一般用順序存儲(chǔ)的方式表示。存儲(chǔ)的方式有：
·行優(yōu)先順序，也就是把數(shù)組逐行依次排列。PASCAL、C
·列優(yōu)先順序，就是把數(shù)組逐列依次排列。FORTRAN
地址的計(jì)算方法：
·按行優(yōu)先順序排列的數(shù)組：LOCa(ij)=LOCa(11)+((i-1)*n+(j-1))*d.·按列優(yōu)先順序排列的數(shù)組：LOCa(ij)=LOCa(11)+((j-1)*n+(i-1))*d.矩陣的壓縮存儲(chǔ)：為多個(gè)相同的非零元素分配一個(gè)存儲(chǔ)空間;對(duì)零元素不分配空間。
特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。
稀疏矩陣的概念：一個(gè)矩陣中若其非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個(gè)數(shù)，則該矩陣稱為稀疏矩陣。
特殊矩陣的類型：
·對(duì)稱矩陣：滿足a(ij)=a(ji)。元素總數(shù)n(n+1)/=max(i，j)，J=min(i，j)，LOCa(ij)=LOC(sa[0])+(I*(I+1)/2+J)*d.·三角矩陣：
·上三角陣：k=i*(2n-i+1)/2+j-i，LOCa(ij)=LOC(sa[0])+k*d.·下三角陣：k=i*(i+1)/2+j，LOCa(ij)=LOC(sa[0])+k*d.·對(duì)角矩陣：k=2i+j，LOCa(ij)=LOC(sa[0])+k*d.稀疏矩陣的壓縮存儲(chǔ)方式用三元組表把非零元素的值和它所在的行號(hào)列號(hào)做為一個(gè)結(jié)點(diǎn)存放在一起，用這些結(jié)點(diǎn)組成的一個(gè)線性表來表示。但這種壓縮存儲(chǔ)方式將失去隨機(jī)存儲(chǔ)功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。
廣義表是n(n≥0)個(gè)元素的有限序列，其中的元素是原子或者是一個(gè)廣義表。
廣義表表頭和表尾的概念：
·若廣義表LS非空(n≥1)，則這個(gè)廣義表的第一個(gè)元素就是表頭。
·其余的元素組成的表稱為L(zhǎng)S的表尾，所以表尾必是一個(gè)子表。
廣義表有兩種表示法，一種是括號(hào)表示法，一種是圖形表示法。
廣義表與樹(形結(jié)構(gòu))相對(duì)應(yīng)，這個(gè)廣義表就是純表。
如果一個(gè)廣義表的結(jié)點(diǎn)又可以被其他結(jié)點(diǎn)所共享，則這個(gè)表稱為再入表。
允許遞歸的表稱為遞歸表。
線性表∈純表(樹)∈再入表∈遞歸表?？梢?，廣義表是對(duì)線性表和樹的推廣。
廣義表有兩個(gè)特殊的基本運(yùn)算：
·取表頭head(LS)：取表中的第一個(gè)數(shù)據(jù)元素，不能對(duì)空表操作。
·取表尾tail(LS);取除表頭外，其余數(shù)據(jù)元素構(gòu)成的子表，不能對(duì)空表操作。
第六章 樹
樹是n個(gè)結(jié)點(diǎn)的有限集合，非空時(shí)必須滿足：只有一個(gè)稱為根的結(jié)點(diǎn);其余結(jié)點(diǎn)形成m個(gè)不相交的子集，并稱根的子樹。
根是開始結(jié)點(diǎn);結(jié)點(diǎn)的子樹數(shù)稱度;度為0的結(jié)點(diǎn)稱葉子(終端結(jié)點(diǎn));度不為0的結(jié)點(diǎn)稱分支結(jié)點(diǎn)(非終端結(jié)點(diǎn));除根外的分支結(jié)點(diǎn)稱內(nèi)部結(jié)點(diǎn);
有序樹是子樹有左，右之分的樹;無序樹是子樹沒有左，右之分的樹;森林是m個(gè)互不相交的樹的集合;
樹的四種不同表示方法：
·樹形表示法;
·嵌套集合表示法;
·凹入表示法;
·廣義表表示法。
二叉樹的定義：是n≥0個(gè)結(jié)點(diǎn)的有限集，它是空集(n=0)或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。
二叉樹不是樹的特殊情形，與度數(shù)為2的有序樹不同。
二叉樹的4個(gè)重要性質(zhì)：
·二叉樹上第i層上的結(jié)點(diǎn)數(shù)目最多為2^(i-1)(i≥1);
·深度為k的二叉樹至多有(2^k)-1個(gè)結(jié)點(diǎn)(k≥1);
·在任意一棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1;
·具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為int(log2n)+1。滿二叉樹是一棵深度為k，結(jié)點(diǎn)數(shù)為(2^k)-1的二叉樹;完全二叉樹是滿二叉樹在最下層自右向左去處部分結(jié)點(diǎn);
二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是把二叉樹的所有結(jié)點(diǎn)按照層次順序存儲(chǔ)到連續(xù)的存儲(chǔ)單元中。(存儲(chǔ)前先將其畫成完全二叉樹)
樹的存儲(chǔ)結(jié)構(gòu)多用的是鏈?zhǔn)酱鎯?chǔ)。BinTNode的結(jié)構(gòu)為lchild|data|rchild，把所有BinTNode類型的結(jié)點(diǎn)，加上一個(gè)指向根結(jié)點(diǎn)的BinTree型頭指針就構(gòu)成了二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個(gè)指針域，n+1個(gè)空指針。
根據(jù)訪問結(jié)點(diǎn)的次序不同可得三種遍歷：先序遍歷(前序遍歷或先根遍歷)，中序遍歷(或中根遍歷)、后序遍歷(或后根遍歷)。時(shí)間復(fù)雜度為O(n)。
利用二叉鏈表中的n+1個(gè)空指針域來存放指向某種遍歷次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針，這些附加的指針就稱為“線索”，加上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡(jiǎn)單有效，但對(duì)于查找指定結(jié)點(diǎn)的前序前趨和后序后繼并沒有什么作用。
樹和森林及二叉樹的轉(zhuǎn)換是唯一對(duì)應(yīng)的。
轉(zhuǎn)換方法：
·樹變二叉樹：兄弟相連，保留長(zhǎng)子的連線。
·二叉樹變樹：結(jié)點(diǎn)的右孩子與其雙親連。
·森林變二叉樹：樹變二叉樹，各個(gè)樹的根相連。
樹的存儲(chǔ)結(jié)構(gòu)：
·有雙親鏈表表示法：結(jié)點(diǎn)data | parent，對(duì)于求指定結(jié)點(diǎn)的雙親或祖先十分方便，但不適于求指定結(jié)點(diǎn)的孩子及后代。
·孩子鏈表表示法：為樹中每個(gè)結(jié)點(diǎn)data | next設(shè)置一個(gè)孩子鏈表firstchild，并將data | firstchild存放在一個(gè)向量中。
·雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結(jié)合。
·孩子兄弟鏈表表示法：結(jié)點(diǎn)結(jié)構(gòu)leftmostchild |data | rightsibing，附加兩個(gè)分別指向該結(jié)點(diǎn)的最左孩子和右鄰兄弟的指針域。樹的前序遍歷與相對(duì)應(yīng)的二叉樹的前序遍歷一致;樹的后序遍歷與相對(duì)應(yīng)的二叉樹的中序遍歷一致。
樹的帶權(quán)路徑長(zhǎng)度是樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。樹的帶權(quán)路徑長(zhǎng)度最小的二叉樹就稱為最優(yōu)二叉樹(即哈夫曼樹)。
在葉子的權(quán)值相同的二叉樹中，完全二叉樹的路徑長(zhǎng)度最短。
哈夫曼樹有n個(gè)葉結(jié)點(diǎn)，共有2n-1個(gè)結(jié)點(diǎn)，沒有度為1的結(jié)點(diǎn)，這類樹又稱為嚴(yán)格二叉樹。
變長(zhǎng)編碼技術(shù)可以使頻度高的字符編碼短，而頻度低的字符編碼長(zhǎng)，但是變長(zhǎng)編碼可能使解碼產(chǎn)生二義性。如00、01、0001這三個(gè)碼無法在解碼時(shí)確定是哪一個(gè)，所以要求在字符編碼時(shí)任一字符的編碼都不是其他字符編碼的前綴，這種碼稱為前綴碼(其實(shí)是非前綴碼)。
哈夫曼樹的應(yīng)用最廣泛地是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼。哈夫曼編碼的構(gòu)造很容易，只要畫好了哈夫曼樹，按分支情況在左路徑上寫代碼0，右路徑上寫代碼1，然后從上到下到葉結(jié)點(diǎn)的相應(yīng)路徑上的代碼的序列就是該結(jié)點(diǎn)的最優(yōu)前綴碼。
年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》各章復(fù)習(xí)要點(diǎn)總結(jié)2
11-12-2數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)指導(dǎo)
第一章：
知識(shí)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)元素關(guān)系的基本結(jié)構(gòu)類型；數(shù)據(jù)元素的不同存儲(chǔ)結(jié)構(gòu)；算法的重要特性；評(píng)價(jià)算法的重要指標(biāo)； 如何由程序代碼估算算法的復(fù)雜度（大O描述）。
第二章：
知識(shí)點(diǎn)：線性表不同的存儲(chǔ)方式及其各自特點(diǎn)；順序表及鏈表的基本操作（插入、刪除等）與其具體代碼實(shí)現(xiàn)。
第三章：
知識(shí)點(diǎn)：棧和隊(duì)列的結(jié)構(gòu)特點(diǎn)；二者基本操作的思想；鏈隊(duì)列和循環(huán)隊(duì)列的基本操作；循環(huán)隊(duì)列如何判空和判滿。
第四章：
知識(shí)點(diǎn)：串的相關(guān)定義與基本操作；模式匹配的定義與思想。
第五章：
知識(shí)點(diǎn)：數(shù)組的定義與順序?qū)崿F(xiàn)方式；數(shù)組順序存儲(chǔ)中元素地址的計(jì)算；稀疏矩陣的壓縮存儲(chǔ)方式與元素地址的特點(diǎn)；廣義表的定義與基本操作（表頭，表尾，判長(zhǎng)度、深度）。
第六章：
知識(shí)點(diǎn)：樹的基本術(shù)語；（滿/完全）二叉樹的定義與各種性質(zhì)特點(diǎn)；二叉樹不同的存儲(chǔ)與遍歷方式；一般樹的存儲(chǔ)結(jié)構(gòu)；樹與森林的遍歷方式；赫夫曼樹與編碼的求法。
第七章：
知識(shí)點(diǎn)：（有向/無向/完全）圖的概念與其特點(diǎn)；（強(qiáng)）聯(lián)通圖的定義與特點(diǎn)；圖的不同存儲(chǔ)結(jié)構(gòu)及其操作；圖的不同方式的遍歷；最小生成樹的定義與其不同的求解方法；拓?fù)渑判虻亩x與思想；關(guān)鍵（最短）路徑的定義與思想。
第九章：
知識(shí)點(diǎn)：順序查找、折半查找的思想及其具體代碼實(shí)現(xiàn)和復(fù)雜度分析；索引查找的思想；二叉排序樹的思想及操作；平衡二叉樹的定義與操作；B-樹的定義與特點(diǎn)；哈希表（函數(shù)）的定義；哈希函數(shù)的構(gòu)造方法與處理沖突的方法。
第十章：
知識(shí)點(diǎn)：各種排序方法的思想與其復(fù)雜度、穩(wěn)定性分析。
注：以上涉及到的復(fù)雜度分析，其推導(dǎo)過程不做要求。
年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》各章復(fù)習(xí)要點(diǎn)總結(jié)3
2010年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》各章復(fù)習(xí)要點(diǎn)總結(jié)(2)2010年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》四至六章復(fù)習(xí)要點(diǎn)總結(jié)。
第四章 串
串是零個(gè)或多個(gè)字符組成的有限序列。
·空串：是指長(zhǎng)度為零的串，也就是串中不包含任何字符(結(jié)點(diǎn))。
·空白串：指串中包含一個(gè)或多個(gè)空格字符的串。
·在一個(gè)串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串就稱為主串。
·子串在主串中的序號(hào)就是指子串在主串中首次出現(xiàn)的位置。
·空串是任意串的子串，任意串是自身的子串。
串分為兩種：
·串常量在程序中只能引用不能改變;
·串變量的值可以改變。
串的基本運(yùn)算有：
·求串長(zhǎng)strlen(char*s)
·串復(fù)制strcpy(char*to，char*from)
·串聯(lián)接strcat(char*to，char*from)
·串比較charcmp(char*s1，char*s2)
·字符定位strchr(char*s，charc)
。串是特殊的線性表(結(jié)點(diǎn)是字符)，所以串的存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類似。串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序串。
順序串又可按存儲(chǔ)分配的不同分為：
·靜態(tài)存儲(chǔ)分配：直接用定長(zhǎng)的字符數(shù)組來定義。優(yōu)點(diǎn)是涉及串長(zhǎng)的操作速度快，但不適合插入、鏈接操作。
·動(dòng)態(tài)存儲(chǔ)分配：是在定義串時(shí)不分配存儲(chǔ)空間，需要使用時(shí)按所需串的長(zhǎng)度分配存儲(chǔ)單元。
串的鏈?zhǔn)酱鎯?chǔ)就是用單鏈表的方式存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。鏈串與單鏈表的差異只是它的結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符。
為了解決“存儲(chǔ)密度”低的狀況，可以讓一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符，即結(jié)點(diǎn)的大小。
順序串上子串定位的運(yùn)算：又稱串的“模式匹配”或“串匹配”，是在主串中查找出子串出現(xiàn)的位置。在串匹配中，將主串稱為目標(biāo)(串)，子串稱為模式(串)。這是比較容易理解的，串匹配問題就是找出給定模式串P在給定目標(biāo)串T中首次出現(xiàn)的有效位移或者是全部有效位移。最壞的情況下時(shí)間復(fù)雜度是O((n-m+1)m)，假如m與n同階的話則它是O(n^2)。鏈串上的子串定位運(yùn)算位移是結(jié)點(diǎn)地址而不是整數(shù)。
第五章 多維數(shù)組和廣義表
數(shù)組一般用順序存儲(chǔ)的方式表示。存儲(chǔ)的方式有：
·行優(yōu)先順序，也就是把數(shù)組逐行依次排列。PASCAL、C
·列優(yōu)先順序，就是把數(shù)組逐列依次排列。FORTRAN
地址的計(jì)算方法：
·按行優(yōu)先順序排列的數(shù)組：LOCa(ij)=LOCa(11)+((i-1)*n+(j-1))*d.·按列優(yōu)先順序排列的數(shù)組：LOCa(ij)=LOCa(11)+((j-1)*n+(i-1))*d.矩陣的壓縮存儲(chǔ)：為多個(gè)相同的非零元素分配一個(gè)存儲(chǔ)空間;對(duì)零元素不分配空間。
特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。
稀疏矩陣的概念：一個(gè)矩陣中若其非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個(gè)數(shù)，則該矩陣稱為稀疏矩陣。
特殊矩陣的類型：
·對(duì)稱矩陣：滿足a(ij)=a(ji)。元素總數(shù)n(n+1)/=max(i，j)，J=min(i，j)，LOCa(ij)=LOC(sa[0])+(I*(I+1)/2+J)*d.·三角矩陣：
·上三角陣：k=i*(2n-i+1)/2+j-i，LOCa(ij)=LOC(sa[0])+k*d.·下三角陣：k=i*(i+1)/2+j，LOCa(ij)=LOC(sa[0])+k*d.·對(duì)角矩陣：k=2i+j，LOCa(ij)=LOC(sa[0])+k*d.稀疏矩陣的壓縮存儲(chǔ)方式用三元組表把非零元素的值和它所在的行號(hào)列號(hào)做為一個(gè)結(jié)點(diǎn)存放在一起，用這些結(jié)點(diǎn)組成的一個(gè)線性表來表示。但這種壓縮存儲(chǔ)方式將失去隨機(jī)存儲(chǔ)功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。
廣義表是n(n≥0)個(gè)元素的有限序列，其中的元素是原子或者是一個(gè)廣義表。
廣義表表頭和表尾的概念：
·若廣義表LS非空(n≥1)，則這個(gè)廣義表的第一個(gè)元素就是表頭。
·其余的元素組成的表稱為L(zhǎng)S的表尾，所以表尾必是一個(gè)子表。
廣義表有兩種表示法，一種是括號(hào)表示法，一種是圖形表示法。
廣義表與樹(形結(jié)構(gòu))相對(duì)應(yīng)，這個(gè)廣義表就是純表。
如果一個(gè)廣義表的結(jié)點(diǎn)又可以被其他結(jié)點(diǎn)所共享，則這個(gè)表稱為再入表。
允許遞歸的表稱為遞歸表。
線性表∈純表(樹)∈再入表∈遞歸表?？梢?，廣義表是對(duì)線性表和樹的推廣。
廣義表有兩個(gè)特殊的基本運(yùn)算：
·取表頭head(LS)：取表中的第一個(gè)數(shù)據(jù)元素，不能對(duì)空表操作。
·取表尾tail(LS);取除表頭外，其余數(shù)據(jù)元素構(gòu)成的子表，不能對(duì)空表操作。
第六章 樹
樹是n個(gè)結(jié)點(diǎn)的有限集合，非空時(shí)必須滿足：只有一個(gè)稱為根的結(jié)點(diǎn);其余結(jié)點(diǎn)形成m個(gè)不相交的子集，并稱根的子樹。
根是開始結(jié)點(diǎn);結(jié)點(diǎn)的子樹數(shù)稱度;度為0的結(jié)點(diǎn)稱葉子(終端結(jié)點(diǎn));度不為0的結(jié)點(diǎn)稱分支結(jié)點(diǎn)(非終端結(jié)點(diǎn));除根外的分支結(jié)點(diǎn)稱內(nèi)部結(jié)點(diǎn);
有序樹是子樹有左，右之分的樹;無序樹是子樹沒有左，右之分的樹;森林是m個(gè)互不相交的樹的集合;
樹的四種不同表示方法：
·樹形表示法;
·嵌套集合表示法;
·凹入表示法;
·廣義表表示法。
二叉樹的定義：是n≥0個(gè)結(jié)點(diǎn)的有限集，它是空集(n=0)或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。
二叉樹不是樹的特殊情形，與度數(shù)為2的有序樹不同。
二叉樹的4個(gè)重要性質(zhì)：
·二叉樹上第i層上的結(jié)點(diǎn)數(shù)目最多為2^(i-1)(i≥1);
·深度為k的二叉樹至多有(2^k)-1個(gè)結(jié)點(diǎn)(k≥1);
·在任意一棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1;
·具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為int(log2n)+1。滿二叉樹是一棵深度為k，結(jié)點(diǎn)數(shù)為(2^k)-1的二叉樹;完全二叉樹是滿二叉樹在最下層自右向左去處部分結(jié)點(diǎn);
二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是把二叉樹的所有結(jié)點(diǎn)按照層次順序存儲(chǔ)到連續(xù)的存儲(chǔ)單元中。(存儲(chǔ)前先將其畫成完全二叉樹)
樹的存儲(chǔ)結(jié)構(gòu)多用的是鏈?zhǔn)酱鎯?chǔ)。BinTNode的結(jié)構(gòu)為lchild|data|rchild，把所有BinTNode類型的結(jié)點(diǎn)，加上一個(gè)指向根結(jié)點(diǎn)的BinTree型頭指針就構(gòu)成了二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個(gè)指針域，n+1個(gè)空指針。
根據(jù)訪問結(jié)點(diǎn)的次序不同可得三種遍歷：先序遍歷(前序遍歷或先根遍歷)，中序遍歷(或中根遍歷)、后序遍歷(或后根遍歷)。時(shí)間復(fù)雜度為O(n)。
利用二叉鏈表中的n+1個(gè)空指針域來存放指向某種遍歷次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針，這些附加的指針就稱為“線索”，加上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡(jiǎn)單有效，但對(duì)于查找指定結(jié)點(diǎn)的前序前趨和后序后繼并沒有什么作用。
樹和森林及二叉樹的轉(zhuǎn)換是唯一對(duì)應(yīng)的。
轉(zhuǎn)換方法：
·樹變二叉樹：兄弟相連，保留長(zhǎng)子的連線。
·二叉樹變樹：結(jié)點(diǎn)的右孩子與其雙親連。
·森林變二叉樹：樹變二叉樹，各個(gè)樹的根相連。
樹的存儲(chǔ)結(jié)構(gòu)：
·有雙親鏈表表示法：結(jié)點(diǎn)data | parent，對(duì)于求指定結(jié)點(diǎn)的雙親或祖先十分方便，但不適于求指定結(jié)點(diǎn)的孩子及后代。
·孩子鏈表表示法：為樹中每個(gè)結(jié)點(diǎn)data | next設(shè)置一個(gè)孩子鏈表firstchild，并將data | firstchild存放在一個(gè)向量中。
·雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結(jié)合。
·孩子兄弟鏈表表示法：結(jié)點(diǎn)結(jié)構(gòu)leftmostchild |data | rightsibing，附加兩個(gè)分別指向該結(jié)點(diǎn)的最左孩子和右鄰兄弟的指針域。樹的前序遍歷與相對(duì)應(yīng)的二叉樹的前序遍歷一致;樹的后序遍歷與相對(duì)應(yīng)的二叉樹的中序遍歷一致。
樹的帶權(quán)路徑長(zhǎng)度是樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。樹的帶權(quán)路徑長(zhǎng)度最小的二叉樹就稱為最優(yōu)二叉樹(即哈夫曼樹)。
在葉子的權(quán)值相同的二叉樹中，完全二叉樹的路徑長(zhǎng)度最短。
哈夫曼樹有n個(gè)葉結(jié)點(diǎn)，共有2n-1個(gè)結(jié)點(diǎn)，沒有度為1的結(jié)點(diǎn)，這類樹又稱為嚴(yán)格二叉樹。
變長(zhǎng)編碼技術(shù)可以使頻度高的字符編碼短，而頻度低的字符編碼長(zhǎng)，但是變長(zhǎng)編碼可能使解碼產(chǎn)生二義性。如00、01、0001這三個(gè)碼無法在解碼時(shí)確定是哪一個(gè)，所以要求在字符編碼時(shí)任一字符的編碼都不是其他字符編碼的前綴，這種碼稱為前綴碼(其實(shí)是非前綴碼)。
哈夫曼樹的應(yīng)用最廣泛地是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼。哈夫曼編碼的構(gòu)造很容易，只要畫好了哈夫曼樹，按分支情況在左路徑上寫代碼0，右路徑上寫代碼1，然后從上到下到葉結(jié)點(diǎn)的相應(yīng)路徑上的代碼的序列就是該結(jié)點(diǎn)的最優(yōu)前綴碼。
年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》各章復(fù)習(xí)要點(diǎn)總結(jié)3篇 數(shù)據(jù)結(jié)構(gòu)第一章知識(shí)點(diǎn)總結(jié)相關(guān)文章：