2022年实验树和二叉树操作.docx

《2022年实验树和二叉树操作.docx》由会员分享，可在线阅读，更多相关《2022年实验树和二叉树操作.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品学习资源试验四树和二叉树的操作一、试验题目：用菜单驱动的手法，编写一个完整的程序，生成一棵二叉树， 求二叉树的高度，求二叉树的叶子结点数，输出二叉树的全部结点；二、试验算法描述 ：二叉树的生成是指如何在内存中建立二叉树的储备结构；建立次序储备结构的问题较简洁，这里仅争论如何建立二叉链表；要建立二叉链表，就需要依据某种方式输人二叉树的结点及其规律信息；留意到对二叉树遍历时，不仅得到了结点信息，而且由序列中结点的先后关系仍可获得肯定的规律信息，假如这些信息足够，就可依据遍历序列生成相应的二叉树二叉树的生成方法就是基于遍历序列的，相当于遍历问题的逆问题，即由遍历序列反求二叉树，这需要分析和利用二

2、叉树遍历序列的特点；在以下两种方法中任选一种；* 以下的 一） 二）要编写在一个完整的程序中；假如你不能编在一个程序中，就可以用两个完整的程序来实现；一）用先根序列建立二叉树二叉树的结点就按相应的遍历过程逐个生成；类似层次遍历，假如不对遍历序列作些补充，是不能完整反映结点间的规律关系的，也就不能得到正确的结果；补充的方法也是增加虚结点，但这里只需对空指针对应的位置进行补 充，而不必补充到完全二叉树的形式；以先根遍历上图为例，二叉树的先根输入序列为：ABD G CE FH其中表示虚结点，这里不需要终止符；算法过程为，先生成根结点，再生成左子树，然后是右子树，左右子树的生成采纳递归；在详细作本试验

3、时, 仍需编写一个主函数调用这个函数来生成二叉树, 最终输出二叉树的结点序列；二）按完全二叉树的层次次序，依次输入结点信息来建立二叉链表这是由于完全三叉树的层次遍历序列中，结点间的序号关系可反映父子关系即规律关系；对一般的二又树，要补充如干个虚结点使其成为完全二叉树后，冉按其层次次序输入；例如，仅含 3个结点A、B、C的右单支树 见下图2），按完全二叉树的形式输入的结点序列为：AB C，其中表示虚结点，表示输入终止；算法的基本思想是： 依次输入结点信息，如输入的结点不是虚结点，就建立一个新结点：如新结点是第 1个结点，就令其为根结点；否就将新结点作为孩子链接到它的双亲结点上；如此重复下去，直至

4、输入字符“”为止；这里的关键是新结点与其双亲的链接；由于是按层次自左至右输入结点的，所以先输入的结点，其孩子也必定较先输入；即结点与其孩子具有先进先出的特点，于是可设置一个队列，储存已输人结点的地址；这样，队尾是当前正输入的结点，队头是其双亲结点；当队头结点的两个孩子都输入完毕后，出队，新的队头是下一个要输入孩子的双亲结点；如此下去，直到输入终止符为止；双亲与孩子的链接方法是：如当前输入的结点编号是偶数，就该结点作为欢迎下载精品学习资源左孩子与其双亲链接；否就作为右孩子与其双亲链；如双亲结点或孩子结点为虚结点，就无需链接；试验程序如下：#include #include #include #i

5、ncludeint cmpconst void *a,const void *breturn *int *a-*int *b；typedef char datatype；typedef struct treenodedatatype data ；struct treenode *leftchild,*rightchild；treenode,*bitree ；treenode *t ；int count=0 ；/建立二叉树方法 1treenode *creattree_1treenode *t,*p,*v100；int i,j ；datatype e；t=NULL ；printfn 请输入初始二

6、叉树各结点的编号和对应的值 ；scanf%d,%c,&i,&e；whilei.=0&e.=# p=treenode *mallocsizeoftreenode；p-data=e；p-leftchild=NULL；p-rightchild=NULL；vi=p ；ifi=1t=p ；else j=i/2 ；ifi%2=0vj-leftchild=p；elsevj-rightchild=p；欢迎下载精品学习资源printfn 请连续输入 ；scanf%d,%c,&i,&e；return t ；/建立二叉树方法 2 treenode *creattree_2treenode *t ；datatype

7、e；scanf%c,&e ；ife=#t=NULL ；else t=treenode *mallocsizeoftreenode；t-data=e；t-leftchild=creattree_2 ；t-rightchild=creattree_2 ；return t ；/先序遍历输出二叉树 void preordertreenode *pifp printf%-4c,p-data；preorderp-leftchild ；preorderp-rightchild ；/中序遍历输出二叉树void inordertreenode *p ifpinorderp-leftchild ；printf%-

8、4c,p-data ；inorderp-rightchild；/后序遍历输出二叉树 void postordertreenode *pifp欢迎下载精品学习资源postorderp-leftchild ；postorderp-rightchild ；printf%-4c,p-data ；/运算二叉树高度int treedepthbitree btint lefthight,righthight,max；ifbt.=NULL lefthight=treedepthbt-leftchild；righthight=treedepthbt-rightchild；max=lefthightrighthi

9、ght.lefthight:righthight；returnmax+1 ；elsereturn 0 ；/逆时针旋转 90度输出二叉树void printtreebitree bt,int level int j ；ifbtprinttreebt-rightchild,level+1；forj=0 ；jprintf ；printf%cn,bt-data；printtreebt-leftchild,level+1；/交换二叉树左右子树void exchangebitree bt bitree p ；ifbtp=bt-leftchild ；bt-leftchild=bt-rightchild；bt

10、-rightchild=p ；exchangebt-leftchild ；exchangebt-rightchild ；欢迎下载精品学习资源/运算叶结点数int leafcountbitree bt ifbt.=NULLleafcountbt-leftchild；leafcountbt-rightchild；ifbt-leftchild=NULL&bt-rightchild=NULLcount+；return count ；/输出叶结点void paintleafbitree bt ifbt.=NULLifbt-leftchild=NULL&bt-rightchild=NULLprintf%-

11、4c,bt-data；paintleafbt-leftchild；paintleafbt-rightchild；/哈夫曼树 int haffmanint a100,b100 ；int i,j=0,k,n ；memseta,0,100；memsetb,0,100；printf 请输入构造哈夫曼树的元素个数 ；scanf%d,&n ；printfn ；printf 请依次输入各元素权值 ；fori=0 ；iscanf%d,&ai；printfn ；getchar；printf 构造哈夫曼树过程： nn ；fori=0 ；iqsorta,n,sizeofa0,cmp；printf 步骤 ；欢迎下载精

12、品学习资源fork=i ； kprintf%d ,ak；printfnn ；bj+=ai ；bj+=ai+1；ai+1=ai+ai+1；printf 当前哈夫曼树的全部结点权值为：n ；fori=0 ；iprintf%-5d,bi；printfnn ；int mainint command ；char order；doprintf=简洁二叉树操作菜单 =n；printf*1.建立二叉树 ；printf*2.建立二叉树 ；printf*3.先序递归遍历二叉树*n ；printf*4.中序递归遍历二叉树*n ；printf*5.后序递归遍历二叉树*n ；printf*6.输出二叉树的高度*n ；p

13、rintf*7.输出二叉树的叶结点*n ；printf*8.交换二叉树的左右子树*n ；printf*9.打印二叉树*n ；printf*10.哈夫曼树 ；printf*0.退出*n ；printf=nn；printf 请输入指令 ；scanf%d,&command ；ifcommand10欢迎下载精品学习资源systemcls ；switchcommandgetchar；printfn 指令输入错误！请重新输入！n ；欢迎下载精品学习资源case 1:getchar；systemcls ；printf 如已构建二叉树，此操作将会清除当前二叉树，连续/退出 Y/N: ；scanf%c,&ord

14、er；iforder=Y|order=y欢迎下载精品学习资源t=creattree_1；iftprintfn ；elseprintfn 当前二叉树为 ；printtreet,0 ；printfn 当前二叉树为空！请先建立二叉树！n ；欢迎下载精品学习资源getchar；break；elsebreak；case 2: getchar；systemcls ；printf 如已构建二叉树，此操作将会清除当前二叉树，连续/退出 Y/N: ；scanf%c,&order；iforder=Y|order=yprintfn 请输入二叉树按先序递归遍历各结点的值 ；fflushstdin ；t=creattr

15、ee_2 ；iftprintfn 当前二叉树为 ；printtreet,0 ；printfn ；elseprintfn 当前二叉树为空！请先建立二叉树！n ；欢迎下载精品学习资源getchar；break；else欢迎下载精品学习资源case 3: getchar；systemcls ；iftbreak；欢迎下载精品学习资源printfn 当前二叉树为 ；printtreet,0 ；欢迎下载精品学习资源printfn ；preordert ；printfn ；printfn 先序递归遍历序列为 :n ；欢迎下载精品学习资源elseprintfn 二叉树为空！请先建立二叉树！n ；break；欢

16、迎下载精品学习资源case 4: getchar；systemcls ；ift欢迎下载精品学习资源printfn 当前二叉树为 ；printtreet,0 ；欢迎下载精品学习资源printfn ；inordert ；printfn ；printfn 中序递归遍历序列为 :n ；欢迎下载精品学习资源elseprintfn 二叉树为空！请先建立二叉树！n ；break；欢迎下载精品学习资源欢迎下载精品学习资源case 5: getchar；systemcls ；ift欢迎下载精品学习资源printfn 当前二叉树为 ；printtreet,0 ；欢迎下载精品学习资源printfn ；printfn

17、 后序递归遍历序列为 :n ；postordert ；printfn ；欢迎下载精品学习资源elseprintfn 二叉树为空！请先建立二叉树！n ；break；欢迎下载精品学习资源systemcls ；case 6: getchar；ift欢迎下载精品学习资源printfn ；printfn 当前二叉树为 ；printtreet,0 ；欢迎下载精品学习资源printf 当前二叉树的高度为 :%dn,treedeptht ；欢迎下载精品学习资源elsebreak；printfn 二叉树为空！请先建立二叉树！n ；欢迎下载精品学习资源欢迎下载精品学习资源systemcls ；case 7: ge

18、tchar；ift欢迎下载精品学习资源printfn ；printfn 当前二叉树为 ；printtreet,0 ；printf 当前二叉树的叶子结点数为:%dnn,leafcountt ；printf 当前二叉树的叶子结点依次为:n ；欢迎下载精品学习资源欢迎下载精品学习资源elsebreak；case 8:paintleaft ；printfn ；printfn 二叉树为空！请先建立二叉树！n ；欢迎下载精品学习资源systemcls ；getchar；ift欢迎下载精品学习资源printfn ；elsebreak；case 9:printfn 当前二叉树为 ；printtreet,0 ；

19、exchanget；printfn 交换后的二叉树为 :n ；printtreet,0 ；printfn ；printfn 二叉树不存在！请先建立二叉树！n ；欢迎下载精品学习资源systemcls ；elsegetchar；iftprintfn 当前二叉树为 ；printtreet,0 ；printfn ；欢迎下载精品学习资源printfn 二叉树不存在！请先建立二叉树！n ；break；case 10:getchar；systemcls ；printf=哈夫曼树的建立与输出=nn；欢迎下载精品学习资源haffman ；break；ifcommand=0getchar；systemcls ；printf 再见！ nn ；break；printfn 请按 ENTER 键返回主菜单 .n ；getchar ；systemcls ；whilecommand=1&command；欢迎下载精品学习资源欢迎下载精品学习资源欢迎下载精品学习资源欢迎下载精品学习资源欢迎下载精品学习资源欢迎下载