自學(xué)數(shù)據(jù)結(jié)構(gòu)大綱筆記

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)概述（教材選用嚴(yán)蔚敏、吳偉民，該書(shū)程序是偽算法具體的程序是高一凡，西電的，大牛，只有程序。還有一本書(shū)，臺(tái)灣的黃國(guó)瑜自己寫(xiě)的只有思路，程序是另外一個(gè)合作的清華的寫(xiě)的，可惜很多錯(cuò)的。）學(xué)完數(shù)據(jù)結(jié)構(gòu)之后會(huì)對(duì)面向過(guò)程的函數(shù)有一個(gè)更深的了解 定義 我們?nèi)绾伟熏F(xiàn)實(shí)中大量而復(fù)雜的問(wèn)題以特定的數(shù)據(jù)類(lèi)型（單 個(gè)數(shù)據(jù)怎樣存儲(chǔ)？）和特定的存儲(chǔ)結(jié)構(gòu)（個(gè)體的關(guān)系） 保存到主存儲(chǔ)器（內(nèi)存）中，以及在此基礎(chǔ)上為實(shí)現(xiàn)某個(gè)功能 （比如查找某個(gè)元素，刪除某個(gè)元素，對(duì)所有元素進(jìn)行排序） 而執(zhí)行的相應(yīng)操作，這個(gè)相應(yīng)的操作也叫算法。（比如班里有 15個(gè)人，其信息量也許一個(gè)數(shù)組就搞定了，但是假如1000

2、0個(gè)， 怎么辦？?jī)?nèi)存也許沒(méi)有這么多連續(xù)的空間，所以我們改用鏈表， you see這就是與存儲(chǔ)有關(guān)系。又比如，人事管理系統(tǒng)的信息存儲(chǔ)， 因?yàn)榇嬖谥舷录?jí)的關(guān)系，所以數(shù)組和鏈表就無(wú)能為力了， 這時(shí)候我們用樹(shù)，再比如我們做的是交通圖，站和站之間肯定要連通，這 時(shí)候以上的存儲(chǔ)方式又無(wú)能為力了，所以我們又有了圖。圖 就是每個(gè)結(jié)點(diǎn)都可以和其他結(jié)點(diǎn)產(chǎn)生聯(lián)系。所以當(dāng)我們要解決 問(wèn)題時(shí)，首先要解決的是如何把這些問(wèn)題轉(zhuǎn)換成數(shù)據(jù)，先保存 到我們的主存中，） 數(shù)據(jù)結(jié)構(gòu) = 個(gè)體的存儲(chǔ) + 個(gè)體的關(guān)系的存儲(chǔ) 算法 = 對(duì)存儲(chǔ)數(shù)據(jù)的操作 算法 解題的方法和步驟 衡量算法的標(biāo)準(zhǔn) 1、時(shí)間復(fù)雜度 大概程序要執(zhí)行的次數(shù)，而非執(zhí)

3、行的時(shí)間。 2、空間復(fù)雜度 算法執(zhí)行過(guò)程中大概所占用的最大內(nèi)存 3、難易程度（主要是應(yīng)用方面看重） 4、健壯性（不能別人給一個(gè)非法的輸入就掛掉） 數(shù)據(jù)結(jié)構(gòu)的地位 數(shù)據(jù)結(jié)構(gòu)是軟件中最核心的課程 程序 = 數(shù)據(jù)的存儲(chǔ)數(shù)據(jù)的操作可以被計(jì)算機(jī)執(zhí)行的語(yǔ)言（已經(jīng)提供） （學(xué)完數(shù)據(jù)結(jié)構(gòu)，想用一種語(yǔ)言去實(shí)現(xiàn)它，必須有指針，數(shù)據(jù)結(jié)構(gòu)java版，就胡扯，變味，因?yàn)槲覀円v鏈表，就是通過(guò)指針鏈在一起的。比如在java中A aa = new A();本質(zhì)上，aa是個(gè)地址） 預(yù)備知識(shí) 指針 指針的重要性：（內(nèi)存是可以被CPU直接訪問(wèn)的，硬盤(pán)不行 主要靠地址總線，數(shù)據(jù)總線，控制總線。） 指針是C語(yǔ)言的靈魂 定義 地址 地

4、址就是內(nèi)存單元的編號(hào) 從0開(kāi)始的非負(fù)整數(shù) 范圍：0-FFFFFFFF0-4G-1（地址線是32位，剛好控制2的32次） 指針： 指針就是地址 地址就是指針 指針變量是存放內(nèi)存單元地址的變量 指針的本質(zhì)是一個(gè)操作受限的非負(fù)整數(shù)（不能加乘除，只能減） 分類(lèi)： 1、基本類(lèi)型的指針 2、指針和數(shù)組的關(guān)系 結(jié)構(gòu)體（C+中用類(lèi)也能實(shí)現(xiàn)） 為什么會(huì)出現(xiàn)結(jié)構(gòu)體 為了表示一些復(fù)雜的數(shù)據(jù)，而普通的基本類(lèi)型變量無(wú)法滿足要求 什么叫結(jié)構(gòu)體 結(jié)構(gòu)體是用戶(hù)根據(jù)實(shí)際需要自己定義的復(fù)合數(shù)據(jù)類(lèi)型 如何使用結(jié)構(gòu)體 兩種方式： struct Student st = 1000, "zhangsan", 20 s

5、truct Student * pst = &st; 1. st.sid 2. pst->sid pst所指向的結(jié)構(gòu)體變量中的sid這個(gè)成員 注意事項(xiàng)： 結(jié)構(gòu)體變量不能加減乘除，但可以相互賦值 普通結(jié)構(gòu)體變量和結(jié)構(gòu)體指針變量作為函數(shù)參數(shù)的傳遞 （病毒就是靠訪問(wèn)正在運(yùn)行的那些程序所占用的內(nèi)存。Java中規(guī)定局部 變量必須初始化，因?yàn)檫@些變量一開(kāi)始都是垃圾值，但是屬性不是必須 初始化的，因?yàn)橐呀?jīng)默認(rèn)初始化為0） 動(dòng)態(tài)內(nèi)存分配和釋放（動(dòng)態(tài)分配的內(nèi)存一定要手動(dòng)釋放，否則造成內(nèi)存 泄露。）（java中A aa = new A();其實(shí)就是 A *p = (A *)malloc(sizeof

6、(A)）模塊一：線性結(jié)構(gòu)【把所有的結(jié)點(diǎn)用一根直線穿起來(lái)】連續(xù)存儲(chǔ)【數(shù)組】1、什么叫做數(shù)組元素類(lèi)型相同，大小相等（數(shù)組傳參，只要傳進(jìn)去首地址和長(zhǎng)度就行）2、數(shù)組的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：存取速度快缺點(diǎn)：事先必須知道數(shù)組的長(zhǎng)度插入刪除元素很慢空間通常是有限制的需要大塊連續(xù)的內(nèi)存塊插入刪除元素的效率很低 離散存儲(chǔ)【鏈表】（我們搞底層的開(kāi)發(fā)，類(lèi)似于SUN公司的類(lèi)） 定義： n個(gè)節(jié)點(diǎn)離散分配 彼此通過(guò)指針相連 每個(gè)節(jié)點(diǎn)只有一個(gè)前驅(qū)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)只有一個(gè)后續(xù)節(jié)點(diǎn) 首節(jié)點(diǎn)沒(méi)有前驅(qū)節(jié)點(diǎn)，尾節(jié)點(diǎn)沒(méi)有后續(xù)節(jié)點(diǎn)。 專(zhuān)業(yè)術(shù)語(yǔ)： 首節(jié)點(diǎn)： 第一個(gè)有效節(jié)點(diǎn)（有效節(jié)點(diǎn)就是存放有效數(shù)據(jù)的節(jié)點(diǎn)） 尾節(jié)點(diǎn)： 最后一個(gè)有效節(jié)點(diǎn) 頭節(jié)點(diǎn)： 頭

7、結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型和首節(jié)點(diǎn)的類(lèi)型一樣 沒(méi)有存放有效數(shù)據(jù)，放在最前面的，是在 首節(jié)點(diǎn)之前的，主要是為了方便對(duì)鏈表 的操作。 頭指針：（指向頭） 指向頭節(jié)點(diǎn)的指針變量 尾指針： 指向尾節(jié)點(diǎn)的指針 （頭結(jié)點(diǎn)有可能很大，占的內(nèi)存可能大，假設(shè)我想造一個(gè)函數(shù)輸出所有鏈表的值，那你如果不用頭指針類(lèi)型做形參，那由于不同鏈表的頭節(jié)點(diǎn)不一樣大小，這樣就沒(méi)辦法找出形參）在學(xué)數(shù)據(jù)結(jié)構(gòu)之前，我們確定數(shù)組的信息就是數(shù)組的長(zhǎng)度和數(shù)組名，那么學(xué)完數(shù)據(jù)結(jié)構(gòu)后就有三個(gè)了，長(zhǎng)度，有效個(gè)數(shù)，數(shù)組名 確定一個(gè)鏈表需要幾個(gè)參數(shù)：（或者說(shuō)如果期望一個(gè)函數(shù)對(duì)鏈表進(jìn)行操作 我們至少需要接收鏈表的那些信息？） 只需要一個(gè)參數(shù):頭指針，因?yàn)橥ㄟ^(guò)它我們

8、可以推出 鏈表的所有信息。（鏈表的程序最好一定要自己敲出來(lái)） 分類(lèi)： 單鏈表每個(gè)節(jié)點(diǎn)的指針域只能指向下一個(gè)節(jié)點(diǎn) 雙鏈表： 每一個(gè)節(jié)點(diǎn)有兩個(gè)指針域 循環(huán)鏈表 能通過(guò)任何一個(gè)節(jié)點(diǎn)找到其他所有的節(jié)點(diǎn) 非循環(huán)鏈表 （java中變成垃圾內(nèi)存則會(huì)自動(dòng)釋放，但是C和C+則不會(huì)，所以要手動(dòng)釋放，否則會(huì)引起內(nèi)存泄露。delete等于free） 算法： 遍歷 查找 清空 銷(xiāo)毀 求長(zhǎng)度 排序 刪除節(jié)點(diǎn) 插入節(jié)點(diǎn)算法：狹義的算法是與數(shù)據(jù)的存儲(chǔ)方式密切相關(guān) 廣義的算法是與數(shù)據(jù)的存儲(chǔ)方式無(wú)關(guān) 泛型：（給你一種假象，只不過(guò)牛人從內(nèi)部都弄好了） 利用某種技術(shù)（比如C+里面函數(shù)重載）達(dá)到的效果就是：不同的存儲(chǔ)方式，執(zhí)行的操作是

9、一樣的算法的真正學(xué)法：很多算法你根本解決不了！因?yàn)楹芏喽紝儆跀?shù)學(xué)上的東西，所以我們把答案找出來(lái)，如果能看懂就行，但是大部分人又看不懂，分三步，按照流程，語(yǔ)句，試數(shù)。這個(gè)過(guò)程肯定會(huì)不斷地出錯(cuò)，所以不斷出錯(cuò)，不斷改錯(cuò)，這樣反復(fù)敲很多次，才能有個(gè)提高。實(shí)在看不懂就先背會(huì)。 鏈表的優(yōu)缺點(diǎn)： 優(yōu)點(diǎn)： 空間沒(méi)有限制 插入刪除元素很快 缺點(diǎn)： 存取速度很慢。# include <stdio.h># include <malloc.h>void f(int k)int i;double * q = (double *)malloc(200);int main(void)int i =

10、10;int * p = (int *)malloc(100);return 0;/f函數(shù)和main函數(shù)里面的i,q,p都是棧里面分配的，由操作系統(tǒng)分配的棧和堆表示的是一種分配數(shù)據(jù)的方式，靜態(tài)的和局部變量是以壓棧和出棧的方式分配內(nèi)存的/malloc(200),malloc(100)是在堆里面分配的，由程序員自己手動(dòng)分配的，動(dòng)態(tài)的是以一種堆排序的方式分配內(nèi)存的 線性結(jié)構(gòu)的兩種常見(jiàn)應(yīng)用之一 棧 (存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)) 定義 一種可以實(shí)現(xiàn)“先進(jìn)后出” 的存儲(chǔ)結(jié)構(gòu) 棧類(lèi)似于箱子 分類(lèi) 靜態(tài)棧 （類(lèi)似于用數(shù)組實(shí)現(xiàn)） 動(dòng)態(tài)棧 （類(lèi)似于用鏈表實(shí)現(xiàn)） 算法（往里放，從里取） 出棧 壓棧（參看Java中線程的例子，

11、成產(chǎn)消費(fèi)的例子）用棧來(lái)實(shí)現(xiàn)的 棧取出（消費(fèi)）生產(chǎn) 左邊生成東西，右邊往出?。ㄏM(fèi)）生產(chǎn)和取出必須要平衡，不平衡的話生產(chǎn)就會(huì)滿了，或者取出的是空的，取空了就是不能再取了，再取就是垃圾數(shù)據(jù)了生產(chǎn)往底部一直往上放，取出就從頂部一直往下取 應(yīng)用 函數(shù)調(diào)用（壓棧和出棧是現(xiàn)實(shí)的） 中斷 表達(dá)式求值（用兩個(gè)棧，一個(gè)存放數(shù)字，一個(gè)存放符號(hào)） 內(nèi)存分配 緩沖處理 迷宮 線性結(jié)構(gòu)的兩種常見(jiàn)應(yīng)用之二 隊(duì)列 定義： 一種可是實(shí)現(xiàn)“先進(jìn)先出”的存儲(chǔ)結(jié)構(gòu) 分類(lèi)： 鏈?zhǔn)疥?duì)列：用鏈表實(shí)現(xiàn) 靜態(tài)隊(duì)列：用數(shù)組實(shí)現(xiàn) 靜態(tài)對(duì)流通常都必須是循環(huán)隊(duì)列，為了減少 內(nèi)存浪費(fèi)。 循環(huán)隊(duì)列的講解： 1、 靜態(tài)隊(duì)列為什么必須是循環(huán)隊(duì)列 2、循環(huán)隊(duì)

12、列需要幾個(gè)參數(shù)來(lái)確定 及其含義 需要2個(gè)參數(shù)來(lái)確定 front rear 3、 循環(huán)隊(duì)列各個(gè)參數(shù)的含義 2個(gè)參數(shù)不同場(chǎng)合不同的含義? 建議初學(xué)者先記住，然后慢慢體會(huì) 1）隊(duì)列初始化 front和rear的值都是零 2）隊(duì)列非空 front代表隊(duì)列的第一個(gè)元素 rear代表了最后一個(gè)有效元素的下一個(gè)元素 3）隊(duì)列空 front和rear的值相等，但是不一定是零 4、循環(huán)隊(duì)列入隊(duì)偽算法講解 兩步完成： 1）將值存入r所代表的位置 2）將r后移，正確寫(xiě)法是 rear = (rear+1)%數(shù)組長(zhǎng)度 錯(cuò)誤寫(xiě)法：rear=rear+1; 5、 循環(huán)隊(duì)列出隊(duì)偽算法講解 front = (front+1)

13、% 數(shù)組長(zhǎng)度 6、 如何判斷循環(huán)隊(duì)列是否為空 如果front與rear的值相等， 則隊(duì)列一定為空 7、 如何判斷循環(huán)隊(duì)列是否已滿 預(yù)備知識(shí)： front的值和rear的值沒(méi)有規(guī)律， 即可以大，小，等。 兩種方式： 1、多增加一個(gè)表標(biāo)識(shí)的參數(shù) 2、少用一個(gè)隊(duì)列中的元素（才一個(gè)，不影響的） 通常使用第二種方法 如果r和f的值緊挨著，則隊(duì)列已滿 用C語(yǔ)言偽算法表示就是： if( (r+1)%數(shù)組長(zhǎng)度 = f ) 已滿 else 不滿 隊(duì)列算法： 入隊(duì) 出隊(duì) 隊(duì)列的具體應(yīng)用： 所有和時(shí)間有關(guān)的操作都有隊(duì)列的影子。 （例如操作系統(tǒng)認(rèn)為先進(jìn)來(lái)的先處理） 專(zhuān)題：遞歸【這對(duì)你的編碼能力是個(gè)質(zhì)的飛躍，如果你想成

14、為一個(gè)很厲害的 程序員，數(shù)據(jù)結(jié)構(gòu)是必須要掌握的，因?yàn)橛?jì)算機(jī)專(zhuān)業(yè)的本科生也達(dá)不到這水 平！計(jì)算機(jī)特別適合用遞歸的思想來(lái)解決問(wèn)題，但是我們?nèi)祟?lèi)用遞歸的思想 來(lái)考慮問(wèn)題就會(huì)感到十分困擾，這也是很多學(xué)過(guò)遞歸的人一直都搞不明白的 地方！那是不是遞歸可以隨便寫(xiě)，當(dāng)然不是，有些同學(xué)一用遞歸程序就死翹 翹了。遞歸的思想是軟件思想的基本思想之一，在樹(shù)和圖論上面，幾乎全是 用遞歸來(lái)實(shí)現(xiàn)的，最簡(jiǎn)單，像求階乘這種沒(méi)有明確執(zhí)行次數(shù)的問(wèn)題，都是用 遞歸來(lái)解決】 定義： 一個(gè)函數(shù)自己直接或間接調(diào)用自己(一個(gè)函數(shù)調(diào)用另外 一個(gè)函數(shù)和他調(diào)用自己是一模一樣的，都是那三步， 只不過(guò)在人看來(lái)有點(diǎn)詭異。)遞歸用棧實(shí)現(xiàn) 遞歸滿足的三個(gè)條

15、件： 1、遞歸必須得有一個(gè)明確的終止條件 2、該函數(shù)處理的數(shù)據(jù)規(guī)模必須在遞減 3、這個(gè)轉(zhuǎn)化必須是可解的。遞歸的調(diào)用1、 當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行被調(diào)用函數(shù)之前，系統(tǒng)需要完成三件事：A 將所有的實(shí)際參數(shù)，返回地址等信息傳遞給被調(diào)函數(shù)保存B 為被調(diào)函數(shù)的局部變量（也包括形參）分配存儲(chǔ)空間C 將控制轉(zhuǎn)移到被調(diào)函數(shù)的入口2、 從被調(diào)函數(shù)返回主調(diào)函數(shù)之前，系統(tǒng)也要完成三件事：A 保存被調(diào)函數(shù)的返回結(jié)果B 釋放被調(diào)函數(shù)所占的存儲(chǔ)空間C 依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)3、 當(dāng)有多個(gè)函數(shù)相互調(diào)用時(shí)，按照“后調(diào)用先返回”的原則，上述函數(shù)之間信息傳遞和控制轉(zhuǎn)移必須借助“棧”來(lái)

16、實(shí)現(xiàn)，即系統(tǒng)將整個(gè)程序運(yùn)行時(shí)所需的數(shù)據(jù)空間安排在一個(gè)棧中，每當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，就在棧頂分配一個(gè)存儲(chǔ)區(qū)，進(jìn)行壓棧操作，每當(dāng)一個(gè)函數(shù)退出時(shí)，就釋放它的存儲(chǔ)區(qū)，就進(jìn)行出棧操作，當(dāng)前運(yùn)行的函數(shù)永遠(yuǎn)都在棧頂位置A函數(shù)調(diào)用A函數(shù)和A函數(shù)調(diào)用B函數(shù)在計(jì)算機(jī)看來(lái)是沒(méi)有任何區(qū)別的，只不過(guò)用我們?nèi)粘５乃季S方式理解比較怪異而已！ 循環(huán)和遞歸： 理論上循環(huán)能解決的，肯定可以轉(zhuǎn)化為遞歸，但是這個(gè) 過(guò)程是復(fù)雜的數(shù)學(xué)轉(zhuǎn)化過(guò)程，遞歸能解決不一定能轉(zhuǎn)化 為循環(huán)，我們初學(xué)者只要把經(jīng)典的遞歸算法看懂就行， 至于有沒(méi)有能力運(yùn)用看個(gè)人。 遞歸： 易于理解(學(xué)完漢諾塔，樹(shù)，圖后就會(huì)發(fā)現(xiàn)遞歸很容易理解) 速度慢 存儲(chǔ)空間大 循環(huán) 不易于理

17、解 速度快 存儲(chǔ)空間小 舉例： 1.求階乘2.1+2+3+4+。+100的和3.漢諾塔【漢諾塔】這不是線性遞歸，這是非線性遞歸！n=1 1n=2 3n=3 7.n=64 2的64次方減1【這是個(gè)天文數(shù)字，就算世界上最快的計(jì)算機(jī)也解決不了，漢諾塔的負(fù)責(zé)度是2的n次方減1】問(wèn)題很復(fù)雜，但真正解決問(wèn)題的編碼只有三句。4.走迷宮(CS的實(shí)現(xiàn))遞歸的運(yùn)用：樹(shù)和森林就是以遞歸的方式定義的樹(shù)和圖的很多算法都是以遞歸來(lái)實(shí)現(xiàn)的很多數(shù)學(xué)公式就是以遞歸的方式定義的斐波拉契序列1 2 3 5 8 13 21 34。用遞歸思想寫(xiě)出代碼為何數(shù)據(jù)結(jié)構(gòu)難學(xué)：因?yàn)橛?jì)算機(jī)內(nèi)存是線性一維的，而我們要處理的數(shù)據(jù)都是比較復(fù)雜的，那么怎

18、么把這么多復(fù)雜的數(shù)據(jù)保存在計(jì)算機(jī)中來(lái)保存本身就是一個(gè)難題，而計(jì)算機(jī)在保存線性結(jié)構(gòu)的時(shí)候比較好理解，尤其是數(shù)組和鏈表只不過(guò)是連續(xù)和離散的問(wèn)題，線性結(jié)構(gòu)是我們學(xué)習(xí)的重點(diǎn)，因?yàn)榫€性算法比較成熟，無(wú)論C+還是Java中都有相關(guān)的工具例如Arraylist.Linkedlist,但是在Java中沒(méi)有樹(shù)和圖，因?yàn)榉蔷€性結(jié)構(gòu)太復(fù)雜了，他的操作遠(yuǎn)遠(yuǎn)大于線性結(jié)構(gòu)的操作。即使SUN公司也沒(méi)造出來(lái)。小復(fù)習(xí)一下：_邏輯結(jié)構(gòu)：（就是在你大腦里面能產(chǎn)生的，不考慮在計(jì)算機(jī)中存儲(chǔ)）線性（用一根直線穿）在計(jì)算機(jī)中存儲(chǔ)用：數(shù)組鏈表?xiàng)：完?duì)列是一種特殊的線性結(jié)構(gòu)，是具體應(yīng)用。（操作受限的線性結(jié)構(gòu)，不受限的應(yīng)該是在任何地方可以增刪改查

19、可以用數(shù)組和鏈表實(shí)現(xiàn)。只要把鏈表學(xué)會(huì)，棧和隊(duì)列都能搞定，數(shù)組稍微復(fù)雜一些。）非線性：樹(shù)圖物理結(jié)構(gòu)：數(shù)組鏈表 模塊二：非線性結(jié)構(gòu)(現(xiàn)在人類(lèi)還沒(méi)有造出一個(gè)容器，能把樹(shù)和圖都裝進(jìn)去的，因?yàn)樗麄兇_實(shí)是太復(fù)雜了)（都要靠鏈表去實(shí)現(xiàn)）樹(shù)樹(shù)定義專(zhuān)業(yè)定義： 1、有且只有一個(gè)稱(chēng)為根的節(jié)點(diǎn) 2、有若干個(gè)互不相交的子樹(shù)，這些子樹(shù)本身也是一棵樹(shù) 通俗定義：1、樹(shù)是由節(jié)點(diǎn)和邊組成2、每個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)但可以有多個(gè)子節(jié)點(diǎn)3、但有一個(gè)節(jié)點(diǎn)例外，該節(jié)點(diǎn)沒(méi)有根節(jié)點(diǎn)，此節(jié)點(diǎn)稱(chēng)為根節(jié)點(diǎn)專(zhuān)業(yè)術(shù)語(yǔ)節(jié)點(diǎn) 父節(jié)點(diǎn) 子節(jié)點(diǎn)子孫 堂兄弟 深度：從根節(jié)點(diǎn)到最底層節(jié)點(diǎn)的層數(shù)稱(chēng)之為深度根節(jié)點(diǎn)是第一層葉子節(jié)點(diǎn)；（葉子就不能劈叉了）沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)

20、非終端節(jié)點(diǎn)：實(shí)際就是非葉子節(jié)點(diǎn)。根節(jié)點(diǎn)既可以是葉子也可以是非葉子節(jié)點(diǎn)度：子節(jié)點(diǎn)的個(gè)數(shù)稱(chēng)為度。（一棵樹(shù)看最大的）樹(shù)分類(lèi)：一般樹(shù)任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的個(gè)數(shù)都不受限制二叉樹(shù)（有序樹(shù)）任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的個(gè)數(shù)最多兩個(gè)，且子節(jié)點(diǎn)的位置不可更改。分類(lèi)：一般二叉樹(shù)滿二叉樹(shù)在不增加樹(shù)的層數(shù)的前提下。無(wú)法再多添加一個(gè)節(jié)點(diǎn)的二叉樹(shù)就是滿二叉樹(shù)。完全二叉樹(shù)如果只是刪除了滿二叉樹(shù)最底層最右邊的連續(xù)若干個(gè)節(jié)點(diǎn)，這樣形成的二叉樹(shù)就是完全二叉樹(shù)。森林n個(gè)互不相交的樹(shù)的集合一般的二叉樹(shù)要以數(shù)組的方式存儲(chǔ)，要先轉(zhuǎn)化成完全二叉樹(shù)，因?yàn)槿绻阒淮嬗行Ч?jié)點(diǎn)（無(wú)論先序，中序，后序），則無(wú)法知道這個(gè)樹(shù)的組成方式是什么樣子的。樹(shù)的存儲(chǔ)（都是轉(zhuǎn)化成二叉樹(shù)來(lái)存儲(chǔ)）二叉樹(shù)的存儲(chǔ)連續(xù)存儲(chǔ)【完全二叉樹(shù)】?jī)?yōu)點(diǎn)：查找某個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)（也包括判斷有咩有）速度很快缺點(diǎn)：耗用內(nèi)存空間過(guò)大鏈?zhǔn)酱鎯?chǔ)一般樹(shù)的存儲(chǔ)雙親表示法求父節(jié)點(diǎn)方便孩子表示法求子節(jié)點(diǎn)方便雙親孩子表示法求父節(jié)點(diǎn)和子節(jié)點(diǎn)都很方便二叉樹(shù)表示法把一個(gè)普通樹(shù)轉(zhuǎn)化成二叉樹(shù)來(lái)存儲(chǔ)具體轉(zhuǎn)換方法：設(shè)法保證任意一個(gè)節(jié)點(diǎn)的左指針域指向它的第一個(gè)孩子有指針域指向它的下一個(gè)兄弟只要能滿足此條件，就可以把