1樓：tudou天堂
#include
typedef char datatype;
typedef struct bintreenode *pbintreenode;
struct bintreenode
; typedef struct bintreenode *btree; //表示二叉樹型別
typedef struct bintreenode *bnode; //表示二叉樹
節點型別
btree createemptytree() //建空二叉樹
else
printf("out of space! \n"); /*建立失敗*/
return (atree);
為二叉樹根節點,a為目標子節點，p目標父節點
else}}
構造t->info=x,t->llink=null
int main()
printf("\n");
return 0;}
2樓：匿名使用者
建立好二叉樹後，後序遍歷該二叉樹，'h'後面的所有節點就是'h'的所有祖先。
在二叉樹中有兩個結點m和n,如果m是n的祖先,可以找到從m到n的路徑的遍歷方式是
3樓：匿名使用者
觀察棧中的序列。遍歷一棵二叉樹時會使用棧，當利用後序遍歷到目標結點n時，棧中的序列就為n結點的全部父結點（棧為一個陣列）。
結點總數n=n0+n1+n2。設b為分支總數，因為除根節點外，其餘結點都有一個分支進入，所以n=b+1。又因為分支是由度為1或2的結點射出，所以b=n1+2n2。
綜上：n=n0+n1+n2=b+1=n1+2n2+1，得出：n0=n2+1。
所以本題，度為2額節點有m個。
葉子節點n0=n2+1=m+1。
4樓：mighty之
大家可能有一個思維慣性就是在visit()時得到的序列為路徑，其實正確的思想應該是觀察棧中的序列。遍歷一棵二叉樹時會使用棧，當利用後序遍歷到目標結點n時，棧中的序列就為n結點的全部父結點（棧為一個陣列）。
可以自己畫一個二叉樹來後序遍歷一遍注意觀察棧中的元素而不是visit()的元素！
5樓：可靠的青春舞曲
四、遍歷二叉樹二叉樹是一種非線性的資料結構，在對它進行操作時，總是需要逐一對每個資料元素實施操作，這樣就存在一個操作順序問題，由此提出了二叉樹的遍歷操作。所謂遍歷二叉樹就是按某種順序訪問二叉樹中的每個結點一次且僅一次的過程。這裡的訪問可以是輸出、比較、更新、檢視元素內容等等各種操作。
二叉樹的遍歷方式分為兩大類：一類按根、左子樹和右子樹三個部分進行訪問；另一類按層次訪問。下面我們將分別進行討論。
1、按根、左子樹和右子樹三部分進行遍歷遍歷二叉樹的順序存在下面6種可能：tlr（根左右）,trl（根右左）ltr（左根右）,rtl（右根左）lrt（左右根）,rlt（右左根）其中，trl、rtl和rlt三種順序在左右子樹之間均是先右子樹後左子樹，這與人們先左後右的習慣不同，因此，往往不予採用。餘下的三種順序tlr、ltr和lrt根據根訪問的位置不同分別被稱為先序遍歷、中序遍歷和後序遍歷。
（1）先序遍歷若二叉樹為空，則結束遍歷操作；否則訪問根結點；先序遍歷左子樹；先序遍歷右子樹。（2）中序遍歷若二叉樹為空，則結束遍歷操作；否則中序遍歷左子樹；訪問根結點；中序遍歷右子樹。（3）後序遍歷若二叉樹為空，則結束遍歷操作；否則後序遍歷左子樹；後序遍歷右子樹；訪問根結點。
例如。以下是一棵二叉樹及其經過三種遍歷所得到的相應遍歷序列二叉樹的兩種遍歷方法：（1）對一棵二叉樹中序遍歷時，若我們將二叉樹嚴格地按左子樹的所有結點位於根結點的左側，右子樹的所有結點位於根右側的形式繪製，就可以對每個結點做一條垂線，對映到下面的水平線上，由此得到的順序就是該二叉樹的中序遍歷序列（2）任何一棵二叉樹都可以將它的外部輪廓用一條線繪製出來，我們將它稱為二叉樹的包線，這條包線對於理解二叉樹的遍歷過程很有用。
由此可以看出：（1）遍歷操作實際上是將非線性結構線性化的過程，其結果為線性序列，並根據採用的遍歷順序分別稱為先序序列、中序序列或後序序列；（2）遍歷操作是一個遞迴的過程，因此，這三種遍歷操作的演算法可以用遞迴函式實現。（1）先序遍歷遞迴演算法voidpreorder(btreebt)（2）中序遍歷遞迴演算法voidinorder(btreebt)}（3）後序遍歷遞迴演算法voidpostorder(btreebt)}2、按層次遍歷二叉樹實現方法為從上層到下層，每層中從左側到右側依次訪問每個結點。
下面我們將給出一棵二叉樹及其按層次順序訪問其中每個結點的遍歷序列。voidleveloreder(qbtreebt)}
五、典型二叉樹的操作演算法1、輸入一個二叉樹的先序序列，構造這棵二叉樹為了保證唯一地構造出所希望的二叉樹，在鍵入這棵樹的先序序列時，需要在所有空二叉樹的位置上填補一個特殊的字元，比如，'#'。在演算法中，需要對每個輸入的字元進行判斷，如果對應的字元是'#'，則在相應的位置上構造一棵空二叉樹；否則，建立一個新結點。整個演算法結構以先序遍歷遞迴演算法為基礎，二叉樹中結點之間的指標連線是通過指標引數在遞迴呼叫返回時完成。
演算法：btreepre_create_bt()}2、計算一棵二叉樹的葉子結點數目這個操作可以使用三種遍歷順序中的任何一種，只是需要將訪問操作變成判斷該結點是否為葉子結點，如果是葉子結點將累加器加1即可。下面這個演算法是利用中序遍歷實現的。
演算法：voidleaf(btreebt,int*count)}3、交換二叉樹的左右子樹許多操作可以利用三種遍歷順序的任何一種，只是某種遍歷順序實現起來更加方便一些。而有些操作則不然，它只能使用其中的一種或兩種遍歷順序。
將二叉樹中所有結點的左右子樹進行交換這個操作就屬於這類情況。演算法：voidchange_left_right(btreebt)}4、求二叉樹的高度這個操作使用後序遍歷比較符合人們求解二叉樹高度的思維方式。
首先分別求出左右子樹的高度，在此基礎上得出該棵樹的高度，即左右子樹較大的高度值加1。演算法：inthight(btreebt)+1;}}
六、樹、森林與二叉樹的轉換1、樹、森林轉換成二叉樹將一棵樹轉換成二叉樹的方法：將一棵樹轉換成二叉樹實際上就是將這棵樹用孩子兄弟表示法儲存即可，此時，樹中的每個結點最多有兩個指標：一個指標指向第一個孩子，另一個指標指向右側第一個兄弟。
當你將這兩個指標看作是二叉樹中的左孩子指標和孩子右指標時，就是一棵二叉樹了。特點：一棵樹轉換成二叉樹後，根結點沒有右孩子。
將森林轉換成二叉樹的方法與一棵樹轉換成二叉樹的方法類似，只是把森林中所有樹的根結點看作兄弟關係，並對其中的每棵樹依依地進行轉換。2、二叉樹還原成樹或森林這個過程實際上是樹、森林轉換成二叉樹的逆過程，即將該二叉樹看作是樹或森林的孩子兄弟表示法。比如，若二叉樹為空，樹也為空；否則，由二叉樹的根結點開始，延右指標向下走，直到為空，途經的結點個數是相應森林所含樹的棵數；若某個結點的左指標非空，說明這個結點在樹中必有孩子，並且從二叉樹中該結點左指標所指結點開始，延右指標向下走，直到為空，途經的結點個數就是這個結點的孩子數目。
第3節哈夫曼樹及其應用1、哈夫曼樹的定義及特點在二叉樹中，一個結點到另一個結點之間的分支構成這兩個結點之間的路徑。這三棵二叉樹的帶權路徑長度分別為：wpl1=10*2+11*2+3*3+6*3+7*3+9*3=117wpl2=3*1+6*2+7*3+9*4+10*5+11*5=177wpl3=9*1+7*2+6*3+3*4+10*5+11*5=158哈夫曼樹的一個重要特點是：
沒有度為1的結點。2、構造哈夫曼樹的過程：（1）將給定的n個權值作為n個根結點的權值構造一個具有n棵二叉樹的森林，其中每棵二叉樹只有一個根結點；（2）在森林中選取兩棵根結點權值最小的二叉樹作為左右子樹構造一棵新二叉樹，新二叉樹的根結點權值為這兩棵樹根的權值之和；（3）在森林中，將上面選擇的這兩棵根權值最小的二叉樹從森林中刪除，並將剛剛新構造的二叉樹加入到森林中；（4）重複上面（2）和（3），直到森林中只有一棵二叉樹為止。
這棵二叉樹就是哈夫曼樹。例如：假設有一組權值，下面我們將利用這組權值演示構造哈夫曼樹的過程。
它的帶權的路徑長度為：wpl=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2713．判定樹在很多問題的處理過程中，需要進行大量的條件判斷，這些判斷結構的設計直接影響著程式的執行效率。例如，編制一個程式，將百分制轉換成五個等級輸出。
大家可能認為這個程式很簡單，並且很快就可以用下列形式編寫出來：if(socre<60)printf("bad");elseif(socre<70)printf("pass");elseif(score<80)printf("general");elseif(score<90)printf("good");esleprintf("verygood");在實際應用中，往往各個分數段的分佈並不是均勻的。下面就是在一次考試中某門課程的各分數段的分佈情況：
4．字首編碼在電文傳輸中，需要將電文中出現的每個字元進行二進位制編碼。在設計編碼時需要遵守兩個原則：（1）傳送方傳輸的二進位制編碼，到接收方解碼後必須具有唯一性，即解碼結果與傳送方傳送的電文完全一樣；（2）傳送的二進位制編碼儘可能地短。
下面我們介紹兩種編碼的方式。（1）等長編碼這種編碼方式的特點是每個字元的編碼長度相同（編碼長度就是每個編碼所含的二進位制位數）。假設字符集只含有4個字元a，b，c，d，用二進位制兩位表示的編碼分別為00，01，10，11。
若現在有一段電文為：abaccda，則應傳送二進位制序列：00010010101100，總長度為14位。
當接收方接收到這段電文後，將按兩位一段進行譯碼。這種編碼的特點是譯碼簡單且具有唯一性，但編碼長度並不是最短的。（2）不等長編碼在傳送電文時，為了使其二進位制位數儘可能地少，可以將每個字元的編碼設計為不等長的，使用頻度較高的字元分配一個相對比較短的編碼，使用頻度較低的字元分配一個比較長的編碼。
例如，可以為a，b，c，d四個字元分別分配0，00，1，01，並可將上述電文用二進位制序列：000011010傳送，其長度只有9個二進位制位，但隨之帶來了一個問題，接收方接到這段電文後無法進行譯碼，因為無法斷定前面4個0是4個a，1個b、2個a，還是2個b，即譯碼不唯一，因此這種編碼方法不可使用。（1）利用字符集中每個字元的使用頻率作為權值構造一個哈夫曼樹；（2）從根結點開始，為到每個葉子結點路徑上的左分支賦予0，右分支賦予1，並從根到葉子方向形成該葉子結點的編碼。
假設有一個電文字符集中有8個字元，每個字元的使用頻率分別為，現以此為例設計哈夫曼編碼。哈夫曼編碼設計過程為：（1）為方便計算，將所有字元的頻度乘以100，使其轉換成整型數值集合，得到；（2）以此集合中的數值作為葉子結點的權值構造一棵哈夫曼樹，如圖5-27所示；（3）由此哈夫曼樹生成哈夫曼編碼，如圖5-28所示。
最後得出每個字元的編碼為：比如，傳送一段編碼：0000011011010010，接收方可以準確地通過譯碼得到：
⑥⑥⑦⑤②⑧。
某二叉樹共有結點，其中葉子結點只有。則該二叉樹的深度為（根節點在第一層）
二叉樹的深度為12。因為葉子節點為1個，按二叉樹理論得出 任意一棵二叉樹中度為0的節點總是比度為2的節點多一個 故得出此二叉樹度為2的節點為0個。12 總節點 1 度為0 0 度為2 11 度為1 故證明此二叉樹每層只有1個節點，總共12層。一棵深度為k，且有2 k 1個節點的二叉樹，稱為滿二叉樹。...
二叉樹的層次遍歷演算法，二叉樹層次遍歷怎麼進行？
建立一個佇列q 將根放入佇列 while 佇列非空 求用c語言實現二叉樹層次遍歷的遞迴演算法，謝謝！二叉樹層次遍歷怎麼進行？設計一個演算法層序遍歷二叉樹 同一層從左到右訪問 思想 用一個佇列儲存被訪問的當前節點的左右孩子以實現層序遍歷。void hierarchybitree bitree root...
C語言問題某二叉樹共有結點,其中葉子結點只有,則該
因為葉子節點為1個,所以是一個一個接著向下的所以深度為7 二級access有這麼一道題 某二叉樹有7個結點,其中葉子節點只有一個 則該二叉樹的深度為多少?求詳細解答 二叉樹有個性質 葉子節點的個數比度數為2的節點多1.本題中 葉子節點只有一個.說明該二叉樹沒有讀書為2的節點 所以其餘的6個節點全是度...