樹和二叉樹的建立和遍歷-數據結構試驗報告

1、實驗報告一：預習要求預習樹和二叉樹的存儲結構、以遞歸為基本思想的相應遍歷操作。二：實驗目的1、通過實驗，掌握二叉樹的建立與存儲方法。2、掌握二叉樹的結構特性，以及各種存儲結構的特點和適用范圍。3、掌握用指針類型描述、訪問和處理二叉樹的運算。4、理解 huffman 編解碼的算法三：實驗內容以括號表示法輸入一棵二叉樹， 編寫算法建立二叉樹的二叉鏈表結構； 編寫先序、中序、后序、層次遍歷二叉樹的算法；編寫算法計算二叉樹的結點數，葉子結點數，以及二叉樹的深度。四: 實驗原理及試驗方法adt binarytree 數據對象 ：d：d 是具有相同特征的數據元素的集合數據結構 ：r：若 d= 空集，則 r

2、= 空集，稱 binarytree 為空二叉樹；若 d不等于空集，則r=h，h是如下二元關系：（1） 在 d中存在唯一的稱為根的數據元素root ，它在關系 h下無前驅；（2） 若 d-root不等于空集，則存在d-root=d1,dr,且 d1 dr=空集；（3） 若 d1不等于空集，則d1中存在唯一的元素x1， h，且存在 d1上的關系 h1包含于 h；若 dr空集，則 dr 中存在唯一的元素xr, h， 且 存 在dr上 的 關 系hr包 含 于h；h=,h1,hr; （4） (d1,h1)是一顆符合本定義的二叉樹，稱為根的左子樹，（dr,hr ）是一顆符合本定義的二叉樹，稱為根的右子樹

3、?；静僮?p：createbitree(&t,definition); 初始條件： definition給出二叉樹的定義。操作結果：按 definition構造二叉樹 t。preordertraverse(t); 初始條件：二叉樹t 存在。操作結果：先序遍歷t 。inordertraverse(t); 初始條件：二叉樹t 存在。操作結果：中序遍歷t。postordertraverse(t); 初始條件：二叉樹 t 存在。操作結果：后序遍歷t。 guangyi(t); 初始條件：二叉樹 t 存在。操作結果：廣義表遍歷。prethreading(t) 初始條件：二叉樹t 存在。操作結果：

4、二叉樹先序線索化。preorderthreading （thrt,t ）初始條件：二叉樹t 存在。操作結果：先序遍歷二叉樹將二叉樹線索化。preorderthread(t) 初始條件： t存在。操作結果：將先序線索化的二叉樹輸出。inthreading(t) 初始條件： t存在。操作結果：二叉樹中序線索化。inorderthreading （thrt,t ）初始條件： t存在。操作結果：中序遍歷二叉樹將二叉樹線索化。inorderthread （t）初始條件： t存在。操作結果：將中序線索化的二叉樹輸出。postorderthreading （t）初始條件： t存在。操作結果：二叉樹的后序遍歷

5、。postthreading （thrt,t ）初始條件： t存在。操作結果：后序遍歷二叉樹并將其線索化。postorderthread （t）初始條件： t存在。操作結果：將后序線索化的二叉樹輸出。huffmancoding（ht,hc,n）初始條件： ht ，hc存在。操作結果：構造赫夫曼樹ht ，并將赫夫曼譯碼保存在hc 。select(ht,n,s1,s2) 初始條件： ht存在。操作結果：用 s1 和 s2 返回 ht中權值最小的兩個字符。adt binarytree線索二叉樹結構體：#include typedef struct tree /樹的結構體定義char data; /存

6、儲類型int ltag,rtag; /判斷結點是的左、右孩子指針的指向變量，/ ltag=0 表示該結點有左孩子且lchild 指向左孩子， ltag=1 表示該結點的lchild 指向該結點的前驅/rtag=0 表示該結點有右孩子且rchild 指向右孩子， rtag=1 表示該結點的rchild 指向該結點的后繼struct tree *lchild,*rchild; /結點的左、右孩子指針bit,*bit; 構造一個二叉樹：bit createbitree(bit t) /用先序遍歷構建一個二叉樹 char ch; ch=getchar(); /從剛在內存中輸入的字符竄中依次獲得字符if

7、(ch=#) /判斷接受字符是否表示空 t=null; /指針為空 else t=(bit *)malloc(sizeof(bit); /向內存中申請一個結點t-data=ch; /對結點進行字符賦值t-ltag=0; /初始化 ltag 和 rtag,讓他們的初值都為0 t-rtag=0; t-lchild=createbitree(t-lchild); /構建結點的左孩子t-rchild=createbitree(t-rchild); /構建結點的右孩子 return t; /返回結點的地址 二叉樹的先序遍歷：void preordertraverse(bit t) /先序遍歷 if(t)

8、 printf(%c,t-data); /遍歷根結點preordertraverse(t-lchild); /遍歷左孩子preordertraverse(t-rchild);/ 遍歷右孩子 二叉樹的廣義表遍歷：void guangyi(bit t) /廣義表遍歷 if(t) if(t-lchild=null & t-rchild=null) /判斷結點的左右孩子都是否為空 printf(%c,t-data);/ 都為空時，輸出結點字符 else /至少有一個不為空時printf(%c,t-data);/ 輸出結點的字符if(t-lchild)printf(,);guangyi(t-lc

9、hild);/判斷結點的左孩子是否為空，不為空時，遞歸的調用guangyi 函數if(t-rchild)printf(,);guangyi(t-rchild);printf();/判斷結點的右孩子是否為空，不為空時，遞歸的調用guangyi 函數else printf(); /否則輸出） 二叉樹的先序線索化：void prethreading(bit p) /先序線索化 if(p) / 判斷結點是否為空 if(!p-lchild)p-ltag=1;p-lchild=pre; /前驅線索if(!pre-rchild)pre-rtag=1;pre-rchild=p; /后繼線索pre=p; /保持

10、 pre 指向 p 的前驅if(p-ltag=0)prethreading(p-lchild);/ 左子樹線索化if(p-rtag=0)prethreading(p-rchild); /右子樹線索化 bit preorderthreading(bit thrt,bit t)/先序遍歷二叉樹t，并將其線索化， thrt 指向頭結點并返回到主函數中 thrt=(bit)malloc(sizeof(bit);/相內存中申請結點thrt-data=#; /頭指針內容為空thrt-ltag=0;thrt-rtag=1; /建立頭結點thrt-rchild=thrt;/ 右指針回指if(!t)/ 若二叉樹

11、為空，則左指針回指 thrt-lchild=thrt; else thrt-lchild=t; pre=thrt; prethreading(t); /先序遍歷進行先序線索化pre-rchild=thrt;pre-rtag=1;/ 最后一個結點的線索化thrt-rchild=null; return thrt; 先序二叉樹的還原：int returntree(bit t) if(t-ltag=0)returntree(t-lchild);/遍歷左子樹 ,找到 ltag=1 的結點else t-lchild=null; /令左指針指向空if(t-rtag=0)returntree(t-rchil

12、d);/遍歷右子樹，找到rtag=1 的結點else t-rchild=null; /令右指針指向空 7、樹的清空：int cleantree(bit t) / 樹的清空if(t) if(t-lchild)cleantree(t-lchild); if(t-rchild)cleantree(t-rchild); free(t); 赫夫曼樹的結構體：typedef struct / 赫夫曼編碼結構體char ch; /編碼存儲類型unsigned int weight;/ 權值unsigned int parent,lchild,rchild; / 雙親、左孩子、右孩子htnode,*huffm

13、antree; typedef char *huffmancode; /動態(tài)分配數組存儲赫夫曼編碼兩個權值最小字符的尋找：int select(huffmantree ht,int n,int *s1,int *s2) /在赫夫曼樹中選取兩個雙親為零且權值最小的兩個節(jié)點，用s1、s2 返回 int i,j; for(j=1;j=n;+j) if(htj.parent=0) /選取第一個雙親不為零的結點賦值給s1 *s1=j; break; for(i=j+1;i=n;+i) if(hti.weightht*s1.weight&hti.parent=0)/選出權值最小的節(jié)點*s1=i;

14、for(j=1;j=n;+j) /選出雙親為零且不是s1 的結點if(htj.parent=0&*s1!=j) *s2=j; break; for(i=j+1;i=n;+i) if(hti.weightht*s2.weight&hti.parent=0&*s1!=i) /選出權值次小的節(jié)點 *s2=i; if(*s2*s1) /判斷兩個權值的大小是否符合要求，不符合交換 i=*s1; *s1=*s2; *s2=i; 赫夫曼編碼：void huffmancoding(huffmantree ht,huffmancode *hc,int n) /構造赫夫曼樹ht，并求出赫夫

15、曼樹所對應的的赫夫曼編碼 int i,j,f,m,c,start; int s1,s2; char *cd; m=n*2; for(i=1;i=n;i+) /初始構造赫夫曼樹 printf( 請輸入第 %d 個字符和字符對應權值（中間用空格隔開，如：g 29）： ,i); scanf(%s %d,&hti.ch,&hti.weight); hti.parent=0; /雙親和左右孩子均初始化為0；hti.lchild=0; hti.rchild=0; for(;im;i+) /將沒有存放字符的結點權值、雙親和左右孩子均初始化為0 hti.weight=0; hti.lchild

16、=0; hti.rchild=0; hti.parent=0; for(i=n+1;im;i+) select(ht,i-1,&s1,&s2);/ 從結點中選取兩個最小的結點hts1.parent=i;hts2.parent=i; /將新結點的位置的值賦給最小的兩個結點的雙親hti.lchild=s1;hti.rchild=s2; /將最小的兩個結點的位置的值賦給新結點的左右孩子hti.weight=hts1.weight+hts2.weight; /將兩個最小結點的權值相加賦新結點的權值 cd=(char *)malloc(n*sizeof(char); /向內存中申請分配求

17、編碼的存儲空間cdn-1=0;/ 編碼的標示符for(i=1;i=n;i+)/逐個字符求赫夫曼編碼 start=n-1; /編碼結束符位置for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)/從葉子到根逆向求編碼 if(htf.lchild=c)cd-start=0; / 判斷 c 是結點的那個孩子，左孩子添加0，右孩子添加1 else cd-start=1; hci=(char *)malloc(n-start)*sizeof(char);/向內存中申請第i 個字符編碼分配空間strcpy(hci,&cdstart); /從 cd 復制編碼串到hc

18、printf( 字符譯碼 n); for(i=1;i=n;i+) /顯示譯碼 printf(%5c %sn,hti.ch,hci); free(cd);/釋放空間 六、思考題：1. 輸入進行編碼的字符串2. 遍歷字符串，并為葉子節(jié)點權重賦值3. 依次對各字符進行哈弗曼編碼， 自下往上，若是雙親節(jié)點左孩子則編碼前插入0，若是雙親節(jié)點右孩子則編碼錢插入1。4. 顯示各字符的哈弗曼編碼。5. 對字符串進行編碼，挨個遍歷字符，找到相應的編碼，復制到總的編碼里，最后輸出字符串的編碼。6. 對字符串的哈弗曼碼進行譯碼。自上往下，若是0，則遞歸到左孩子，若是1，則遞歸到右孩子，知道葉子節(jié)點，輸出該葉子節(jié)點代

19、表字符，再繼續(xù)遍歷。7. 分析內存占用情況。若用ascii 編碼，每個字符占1 個字節(jié)，即 8bit ，該情況下占用內存就是 （字符長度） *8。若用哈弗曼編碼， 占用內存是各（字符頻度）*（每個字符占用位數）之和。七：參考文獻：1. c語言入門經典（第5 版）作者： ( 美）霍爾頓 (horton,i.)著，楊浩譯，清華大學出版社， 2013年 11 月2. 數據結構（ c 語言版），嚴蔚敏，吳偉民編著，清華大學出版社，2011年 11 月3. 數據結構（ c語言版）（第 2 版），嚴蔚敏，李冬梅，吳偉民編著，人民郵電出版社， 2015年 2 月八：源代碼：1、二叉樹：#include ty

20、pedef struct tree /樹的結構體定義char data; /存儲類型int ltag,rtag; /判斷結點是的左、右孩子指針的指向變量，/ ltag=0表示該結點有左孩子且lchild 指向左孩子， ltag=1 表示該結點的 lchild指向該結點的前驅/rtag=0表示該結點有右孩子且rchild 指向右孩子，rtag=1表示該結點的 rchild指向該結點的后繼struct tree *lchild,*rchild; /結點的左、右孩子指針bit,*bit; bit createbitree(bit t) /用先序遍歷構建一個二叉樹 char ch; ch=getcha

21、r(); /從剛在內存中輸入的字符竄中依次獲得字符if(ch=#) /判斷接受字符是否表示空 t=null; /指針為空 else t=(bit *)malloc(sizeof(bit); /向內存中申請一個結點t-data=ch; /對結點進行字符賦值t-ltag=0; /初始化 ltag 和 rtag,讓他們的初值都為0 t-rtag=0; t-lchild=createbitree(t-lchild); /構建結點的左孩子t-rchild=createbitree(t-rchild); /構建結點的右孩子 return t; /返回結點的地址 /二叉樹的遞歸遍歷void preorder

22、traverse(bit t) /先序遍歷 if(t) printf(%c,t-data); /遍歷根結點preordertraverse(t-lchild); /遍歷左孩子preordertraverse(t-rchild);/ 遍歷右孩子 void inordertraverse(bit t) /中序遍歷 if(t) inordertraverse(t-lchild);/遍歷左孩子printf(%c,t-data);/ 遍歷根結點inordertraverse(t-rchild);/遍歷右孩子 void postordertraverse(bit t) /后序遍歷 if(t) postor

23、dertraverse(t-lchild);/遍歷左孩子postordertraverse(t-rchild);/ 遍歷右孩子printf(%c,t-data);/ 遍歷根結點 void guangyi(bit t) /廣義表遍歷 if(t) if(t-lchild=null & t-rchild=null) /判斷結點的左右孩子都是否為空 printf(%c,t-data);/ 都為空時，輸出結點字符 else /至少有一個不為空時printf(%c,t-data);/ 輸出結點的字符if(t-lchild)printf(,);guangyi(t-lchild);/判斷結點的左孩子是

24、否為空，不為空時，遞歸的調用guangyi 函數if(t-rchild)printf(,);guangyi(t-rchild);printf();/判 斷 結 點 的右孩子是否為空，不為空時，遞歸的調用guangyi 函數else printf(); /否則輸出） /二叉樹的線索化bit pre;/定義全局的指針變量，用于指向當前時刻的結點位置/先序線索void prethreading(bit p) /先序線索化 if(p) / 判斷結點是否為空 if(!p-lchild)p-ltag=1;p-lchild=pre; /前驅線索if(!pre-rchild)pre-rtag=1;pre-rc

25、hild=p; /后繼線索pre=p; /保持 pre指向 p 的前驅if(p-ltag=0)prethreading(p-lchild);/ 左子樹線索化if(p-rtag=0)prethreading(p-rchild); / 右子樹線索化 bit preorderthreading(bit thrt,bit t)/ 先序遍歷二叉樹 t，并將其線索化， thrt 指向頭結點并返回到主函數中 thrt=(bit)malloc(sizeof(bit);/ 相內存中申請結點thrt-data=#; /頭指針內容為空thrt-ltag=0;thrt-rtag=1; /建立頭結點thrt-rchil

26、d=thrt;/ 右指針回指if(!t)/ 若二叉樹為空，則左指針回指 thrt-lchild=thrt; else thrt-lchild=t; pre=thrt; prethreading(t); /先序遍歷進行先序線索化pre-rchild=thrt;pre-rtag=1;/最后一個結點的線索化thrt-rchild=null; return thrt; void preorderthread(bit t) /先序遍歷 if(t) /判斷輸出的內容if(t-ltag=0 & t-rtag=0)printf(%c的 左 、 右 孩 子 分 別為：%c %cn,t-data,t-lc

27、hild-data,t-rchild-data); if(t-ltag=1 & t-rtag=0)printf(%c的 右 孩 子 和 前 驅 分 別為：%c %cn,t-data,t-rchild-data,t-lchild-data); if(t-ltag=0 & t-rtag=1)printf(%c的 左 孩 子 和 后 繼 分 別為：%c %cn,t-data,t-lchild-data,t-rchild-data); if(t-ltag=1 & t-rtag=1)printf(%c的 前 驅 和 后 繼 分 別為：%c %cn,t-data,t-lchild-

28、data,t-rchild-data); if(t-ltag=0)preorderthread(t-lchild); /遍歷左孩子if(t-rtag=0)preorderthread(t-rchild); / 遍歷右孩子 /中序線索int inthreading(bit p)/ 中序線索化 if(p) inthreading(p-lchild);/ 左子樹線索化if(!p-lchild)p-ltag=1;p-lchild=pre;/判斷結點的左孩子是否存在，讓其指向其前驅if(!pre-rchild)pre-rtag=1;pre-rchild=p;/ 后繼線索化pre=p;/保持 pre指向

29、p 的前驅inthreading(p-rchild);/右子樹線索化 bit inorderthreading(bit thrt,bit t)/ 中序遍歷二叉樹 t，并將其線索化， thrt 指向頭結點并返回到主函數中 thrt=(bit)malloc(sizeof(bit);/ 向內存中申請一個頭結點thrt-data=#;/給頭結點賦值為空thrt-ltag=0; thrt-rtag=1;thrt-rchild=thrt;/ 頭結點右指針回指if(!t)thrt-lchild=thrt;/ 若二叉樹為空，則左指針回指else thrt-lchild=t;/ 二叉樹不為空，左指針指向樹pre

30、=thrt;/pre 賦初值inthreading(t);/中序線索化二叉樹pre-rchild=thrt;/ 最后一個結點線索化pre-rtag=1; thrt-rchild=null; return thrt; void inorderthread(bit t) if(t) if(t-ltag=0)preorderthread(t-lchild); /遍歷左孩子if(t-ltag=0 & t-rtag=0)printf(%c的 左 、 右 孩 子 分 別為：%c %cn,t-data,t-lchild-data,t-rchild-data); if(t-ltag=1 & t

31、-rtag=0)printf(%c的 右 孩 子 和 前 驅 分 別為：%c %cn,t-data,t-rchild-data,t-lchild-data); if(t-ltag=0 & t-rtag=1)printf(%c的 左 孩 子 和 后 繼 分 別為：%c %cn,t-data,t-lchild-data,t-rchild-data); if(t-ltag=1 & t-rtag=1)printf(%c的 前 驅 和 后 繼 分 別為：%c %cn,t-data,t-lchild-data,t-rchild-data); if(t-rtag=0)preorderthre

32、ad(t-rchild); / 遍歷右孩子 /后序線索int postthreading(bit p) if(p) inthreading(p-lchild); inthreading(p-rchild); if(!p-lchild)p-ltag=1;p-lchild=pre; if(!pre-rchild)pre-rtag=1;pre-rchild=p; pre=p; bit postorderthreading(bit thrt,bit t) thrt=(bit)malloc(sizeof(bit); thrt-data=#; thrt-ltag=0; thrt-rtag=1;thrt-r

33、child=thrt; if(!t)thrt-lchild=thrt; else thrt-lchild=t; pre=thrt; inthreading(t); pre-rchild=thrt; pre-rtag=1; thrt-rchild=null; return thrt; void postorderthread(bit t) if(t) if(t-ltag=0)preorderthread(t-lchild); /遍歷左孩子if(t-rtag=0)preorderthread(t-rchild); / 遍歷右孩子if(t-ltag=0 & t-rtag=0)printf(%

34、c的 左 、 右 孩 子 分 別為：%c %cn,t-data,t-lchild-data,t-rchild-data); if(t-ltag=1 & t-rtag=0)printf(%c的 右 孩 子 和 前 驅 分 別為：%c %cn,t-data,t-rchild-data,t-lchild-data); if(t-ltag=0 & t-rtag=1)printf(%c的 左 孩 子 和 后 繼 分 別為：%c %cn,t-data,t-lchild-data,t-rchild-data); if(t-ltag=1 & t-rtag=1)printf(%c的 前

35、驅 和 后 繼 分 別為：%c %cn,t-data,t-lchild-data,t-rchild-data); /將線索樹還原成普通樹int returntree(bit t) if(t-ltag=0)returntree(t-lchild);/ 遍歷左子樹 ,找到 ltag=1的結點else t-lchild=null; /令左指針指向空if(t-rtag=0)returntree(t-rchild);/遍歷右子樹，找到rtag=1 的結點else t-rchild=null; /令右指針指向空 int cleantree(bit t) / 樹的清空if(t) if(t-lchild)cl

36、eantree(t-lchild); if(t-rchild)cleantree(t-rchild); free(t); void main() bit *l,*thrt; char x; printf( *n); printf( 二叉樹的三種遍歷（ #表示為空?。?n); printf( 例如輸入： abc#de#g#f#n); printf( *n); printf( 請輸入二叉樹： ); l=createbitree(l); while(1) printf( =*操 作 選 擇*=n); printf( * 遍 歷* 請輸入 *1n); printf( * 線 索* 請輸入 *2n);

37、printf( * 退 出* 請輸入 *0n); printf( 操作數： ); scanf(%s,&x); switch(x) case 1: printf( 先序遍歷： ); preordertraverse(l); printf(n); printf( 中序遍歷： ); inordertraverse(l); printf(n); printf( 后序遍歷： ); postordertraverse(l); printf(n); printf( 廣義遍歷： ); guangyi(l); printf(n);break; case 2: thrt=preorderthreading

38、(thrt,l); if(thrt)printf( 二叉樹先序線索化成功！ n); preorderthread(l); returntree(l); free(thrt); thrt=inorderthreading(thrt,l); if(thrt)printf( 二叉樹中序線索化成功！ n); inorderthread(l); returntree(l); free(thrt); thrt=postorderthreading(thrt,l); if(thrt)printf( 二叉樹后序線索化成功！ n); postorderthread(l); returntree(l); free

39、(thrt);break; case 0:break; default:printf(輸入有誤！請重新輸入！n); if(x=0)break; 2、赫夫曼編碼：#include typedef struct /赫夫曼編碼結構體char ch; /編碼存儲類型unsigned int weight;/權值unsigned int parent,lchild,rchild; / 雙親、左孩子、右孩子htnode,*huffmantree; typedef char *huffmancode; /動態(tài)分配數組存儲赫夫曼編碼int select(huffmantree ht,int n,int *s1

40、,int *s2) /在赫夫曼樹中選取兩個雙親為零且權值最小的兩個節(jié)點，用s1、s2 返回 int i,j; for(j=1;j=n;+j) if(htj.parent=0) /選取第一個雙親不為零的結點賦值給s1 *s1=j; break; for(i=j+1;i=n;+i) if(hti.weightht*s1.weight&hti.parent=0)/選出權值最小的節(jié)點*s1=i; for(j=1;j=n;+j) /選出雙親為零且不是s1的結點if(htj.parent=0&*s1!=j) *s2=j; break; for(i=j+1;i=n;+i) if(hti.weightht*s2.weight&hti.parent=0&*s1!=i) /選出權值次小的節(jié)點 *s2=i; if(*s2*s1) /判斷兩個權值的大小是否符合要求，不符合交換 i=*s1; *s1=*s2; *s2=i; void huffmancoding(huffma