1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告三學(xué)校： 班級： 學(xué)號： 姓名： 日期： 程序名：作業(yè)二叉樹的遞歸操作.cpp一、上機(jī)實(shí)驗(yàn)的問題和要求：要求采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，完成二叉樹的建立，前序、中序和后序遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作等。具體實(shí)現(xiàn)要求：基于先序遍歷的構(gòu)造算法：輸入是二叉樹的先序序列，但必須在其中加入虛結(jié)點(diǎn)以示空指針的位置。假設(shè)虛結(jié)點(diǎn)輸入時(shí)用空格字符表示。用廣義表表示所建二叉樹。用凹入表表示所建二叉樹。分別利用前序遍歷、中序遍歷、后序遍歷所建二叉樹。求二叉樹結(jié)點(diǎn)總數(shù)，觀察輸出結(jié)果。求二叉樹葉子總數(shù)，觀察輸出結(jié)果。交換各結(jié)點(diǎn)的左右子樹，用廣義表表示法顯示新的二叉樹。（）二叉樹采用鏈接存儲(chǔ)結(jié)構(gòu)，

2、其根結(jié)點(diǎn)指針為T，設(shè)計(jì)一個(gè)算法對這棵二叉樹的每個(gè)結(jié)點(diǎn)賦值：（注意要修改DataType類型）葉結(jié)點(diǎn)的值為3只有左孩子或右孩子的結(jié)點(diǎn)則其值分別等于左孩子或右孩子的值左、右孩子均有的結(jié)點(diǎn)，則其值等于左、右孩子結(jié)點(diǎn)的值之和用廣義表表示法顯示所建二叉樹閱讀理解建立Huffman樹的算法，對該算法進(jìn)行運(yùn)行及調(diào)試。具體實(shí)現(xiàn)要求：調(diào)試并運(yùn)行Huffman算法，驗(yàn)算回家作業(yè)六的第3題。（）求Huffman樹的帶權(quán)路徑長度WPL。二、程序設(shè)計(jì)的基本思想，原理和算法描述：（包括程序的結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)，輸入/輸出設(shè)計(jì)，符號名說明等）基本思想：對任意一棵二叉樹，試將其所有節(jié)點(diǎn)的左、右子樹交換。并將交換前、后不同的二叉樹

3、分別用前序、中序、和后序三種不同的方法進(jìn)行遍歷?；驹恚和揪€性表、特殊線性表相似，二叉樹也有順序和鏈?zhǔn)絻煞N基本的存儲(chǔ)結(jié)構(gòu)。因此針對不同的存儲(chǔ)結(jié)構(gòu)，在實(shí)現(xiàn)左右子樹交換的過程中方法會(huì)有不同。在程序?qū)崿F(xiàn)過程中要求不同功能分別用單個(gè)的函數(shù)實(shí)現(xiàn)，其中按層遍歷二叉樹的函數(shù)用順序方法實(shí)現(xiàn)，其他函數(shù)用鏈?zhǔn)椒椒▽?shí)現(xiàn)?；驹恚海?）創(chuàng)建二叉樹。（2）用三種不同的方法遍歷交換左右子樹前的二叉樹。（3）交換二叉樹中所有結(jié)點(diǎn)的左右子樹。（4）用三種不同的方法遍歷交換左右子樹后的二叉樹。三、源程序及注釋：/要求采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，完成二叉樹的建立，前序、中序和后序遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作等#i

4、nclude #include #include #include #define NULL 0typedef char DataType;typedef struct BinTNodeDataType data;struct BinTNode *rchild,*lchild;BinTNode,*BinTree;/創(chuàng)建二叉數(shù)void Create(BinTree *T)char ch;if(ch = getchar() = *)/輸入*時(shí)該節(jié)點(diǎn)為空*T = NULL;else*T = (BinTree)malloc(sizeof(BinTNode);(*T)-data = ch;Create(

5、&(*T)-lchild);Create(&(*T)-rchild);/先序遍歷二叉樹void PreOrder(BinTree T)if(T)printf(%c,T-data);PreOrder(T-lchild);PreOrder(T-rchild);/中序遍歷二叉樹void InOrder(BinTree T) if(T)InOrder(T-lchild);printf(%c,T-data);InOrder(T-rchild);/后序遍歷二叉樹void PostOrder(BinTree T)if(T)PostOrder(T-lchild);PostOrder(T-rchild);pri

6、ntf(%c,T-data);/用廣義表表示二叉樹void ListPrint(BinTree T)if(T)printf(%c,T-data);if(T-lchild != NULL | T-rchild != NULL)printf();ListPrint(T-lchild);if(T-lchild != NULL)printf(,);ListPrint(T-rchild);printf();/用凹入表表示二叉樹/*對于凹入表表示二叉樹，其實(shí)就是把二叉樹結(jié)點(diǎn)的深度表示出來*/void DisplayPrint(BinTree T,int lay)if(T)for(int i=0;idata

7、);DisplayPrint(T-lchild,lay+1);DisplayPrint(T-rchild,lay+1);/求結(jié)點(diǎn)的個(gè)數(shù)int Node(BinTree T)int static N=0;if(T)Node(T-lchild);N+;Node(T-rchild);return N;/求葉子的個(gè)數(shù)int Leaf(BinTree T)int static L=0;if(T)Leaf(T-lchild);if(!(T-lchild|T-rchild)/沒有左子樹和右子樹,就是葉子L+;Leaf(T-rchild);return L;/交換左子樹和右子樹void Change(BinT

8、ree *T)if(*T)BinTNode *temp;Change(&(*T)-lchild);Change(&(*T)-rchild);temp=(*T)-lchild;(*T)-lchild=(*T)-rchild;(*T)-rchild=temp;void main()BinTree T;printf(輸入先序序列:);Create(&T);printf(輸出先序遍歷:);PreOrder(T);printf(n);printf(輸出中序遍歷:);InOrder(T);printf(n);printf(輸出后序遍歷:);PostOrder(T);printf(n);printf(輸出廣

9、義表表示法:);ListPrint(T);printf(n);printf(輸出凹入表表示法:n);DisplayPrint(T,1);printf(結(jié)點(diǎn)的個(gè)數(shù):nodes = %dn,Node(T);printf(葉子的個(gè)數(shù):leaves = %dn,Leaf(T);Change(&T);printf(交換左右子樹，并用廣義表表示法:);ListPrint(T);printf(n);四、運(yùn)行輸出結(jié)果：五、調(diào)試和運(yùn)行程序過程中產(chǎn)生的問題及采取的措施：有語法錯(cuò)誤和打程序時(shí)的拼寫錯(cuò)誤，主要就是根據(jù)出錯(cuò)的地方進(jìn)行單方面的調(diào)試。六、對算法的程序的討論、分析，改進(jìn)設(shè)想，其它經(jīng)驗(yàn)教訓(xùn)：在算法實(shí)現(xiàn)上，從算法的效率看，非遞歸方法具有較好的時(shí)間效率，遞歸方法書寫形式較為簡捷，更為直