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