第五章 串
串:串是由零個或多個字符組成的有限序列，又名叫字符串。
串中字符數(shù)目n稱為串的長度。
零個字符的串稱為空串。
串的比較是通過組成串的字符之間的編碼來進(jìn)行的，而字符的編碼指的是字符在對應(yīng)字符集中的序號。
常用的字符編碼有ASCII 和Unicode。
第六章 樹
樹的定義：樹是n(n>=0)結(jié)點的有限集。n=0時稱為空樹。在任意一顆非空樹中：（1）有且只有一個特定的稱為根（Root）的結(jié)點；（2）當(dāng)n>1時，其余結(jié)點可分為m(m＞0)個互不相交的有限集T1，T2...Tn,其中每一個集合本省又是一棵樹，并且稱為根的子樹（SubTree）。
注意：
（1）n>0時，根節(jié)點是唯一的；
（2）子樹的個數(shù)沒有限制，但是子樹一定是互不相交的。下面兩個圖的結(jié)構(gòu)都不是樹。
結(jié)點的分類
結(jié)點擁有的子樹數(shù)稱為節(jié)點的度。度為0的結(jié)點成為葉結(jié)點或終端結(jié)點。度不為0的結(jié)點稱為非終端結(jié)點或分支結(jié)點。除根節(jié)點外，分支結(jié)點也稱為內(nèi)部結(jié)點。樹的度是樹內(nèi)各結(jié)點的度的最大值。
結(jié)點的層次
結(jié)點的層次從根開始定義起，根為第一層，根的孩子為第二層。樹中結(jié)點最大的層次稱為樹的深度或高度。
如果將樹中各結(jié)點的子樹看成從左至右是有次序的，不能互換的，則稱該樹是有序樹，否則稱無序樹。
森林是m(m>0)棵互不相交的樹的集合。
線性表和樹的異同點：
樹的存儲結(jié)構(gòu)
1 雙親表示法
在每個結(jié)點中，附設(shè)一個指示器指示其雙親結(jié)點到鏈表中的位置。
注意雙親域，長子域和左右兄弟域的靈活運用。
2 孩子表示法
把每個結(jié)點的孩子結(jié)點排列起來，以單鏈表作為存儲結(jié)構(gòu)，則n個結(jié)點有n個孩子鏈表，如果是葉子結(jié)點則此單鏈表為空。然后n個頭指針又組成一個線性表，采用順序存儲結(jié)構(gòu)，放進(jìn)一個一維數(shù)組中。
3 孩子兄弟表示法
任意一棵樹，它的結(jié)點的第一個孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我們設(shè)置兩個指針，分別指向該節(jié)點的第一個孩子和此節(jié)點的右兄弟。
二叉樹
定義：二叉樹是n(n>=0)個結(jié)點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根節(jié)點和兩顆互不相交的，分別稱為根節(jié)點的左子樹和右子樹的二叉樹組成。
二叉樹的特點：
1 每個結(jié)點最多有兩顆子樹。
2左子樹和右子樹是有順序的，不能任意顛倒。
3 即使某個結(jié)點只有一顆子樹，也要區(qū)分左右。
根據(jù)以上特點總結(jié)二叉樹的五種基本形態(tài)：
1 空二叉樹。
2只有一個根節(jié)點。
3根節(jié)點之后左子樹。
4 根節(jié)點只有右子樹。
5 根節(jié)點既有左子樹，又有右子樹。
斜樹：所有結(jié)點都只有左子樹的二叉樹叫做左斜樹，都只有右結(jié)點的二叉樹叫做右斜樹。
滿二叉樹：在一顆二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。
完全二叉樹：對一顆具有n個結(jié)點的二叉樹按層序編號，如果編號為i(1<=i<=n)的結(jié)點與同樣深度的滿二叉樹中編號為i的結(jié)點在二叉樹中的位置完全相同，則這棵二叉樹稱為完全二叉樹。
二叉樹的性質(zhì)
1 在二叉樹的第i層上最多有2^(i-1)個結(jié)點 (i>=1)。
2 深度為k的二叉樹最多有2^k -1個結(jié)點(k>=1)。
3 對于任何一顆二叉樹T,如果其葉子結(jié)點數(shù)為n0,度為2的結(jié)點數(shù)為n2,則n0=n2+1。
4 具有n個結(jié)點的完全二叉樹的深度為log2n+1。
二叉樹的存儲結(jié)構(gòu)
順序存儲結(jié)構(gòu)：一般只適用于完全二叉樹，因為其他類型的二叉樹會浪費大量的存儲空間。
二叉鏈表：二叉樹每個結(jié)點最多有兩個孩子，所以為它設(shè)計一個數(shù)據(jù)域和兩個指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。
二叉樹的遍歷：是指從根結(jié)點出發(fā)，按照某種次序依次訪問二叉樹中所有結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次。
二叉樹的遍歷方法
1 前序遍歷
規(guī)則：若二叉樹為空，則空操作返回，否則先訪問根節(jié)點，然后前序遍歷左子樹，再前序遍歷右子樹。
2 中序遍歷
規(guī)則：若二叉樹為空，則空操作返回，否則從根結(jié)點開始（注意并不是先訪問根結(jié)點），中序遍歷根結(jié)點的左子樹，然后是訪問根結(jié)點，最后中序遍歷右子樹。
3 后序遍歷
規(guī)則：若二叉樹為空，則空操作返回，否則從左到右先葉子后結(jié)點的方式遍歷訪問左右子樹，最后訪問根結(jié)點。
4 層序遍歷
規(guī)則：若二叉樹為空，則空操作返回，否則從樹的第一層，也就是根結(jié)點開始訪問，從上而下逐層遍歷，在同一層中，按照從左到右的順序?qū)Y(jié)點逐個訪問。
二叉樹遍歷的性質(zhì)：
1 已知前序和中序遍歷序列可以唯一確定一顆二叉樹。
2 已知后序和中序遍歷序列可以唯一確定一顆二叉樹。
線索二叉樹
定義：每個結(jié)點都有一個指向前驅(qū)和后繼的指針（線索），加上線索的二叉鏈表成為線索鏈表，相應(yīng)的二叉樹就稱為下所二叉樹。
其實線索二叉樹就是把二叉樹變成了一個雙向鏈表。
在實際問題中，如果所用的二叉樹需要經(jīng)常遍歷或查找結(jié)點時需要某種遍歷序列中的前驅(qū)和后繼，那么采用線索二叉樹的結(jié)構(gòu)就是非常不錯的選擇。
赫夫曼樹的應(yīng)用-文檔壓縮技術(shù)。
