【正文】 T。 char ch。 scanf(“%c”,amp。ch)。 if(ch==’’) T=NULL。 else { T=( Bintree )malloc(sizeof(BinTNode))。 Tdata=ch。 Tlchild=createBTpre()。 Trchild=createBTpre()。 } return T。}//后序遍歷銷毀一個樹void BiTree_Free(BiTNode* T){ BiTNode *tmp = NULL。 if (T!= NULL) { if (Trchild != NULL) BiTree_Free(Trchild)。 if (Tlchild != NULL) BiTree_Free(Tlchild)。 if (T != NULL) { free(T)。 T = NULL。 } }}前言普通二叉樹只能找到結點的左右孩子信息，而該結點的直接前驅和直接后繼只能在遍歷過程中獲得。若可將遍歷后對應的有關前驅和后繼預存起來，則從第一個結點開始就能很快“順藤摸瓜”而遍歷整個樹了。二叉線索樹思想是干什么的？中序遍歷這棵樹===》轉換成鏈表訪問2線索化思想結論：線索化過程就是在遍歷過程（假設是中序遍歷）中修改空指針的過程：將空的lchild改為結點的直接前驅；將空的rchild改為結點的直接后繼。3線索化思想訓練請將此樹線索化。1）右空指針線索化：2）左空指針線索化3）總結1）線索化樹結點typedef struct BiThrNode /* 二叉線索存儲結點結構 */{ char data。 /* 結點數(shù)據(jù) */ struct BiThrNode *lchild, *rchild。 /* 左右孩子指針 */ int LTag。 int RTag。 /* 左右標志 */} BiThrNode, *BiThrTree。2）線索化思想分析線索化的本質：讓前后結點，建立關系；1）兩個輔助指針變量形成差值后：后繼結點的左孩子指向前驅結點，前驅結點的右孩子指向后繼結點。2）賦值指針變量和業(yè)務操作的邏輯關系4） 二叉樹線索化樹的遍歷/* 中序遍歷二叉線索樹T(頭結點)的非遞歸算法 */int InOrderTraverse_Thr(BiThrNode* T){ BiThrNode* p。 p = Tlchild。 /* p指向根結點 */ while (p != T) { /* 空樹或遍歷結束時,p==T */ while (pLTag == Link) p = plchild。 printf(%c , pdata)。 while (pRTag==Thread amp。amp。 prchild!=T) { p = prchild。 printf(%c , pdata)。 } p=prchild。 } return 0。}組建一個網(wǎng)絡，耗費最小 WPL最?。贿@個方法是霍夫曼想出來的，稱為霍夫曼樹對于文本”BADCADFEED”的傳輸而言，因為重復出現(xiàn)的只有”ABCDEF”這6個字符，因此可以用下面的方式編碼：接收方可以根據(jù)每3個bit進行一次字符解碼的方式還原文本信息。這樣的編碼方式需要30個bit位才能表示10個字符那么當傳輸一篇500個字符的情報時，需要15000個bit位在戰(zhàn)爭年代，這種編碼方式對于情報的發(fā)送和接受是很低效且容易出錯的。如何提高收發(fā)效率？要提高效率，必然要從編碼方式的改進入手，要避免每個字符都占用相同的bit位準則：任一字符的編碼都不是另一個字符編碼的前綴！也就是說：每一個字符的編碼路徑，都不包含另外一個字符的路徑?；舴蚵鼧鋥 v1, v2, …, vn}F = { T1, T2, …, Tn}Ti的數(shù)據(jù)域為vi，左右子樹為空，這棵二叉樹的根結點中的值為左右子樹根結點中的值之和，并將構造的新二叉樹加入F中，直到F中只剩下一個樹為止。這棵樹即霍夫曼樹假設經(jīng)過統(tǒng)計ABCDEF在需要傳輸?shù)膱笪闹谐霈F(xiàn)的概率如下霍夫曼樹是一種特殊的二叉樹 霍夫曼樹應用于信息編碼和數(shù)據(jù)壓縮領域 霍夫曼樹是現(xiàn)代壓縮算法的基礎 排序 現(xiàn)實生活中排序很重要算法已寫好代碼復用 amp。 和我們需要學習前輩們的經(jīng)驗 不矛盾，也不代表我們不需要不學習。排序是計算機內經(jīng)常進行的一種操作，其目的是將一組“無序”的數(shù)據(jù)元素調整為“有序”的數(shù)據(jù)元素。排序數(shù)學定義：假設含n個數(shù)據(jù)元素的序列為{ R1, R2, …, Rn}其相應的關鍵字序列為{ K1, K2, …, Kn}這些關鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關系 ：Kp1≤Kp2≤…≤Kpn按此固有關系將上式記錄序列重新排列為{ Rp1, Rp2, …，Rpn}的操作稱作排序 排序的穩(wěn)定性如果在序列中有兩個數(shù)據(jù)元素r[i]和r[j]，它們的關鍵字k[i] == k [j]，且在排序之前，對象r[i]排在r[j]前面。如果在排序之后，對象r[i]仍在r[j]前面，則稱這個排序方法是穩(wěn)定的；否則稱這個排序方法是不穩(wěn)定的。多關鍵字排序排序時需要比較的關鍵字多余一個排序結果首先按關鍵字1進行排序當關鍵字1相同時按關鍵字2進行排序當關鍵字n1相同時按關鍵字n進行排序對于多關鍵字排序，只需要在比較操作時同時考慮多個關鍵字即可！排序中的關鍵操作比較任意兩個數(shù)據(jù)元素通過比較操作確定先后次序交換數(shù)據(jù)元素之間需要交換才能得到預期結果內排序和外排序內排序整個排序過程不需要訪問外存便能完成 外排序待排序的數(shù)據(jù)元素數(shù)量很大，整個序列的排序過程不可能在內存中完成排序的審判時間性能關鍵性能差異體現(xiàn)在比較和交換的數(shù)量 輔助存儲空間為完成排序操作需要的額外的存儲空間 必要時可以“空間換時間”算法的實現(xiàn)復雜性過于復雜的排序法會影響代碼的可讀性和可維護性，也可能影響排序的性能總結排序是數(shù)據(jù)元素從無序到有序的過程排序具有穩(wěn)定性，是選擇排序算法的因素之一比較和交換是排序的基本操作多關鍵字排序與單關鍵字排序無本質區(qū)別排序的時間性能是區(qū)分排序算法好壞的主要因素基本思想每一趟 (例如第 i 趟，i = 0, 1, …,n2)在后面 ni個待排的數(shù)據(jù)元素中選出關鍵字最小的元素, 作為有序元素序列的第 i 個元素。排序過程 首先通過n1次關鍵字比較，從n個記錄中找出關鍵字最小的記錄，將它與第一個記錄交換 再通過n2次比較，從剩余的n1個記錄中找出關鍵字次小的記錄，將它與第二個記錄交換 重復上述操作，共進行n1趟排序后，排序結束基本思想：元素1個元素，排序過程：整個排序過程為n1趟插入，即先將序列中第1個記錄看成是一個有序子序列，然后從第2個記錄開始，逐個進行插入，直至整個序列有序實質：對線性表執(zhí)行n1次插入操作，只是先要找到插入位置V[0], V[1], …, V[i1]已經(jīng)排好序。這時已經(jīng)排好序。這時,用V[i]的關鍵字與V[i1], V[i2], …的關鍵字進行比較, 找到插入位置即將V[i]]插入, 原來位置上的對象向后順移。插入排序關鍵點：拿出一個元素，留出位置、2 符合條件的元素后移排序過程：先取一個正整數(shù)d1n，把所有相隔d1的記錄放一組，組內進行直接插入排序；然后取d2d1，重復上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止O()Q(nlogn) 希爾排序是不穩(wěn)定的。思想：快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序將要排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，基準數(shù)據(jù)排在這兩個子序列的中間；然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。// O(n*logn)不穩(wěn)定，分組，后面的有可能跑到前面去了。21 100 3 50 1 3 1 21 100 50 1 3 21 50 100思想：注意：一個元素，可以看做有序的，是穩(wěn)定的算法對一個數(shù)組分成兩路，mid中間 設兩個有序的子文件(相當于輸入堆)放在同一向量中相鄰的位置上：R[low..m],R[m+1..high],先將它們合并到一個局部的暫存向量R1(相當于輸出堆)中,待合并完成后將R1復制回R[low..high]中。 6 C++模板類與數(shù)據(jù)結構基礎 C++模板是容器的概念。理論提高：所有容器提供的都是值（value）語意，而非引用（reference）語意。容器執(zhí)行插入元素的操作時，內部實施拷貝動作。所以STL容器內存儲的元素必須能夠被拷貝（必須提供拷貝構造函數(shù)）。 加入到容器中的元素，應該可以被加入才行。鏈表類_鏈式存儲設計與實現(xiàn) 棧類_鏈式存儲設計與實現(xiàn) 隊列類_鏈式存儲設計與實現(xiàn) 鏈表類_順序存儲設計與實現(xiàn) 棧類_順序存儲設計與實現(xiàn) 隊列類_順序存儲設計與實現(xiàn)