【文章內(nèi)容簡(jiǎn)介】 n,n1 , ann } Loc( aij ) = Loc(a11) + 2 * (i1) + (j1) 三對(duì)角陣 三、稀疏矩陣（矩陣的壓縮存儲(chǔ)） 矩陣在科學(xué)運(yùn)算中十分廣泛 ， 且隨計(jì)算機(jī)應(yīng)用的發(fā)展 ， 出現(xiàn)了大量的高介矩陣 ， 這些矩陣中的絕大部分元素往往為零值 。 定義：非零元較零元少 ， 且分布沒(méi)有一定規(guī)律的矩陣 。 壓縮存儲(chǔ)原則：只存矩陣的行列維數(shù)和每個(gè)非零元的行列下標(biāo)及其值 。 順序存儲(chǔ)結(jié)構(gòu)三元組稀疏矩陣的轉(zhuǎn)置運(yùn)算 3 0 0 0 7 0 0 1 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 2 0 M= 3 0 1 0 0 0 0 2 0 0 0 1 0 0 0 0 0 0 0 2 7 0 0 0 0 M= 行 列 值 2 4 5 2 2 3 1 1 3 1 3 2 7 5 1 3 1 1 行 列 值 7 1 5 2 5 4 1 2 3 2 3 2 1 3 1 3 1 1 2）帶輔助向量的三元組表示 為了便于通過(guò)三元組法訪問(wèn)稀疏矩陣中的元素，通常附設(shè)兩個(gè)向量 POS和 NUM，稱為 行輔助向量 。它們滿足： POS（ 1） = 1 POS（ i） = POS（ i1） + NUM（ i1）， 2=i=m 其中， POS（ i）表示稀疏矩陣中第 i行的第一個(gè)非零元素在三元組中的行號(hào)； NUM（ i）表示稀疏矩陣中第 i行的非零元素的個(gè)數(shù)。 3 0 0 0 7 0 0 1 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 2 0 M= i 1 2 3 4 5 POS 1 3 4 6 6 NUM 2 1 2 0 1 3）偽地址表示法 偽地址表示法是通過(guò)本元素在矩陣中（含 0元素）按行優(yōu)先順序的相對(duì)位置。 在上例中， M中非 0元素的偽地址為： { 1， 5， 8， 11， 12， 24 } 偽地址表中每個(gè)節(jié)點(diǎn)含兩個(gè)字段： 一個(gè)是偽地址，另一個(gè)是元素值。 偽地址 值 1 3 5 7 8 1 11 1 12 2 24 2 該方法節(jié)省空間，但是在運(yùn)算過(guò)程中要計(jì)算偽地址，浪費(fèi)時(shí)間。 1）帶行指針向量的單鏈表 設(shè)置一個(gè)行指針向量，向量中每個(gè)元素為一個(gè)指針，指向本行矩陣的第一個(gè)非 0元素節(jié)點(diǎn)，若本行無(wú)非 0元素，則指針為空。矩陣中每一個(gè)非 0元素由三個(gè)數(shù)據(jù)域，列、元素值以及指向本行下一個(gè)非 0 結(jié)點(diǎn)的指針，同一行的非 0元素構(gòu)成一個(gè)單鏈表。 ^ 3 1 ^ 1 3 1 1 ^ 2 4 ^ 2 2 ^ 7 5 3 0 0 0 7 0 0 1 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 2 0 M= 定義：樹(shù)是由 n個(gè)（ n=0）結(jié)點(diǎn)組成的有限集合 T。其中有且僅有一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)（ root） A,其余結(jié)點(diǎn)可分為 m（ m=0） 個(gè)互不相交的有限集合 T T … 、 Tm，其中的每一個(gè)集合 Ti本身又是一棵樹(shù)，稱為根結(jié)點(diǎn) root的子樹(shù)。 n=0時(shí)，樹(shù)為空樹(shù)。 特點(diǎn)：樹(shù)中至少有一個(gè)結(jié)點(diǎn)，根；樹(shù)中各子樹(shù)是互不相交的集合。 B E L K T1 F D H I T3 J M C G T2 一、樹(shù)的定義 B E L K T1 F D H I T3 J M C G T2 一、樹(shù)的定義 A 結(jié)點(diǎn) （ Node） ：樹(shù)中的元素 ， 含數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的指針； 結(jié)點(diǎn)的度 （ Degree） ：結(jié)點(diǎn)擁有的子樹(shù)數(shù) 。 樹(shù)中最大結(jié)點(diǎn)的度數(shù)稱為樹(shù)的度數(shù)； 結(jié)點(diǎn)的層次（ Level） ：從根結(jié)點(diǎn)開(kāi)始算起，根為第一層； 葉子 （ Leaf） ：度為零的結(jié)點(diǎn) ， 也稱端結(jié)點(diǎn)； 孩子 （ Child） ：結(jié)點(diǎn)子樹(shù)的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)； 兄弟 （ Sibling） ： 同一雙親的孩子； 雙親 （ Parent） ：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)； 深度 （ Depth)： 樹(shù)中結(jié)點(diǎn)的最大層次數(shù) 。 森林 （ Forest） ： M棵互不相交的樹(shù)的集合 。 有序樹(shù) ：樹(shù)中結(jié)點(diǎn)在同層中按從左到右有序排列 、 不能互換的稱為有序樹(shù) ， 反之 ， 稱為 無(wú)序樹(shù) 。 樹(shù)的常用術(shù)語(yǔ) B E L K T1 F D H T3 M C G T2 A I J 一棵 n個(gè)結(jié)點(diǎn)的k叉樹(shù)，有 nk個(gè)指針域，有用的指針域?yàn)?n1個(gè)，空鏈域?yàn)閚k（ n1） 個(gè)。 樹(shù)的存儲(chǔ) 1） 結(jié)點(diǎn)異構(gòu)型 ：根據(jù)每個(gè)結(jié)點(diǎn)的子樹(shù)數(shù)設(shè)置相應(yīng)的指針域，由于樹(shù)中每個(gè)結(jié)點(diǎn)的度不盡相同，同一棵樹(shù)中各結(jié)點(diǎn)的結(jié)構(gòu)形式也不同。節(jié)約空間，運(yùn)算不便。 2） 結(jié)點(diǎn)同構(gòu)型 ：每個(gè)結(jié)點(diǎn)的指針域數(shù)目均為樹(shù)的度數(shù)。運(yùn)算方便，浪費(fèi)空間。 比較不同的 k值： 2/1211)1(23/23121)1(311)1(l i m?????????????????nnnkknknnnkknknkknk二、二叉樹(shù) （ Binary Tree） 二叉樹(shù)的五種基本形態(tài)： 僅有根結(jié)點(diǎn) 右子樹(shù)為空 左子樹(shù)為空 左右子樹(shù)均非空 定義：二叉樹(shù)是 n(n?0)個(gè)結(jié)點(diǎn)的有限集 ， 它或?yàn)榭諛?shù)(n=0)， 或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)構(gòu)成 。 特點(diǎn)： 1） 每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù) (即不存在度大于 2的結(jié)點(diǎn) )； 2） 二叉樹(shù)的子樹(shù)有左 、 右之分 ， 且其次序不能任意顛倒 。 空二叉樹(shù) 1） 二叉樹(shù)的第 i層上至多有 2i1（ i ? 1） 個(gè)結(jié)點(diǎn)； 2） 深度為 h 的二叉樹(shù)中至多含有 2h – 1 個(gè)結(jié)點(diǎn)； 3） 若在任意一棵二叉樹(shù)中 ， 有 n0 個(gè)葉子結(jié)點(diǎn) ， 有 n2 個(gè)度為 2 的結(jié)點(diǎn) ， 則： n0 = n2 + 1。 A B C D E F 二叉樹(shù)的基本性質(zhì) 2） 完全二叉樹(shù) 特點(diǎn)：指深度為 k的 ， 有 n個(gè)結(jié)點(diǎn)的 ， 且每一個(gè)結(jié)點(diǎn)都與深度為 k的滿二叉樹(shù)中編號(hào)從 1至 n的結(jié)點(diǎn)一一對(duì)應(yīng) ， 完全一致 ， 則為完全二叉樹(shù) 。 1）滿二叉樹(shù) 特點(diǎn)：深度為 h且含有 2h1個(gè)結(jié)點(diǎn)的二叉樹(shù) ， 為滿二叉樹(shù) 。 圖示滿二叉樹(shù) ， 結(jié)點(diǎn)編號(hào)為自上而下， 自左而右 。 4 2 3 1 5 6 7 8 9 10 11 12 13 14 15 4 2 3 1 5 6 7 8 9 10 11 12 12 特殊形式的二叉樹(shù) 3）平衡二叉樹(shù) 特點(diǎn)：又稱 AVL樹(shù) ， 它或?yàn)橐豢每諛?shù) ， 或具如下性質(zhì)：其左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù) ， 且左、 右子樹(shù)的深度之差的絕對(duì)值不超過(guò) 1。 左 、 右子樹(shù)的深度之差為平衡因子 ， 平衡二叉樹(shù)的平衡因子只能為 0， 1， 1。 由于二叉樹(shù)常常用二叉鏈表表示，為了使一般樹(shù)也能用二叉鏈表表示，必須找出樹(shù)與二叉樹(shù)之間的關(guān)系。為此，給定一棵樹(shù)，可以找到唯一的一棵二叉樹(shù)與之對(duì)應(yīng)。 1）普通樹(shù)轉(zhuǎn)換為二叉樹(shù)的方法： 對(duì)每個(gè)孩子進(jìn)行自左至右的排序； 在兄弟之間加一條連線； 對(duì)每個(gè)結(jié)點(diǎn)，除了左孩子外，去除其與其余孩子之間的聯(lián)系； 以根結(jié)點(diǎn)為軸心，將整個(gè)樹(shù)順時(shí)針轉(zhuǎn) 45度。 一般樹(shù)轉(zhuǎn)換為二叉樹(shù) A B C D E G H F I 1）樹(shù)轉(zhuǎn)換為二叉樹(shù) A B C D E G H F I A B C D E G H F I A B C D E G H F I T[16] 若父結(jié)點(diǎn)在數(shù)組中 i下標(biāo)處，其左孩子在 2*i處，右孩子在 2*i+1處。 11 A B C F E D ● ● ● ● ● ● ● ● ● 1 2 4 8 9 10 5 6 3 7 12 13 14 15 2h1= 241 = 15 1) 順序存儲(chǔ)結(jié)構(gòu) 用一組連續(xù)的存儲(chǔ)單元存放二叉樹(shù)的數(shù)據(jù)元素 。 結(jié)點(diǎn)在數(shù)組中的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系 。 0 0 0 0 F E 0 0 0 D C 0 B A 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) （順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)） 遍歷定義 遍歷是指按某條搜索路線依次尋訪樹(shù)中每個(gè)結(jié)點(diǎn) ， 每個(gè)結(jié)點(diǎn)被訪問(wèn)且只被訪問(wèn)一次 。 對(duì)二叉樹(shù)的遍歷 ， 總共有六種方式；按先左后右的原則 ， 一般使用三種遍歷： 先序遍歷 (D L R): 訪問(wèn)根結(jié)點(diǎn)，按先序遍歷左子樹(shù)，按先序遍歷右子樹(shù)。 中序遍歷 (L D R): 按中序遍歷左子樹(shù)，訪問(wèn)根結(jié)點(diǎn)，按中序遍歷右子樹(shù)。 后序遍歷 (L R D): 按后序遍歷左子樹(shù)，按后序遍歷右子樹(shù)，訪問(wèn)根結(jié)點(diǎn)。 二叉樹(shù)為空時(shí) ， 執(zhí)行空操作 ， 即空二叉樹(shù)已遍歷完 。 三、二叉樹(shù)的遍歷（ traversing） 先序遍歷： D L R 中序遍歷： L D R 后序遍歷： L R D D L R A D L R D L R B D C D L R ABDC BDAC DBCA 2 遍歷算法 void Pre (struct TreeNode *T) { if (T ! = NULL) { printf (Tdata)。 Pre (Tlchild)。 Pre (Trchild)。 } } /*先序遍歷 */ A D B C T1 T2 T3 3）由遍歷序列恢復(fù)二叉樹(shù) DLR是先訪問(wèn)根結(jié)點(diǎn) ， 再按 DLR方式遍歷根結(jié)點(diǎn)的 左子樹(shù) ， 后按 DLR方式遍歷根結(jié)點(diǎn)的右子樹(shù) 。 即：在 DLR序列中 ， 第一個(gè)結(jié)點(diǎn)一定是二叉樹(shù)的根結(jié)點(diǎn)； LDR是先用 LDR方式 遍歷左子樹(shù) ， 再訪問(wèn)根結(jié)點(diǎn) ， 后用 LDR方式 遍歷右子樹(shù) 。 因此 ， 根結(jié)點(diǎn)在 LDR序列中必將之分割成兩個(gè)子序列 ， 前一個(gè)子序列是根結(jié)點(diǎn)的左子樹(shù)的中序序列 ， 而后一個(gè)子序列是根結(jié)點(diǎn)的右子樹(shù)的 LDR序列 。 據(jù)這兩個(gè)子序列 ， 可在 DLR序列中找到對(duì)應(yīng)的左子序列和右子序列 。 在 DLR序列中 ， 左子序列的第一個(gè)結(jié)點(diǎn)是左子樹(shù)的根結(jié)點(diǎn) ，右子序列的第一個(gè)結(jié)點(diǎn)是右子樹(shù)的根結(jié)點(diǎn) 。 上述過(guò)程 ， 就可以確定二叉樹(shù)的三個(gè)結(jié)點(diǎn) 。 同時(shí) ， 左子樹(shù)和右子樹(shù)的根結(jié)點(diǎn)又可以分別把左子序列和右子序列劃分成兩個(gè)子序列 ， 如此遞歸 ， 便可得到一棵二叉樹(shù) 。 同理，若已知結(jié)點(diǎn)的 后序 、 中序序列，就可以唯一地確定一棵二叉樹(shù)。 已知： DLR A B C D E F G H I LDR B C A E D G H F I 3）由遍歷序列恢復(fù)二叉樹(shù) 同理，若已知結(jié)點(diǎn)的 后序 、 中序序列，就可以唯一地確定一棵二叉樹(shù)。 已知： DLR A B C D E F G H I LDR B C A E D G H F I 哈夫曼樹(shù) （ Huffman) 最優(yōu)樹(shù)： 是帶權(quán)的路徑長(zhǎng)度最短的樹(shù)，常用于信息檢索； 路徑長(zhǎng)度： 從一個(gè)結(jié)點(diǎn)到另一結(jié)點(diǎn)之間經(jīng)過(guò)的分支數(shù)目稱為這對(duì)結(jié)點(diǎn)間的路徑長(zhǎng)度； 樹(shù)的路徑長(zhǎng)度： 從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和，用 PL表示； 結(jié)點(diǎn)帶權(quán)的路徑長(zhǎng)度： 為從該結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。 樹(shù)的帶權(quán)路徑長(zhǎng)度： 為樹(shù)中葉子結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度之和。 記作： 其中： Wk為樹(shù)中每個(gè)葉子結(jié)點(diǎn)的權(quán)； L