【正文】 一棵倒置的樹表示樹結(jié)構(gòu),非常直觀和形象（2）文氏圖表示法。結(jié)點的層次從樹根開始定義,根結(jié)點為第1層,它的孩子結(jié)點為第2層,以此類推,一個結(jié)點所在的層次為其雙親結(jié)點所在的層次加1。注意,下面的先根遍歷和后根遍歷算法都是遞歸的。i/2 （DLR）先序遍歷二叉樹的過程是：(1) 訪問根結(jié)點；(2) 先序遍歷左子樹；(3) 先序遍歷右子樹。(1)創(chuàng)建二叉樹CreateBTNode(*b,*str)：根據(jù)二叉樹括號表示法的字符串*str生成對應的鏈式存儲結(jié)構(gòu)。 DispBiTNode(Trchild)。給定權(quán)值w=(1,3,5,7)來構(gòu)造一棵哈夫曼樹給定一組葉結(jié)點權(quán)值，所構(gòu)造的哈夫曼樹樹的形狀可能不同，但帶權(quán)路徑長度值是相同的，一定是最小的。若不相等,再根據(jù)k與該中間結(jié)點關(guān)鍵字的比較大小確定下一步查找哪個子表,這樣遞歸進行下去,直到找到滿足條件的結(jié)點或者該線性表中沒有這樣的結(jié)點。設有一個包含n個記錄{R(1), R(2), …, R(n)}的源文件。依次類推，一直到所有記錄都有序為止。 i++) {k=i1。具體步驟是：(1) 在未排序的文件中找出關(guān)鍵字值最小的記錄，然后把這個記錄與第一個位置上的記錄對換，使得關(guān)鍵字值最小的記錄定位；(2) 在余下的記錄中找出關(guān)鍵字值最小的記錄，并把它與第二個位置上的記錄進行對調(diào)，使關(guān)鍵字值次小的記錄在已排序的序列中定位；(3) 依次類推，一直到所有的記錄逐個在排序的序列中定位簡單選擇排序算法Bibblesort(R){ Int a[n]。} } a[j+1] = temp。該方法是提取關(guān)鍵字中取值較均勻的數(shù)字位作為哈希地址的方法。 }以有序表表示靜態(tài)查找表時，Search函數(shù)可用折半查找來實現(xiàn)。Lk其中Wk為第k個葉結(jié)點的權(quán)值，Lk為第k個葉結(jié)點的路徑長度。voidDispBiTNode(BiTree T){ if (T != NULL) { printf(%c, Tdata)。 /*遞歸調(diào)用的結(jié)束條件*/PostOrder(btlchild)。/*左右孩子指針域*/}BiTNode, *BiTree。或235。②樹中所有結(jié)點可以有零個或多個后繼結(jié)點。4. 孩子結(jié)點、雙親結(jié)點和兄弟結(jié)點：在一棵樹中,每個結(jié)點的后繼,被稱作該結(jié)點的孩子結(jié)點(或子女結(jié)點)。因此，可以采用單鏈表方式來存儲串值，串的這種鏈式存儲結(jié)構(gòu)簡稱為鏈串。DELQUEUE(queue，r，f，out)/* 在queue隊列中退出一個元素到out，f和r分別是隊首和隊尾的標志 */{ if(f==r)　{ printf(隊空)。 structLsnode *next。 sprior=p。 初始化單鏈表void InitList(LinkList *list)。(2) 確定性:無二義性。：(1) 數(shù)據(jù)元素之間的邏輯關(guān)系,即數(shù)據(jù)的邏輯結(jié)構(gòu)。算法中基本運算次數(shù)T(n)是問題規(guī)模n的某個函數(shù)f(n),記作：T(n)=O(f(n))(2) 空間復雜度：實現(xiàn)算法所需的存儲單元多少第二章線性表線性表是具有相同特性的數(shù)據(jù)元素的一個有限序列。 根據(jù)鍵值查找指定元素intFindElemByNum(LinkList *list, char *keyCh, ElemType *pElem)。循環(huán)鏈表是另一種形式的鏈式存儲結(jié)構(gòu)。2．入棧操作鏈棧入棧操作的含義是：將一個元素推入指定的鏈棧中。（2）StrAssign（s，ch）：串賦值。使用集合以及集合的包含關(guān)系描述樹結(jié)構(gòu)。樹中結(jié)點的最大層次稱為樹的高度(或樹的深度)。1. 先根遍歷先根遍歷過程為： (1)訪問根結(jié)點； (2)按照從左到右的次序先根遍歷根結(jié)點的每一棵子樹。；若2i≤n，則有編號為2i的左孩子，否則沒有左孩子；若2i+1≤n，則有編號為2i+1的右孩子，否則沒有右孩子。voidPreOrder(BiTreebt) { if (bt==NULL) return。** Initiate(bt)：建立一棵空的二叉樹bt，并返回bt。 printf())。編碼方法在哈夫曼編碼樹中，樹的帶權(quán)路徑長度的含義是各個字符的碼長與其出現(xiàn)次數(shù)的乘積之和，也就是電文的代碼總長，所以采用哈夫曼樹構(gòu)造的編碼是一種能使電文代碼總長最短的不等長編碼。其算法如下(在有序表R[0..n1]中進行二分查找,成功時返回記錄的位置,失敗時返回1)：? intBinSearch(SeqListR,intn,KeyType k)? {? int low=0,high=n1,mid。假設有一個子文件，它是由源文件的第一個記錄R(1)構(gòu)成的，顯然，這個只有一個記錄的源文件是有序的。一般情況下，記錄數(shù)為n，需要做n－1次冒泡。min=a[k]。} }}3..簡單選擇排序過程冒泡算法中每次通過若干次交換把待排序序列中最小的數(shù)據(jù)放在已排序序列的最后，簡單選擇排序主要是減少排序過程中的交換次數(shù)，只是簡單的記錄下當前待排序序列中最小數(shù)據(jù)的位置，最后通過1次交換來完成當次排序。}else{Break。除留余數(shù)法的哈希函數(shù)h(k)為：h(k)=k mod p (mod為求余運算,p≤m) p最好取小于m的質(zhì)數(shù)(素數(shù))。elsereturn i。記為： WPL＝Wk /*定義根結(jié)點指針變量*/ t =Initiate()。voidPostOrder(BiTreebt) { if (bt==NULL) return。*rchild。log2n+1249。：①樹的根結(jié)點沒有前驅(qū)結(jié)點，除根結(jié)點之外的所有結(jié)點有且只有一個前驅(qū)結(jié)點。3. 路徑與路徑長度：如果一棵樹中的一串結(jié)點n1,n2,…,nk,有如下關(guān)系：結(jié)點ni是ni+1的父結(jié)點(1≤ik) ,就把n1,n2,…,nk稱為一條由n1至nk的路徑，這條路徑的長度是k1。（1）串賦值StrAssign(t，chars)（2）串聯(lián)接StrConcat(t，s1，s2)（3）求子串SubString(t, s, pos, len)（4）插入函數(shù)StrInsert(s, pos, t)（5）刪除函數(shù)StrDelete (s, pos, t)順序串上的