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

精品学习资源试验四树和二叉树的操作一、试验题目：用菜单驱动的手法，编写一个完整的程序，生成一棵二叉树， 求二叉树的高度，求二叉树的叶子结点数，输出二叉树的全部结点；二、试验算法描述 ：二叉树的生成是指如何在内存中建立二叉树的储备结构；建立次序储备结构的问题较简洁，这里仅争论如何建立二叉链表；要建立二叉链表，就需要依据某种方式输人二叉树的结点及其规律信息；留意到对二叉树遍历时，不仅得到了结点信息，而且由序列中结点的先后关系仍可获得肯定的规律信息，假如这些信息足够，就可依据遍历序列生成相应的二叉树二叉树的生成方法就是基于遍历序列的，相当于遍历问题的逆问题，即由遍历序列反求二叉树，这需要分析和利用二叉树遍历序列的特点；在以下两种方法中任选一种；* 以下的 <一） <二）要编写在一个完整的程序中；假如你不能编在一个程序中，就可以用两个完整的程序来实现；<一）用先根序列建立二叉树二叉树的结点就按相应的遍历过程逐个生成；类似层次遍历，假如不对遍历序列作些补充，是不能完整反映结点间的规律关系的，也就不能得到正确的结果；补充的方法也是增加虚结点，但这里只需对空指针对应的位置进行补 充，而不必补充到完全二叉树的形式；以先根遍历上图为例，二叉树的先根输入序列为：ABD G CE FH其中表示虚结点，这里不需要终止符；算法过程为，先生成根结点，再生成左子树，然后是右子树，左右子树的生成采纳递归；在详细作本试验时, 仍需编写一个主函数调用这个函数来生成二叉树, 最终输出二叉树的结点序列；<二）按完全二叉树的层次次序，依次输入结点信息来建立二叉链表这是由于完全三叉树的层次遍历序列中，结点间的序号关系可反映父子关系即规律关系；对一般的二又树，要补充如干个虚结点使其成为完全二叉树后，冉按其层次次序输入；例如，仅含 3个结点A、B、C的右单支树 <见下图2），按完全二叉树的形式输入的结点序列为：AB C，其中表示虚结点，表示输入终止；算法的基本思想是： 依次输入结点信息，如输入的结点不是虚结点，就建立一个新结点：如新结点是第 1个结点，就令其为根结点；否就将新结点作为孩子链接到它的双亲结点上；如此重复下去，直至输入字符“”为止；这里的关键是新结点与其双亲的链接；由于是按层次自左至右输入结点的，所以先输入的结点，其孩子也必定较先输入；即结点与其孩子具有先进先出的特点，于是可设置一个队列，储存已输人结点的地址；这样，队尾是当前正输入的结点，队头是其双亲结点；当队头结点的两个孩子都输入完毕后，出队，新的队头是下一个要输入孩子的双亲结点；如此下去，直到输入终止符为止；双亲与孩子的链接方法是：如当前输入的结点编号是偶数，就该结点作为欢迎下载精品学习资源左孩子与其双亲链接；否就作为右孩子与其双亲链；如双亲结点或孩子结点为虚结点，就无需链接；试验程序如下：#include<stdio.h> #include<malloc.h> #include<stdlib.h> #include<string.h>int cmpconst void *a,const void *b>return *int *>a-*int *>b；typedef char datatype；typedef struct treenodedatatype data ；struct treenode *leftchild,*rightchild；treenode,*bitree ；treenode *t ；int count=0 ；/建立二叉树方法 1treenode *creattree_1>treenode *t,*p,*v100；int i,j ；datatype e；t=NULL ；printf"n 请输入初始二叉树各结点的编号和对应的值<如1,a） :"> ；scanf"%d,%c",&i,&e>；whilei.=0&&e.='#'> p=treenode *>mallocsizeoftreenode>>；p->data=e；p->leftchild=NULL；p->rightchild=NULL；vi=p ；ifi=1>t=p ；else j=i/2 ；ifi%2=0>vj->leftchild=p；elsevj->rightchild=p；欢迎下载精品学习资源printf"n 请连续输入 <以0， #终止） :"> ；scanf"%d,%c",&i,&e>；return t> ；/建立二叉树方法 2 treenode *creattree_2>treenode *t ；datatype 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 *p>ifp> printf"%-4c",p->data>；preorderp->leftchild> ；preorderp->rightchild> ；/中序遍历输出二叉树void inordertreenode *p> ifp>inorderp->leftchild> ；printf"%-4c",p->data> ；inorderp->rightchild>；/后序遍历输出二叉树 void postordertreenode *p>ifp>欢迎下载精品学习资源postorderp->leftchild> ；postorderp->rightchild> ；printf"%-4c",p->data> ；/运算二叉树高度int treedepthbitree bt>int lefthight,righthight,max；ifbt.=NULL> lefthight=treedepthbt->leftchild>；righthight=treedepthbt->rightchild>；max=lefthight>righthight>.lefthight:righthight；returnmax+1> ；elsereturn 0> ；/逆时针旋转 90度输出二叉树void printtreebitree bt,int level> int j ；ifbt>printtreebt->rightchild,level+1>；forj=0 ；j<=6*level ；j+>printf" "> ；printf"%cn",bt->data>；printtreebt->leftchild,level+1>；/交换二叉树左右子树void exchangebitree bt> bitree p ；ifbt>p=bt->leftchild ；bt->leftchild=bt->rightchild；bt->rightchild=p ；exchangebt->leftchild> ；exchangebt->rightchild> ；欢迎下载精品学习资源/运算叶结点数int leafcountbitree bt> ifbt.=NULL>leafcountbt->leftchild>；leafcountbt->rightchild>；ifbt->leftchild=NULL>&&bt->rightchild=NULL>>count+；return count> ；/输出叶结点void paintleafbitree bt> ifbt.=NULL>ifbt->leftchild=NULL&&bt->rightchild=NULL>printf"%-4c",bt->data>；paintleafbt->leftchild>；paintleafbt->rightchild>；/哈夫曼树 int haffman>int a100,b100 ；int i,j=0,k,n ；memseta,0,100>；memsetb,0,100>；printf" 请输入构造哈夫曼树的元素个数<正整数）： "> ；scanf"%d",&n> ；printf"n"> ；printf" 请依次输入各元素权值<以空格间隔，按 ENTER 键终止）： n"> ；fori=0 ；i<n ； i+>scanf"%d",&ai>；printf"n"> ；getchar>；printf" 构造哈夫曼树过程： nn"> ；fori=0 ；i<n ； i+>qsorta,n,sizeofa0>,cmp>；printf" 步骤 <%d） ",i+1> ；欢迎下载精品学习资源fork=i ； k<n； k+>printf"%d ",ak>；printf"nn"> ；bj+=ai ；bj+=ai+1；ai+1=ai+ai+1；printf" 当前哈夫曼树的全部结点权值为：n"> ；fori=0 ；i<j-1 ；i+>printf"%-5d",bi>；printf"nn"> ；int main>int command ；char order；doprintf"=简洁二叉树操作菜单 =n">；printf"*1.建立二叉树 <依据完全二叉树）*n"> ；printf"*2.建立二叉树 <仿照先序递归遍历）*n"> ；printf"*3.先序递归遍历二叉树*n"> ；printf"*4.中序递归遍历二叉树*n"> ；printf"*5.后序递归遍历二叉树*n"> ；printf"*6.输出二叉树的高度*n"> ；printf"*7.输出二叉树的叶结点*n"> ；printf"*8.交换二叉树的左右子树*n"> ；printf"*9.打印二叉树*n"> ；printf"*10.哈夫曼树 <最优二叉树）*n"> ；printf"*0.退出*n"> ；printf"=nn">；printf" 请输入指令 <0,1,2,3,4,5,6,7,8,9,10 ） :"> ；scanf"%d",&command> ；ifcommand<0|command>10>欢迎下载精品学习资源system"cls"> ；switchcommand>getchar>；printf"n 指令输入错误！请重新输入！n"> ；欢迎下载精品学习资源case 1:getchar>；system"cls"> ；printf" 如已构建二叉树，此操作将会清除当前二叉树，连续/退出 Y/N:"> ；scanf"%c",&order>；iforder='Y'|order='y'>欢迎下载精品学习资源t=creattree_1>；ift>printf"n"> ；elseprintf"n 当前二叉树为 <逆时针旋转 90度）： n"> ；printtreet,0> ；printf"n 当前二叉树为空！请先建立二叉树！n"> ；欢迎下载精品学习资源getchar>；break；elsebreak；case 2: getchar>；system"cls"> ；printf" 如已构建二叉树，此操作将会清除当前二叉树，连续/退出 Y/N:"> ；scanf"%c",&order>；iforder='Y'|order='y'>printf"n 请输入二叉树按先序递归遍历各结点的值<虚结点以 #代替） :n"> ；fflushstdin> ；t=creattree_2> ；ift>printf"n 当前二叉树为 <逆时针旋转 90度）： n"> ；printtreet,0> ；printf"n"> ；elseprintf"n 当前二叉树为空！请先建立二叉树！n"> ；欢迎下载精品学习资源getchar>；break；else欢迎下载精品学习资源case 3: getchar>；system"cls"> ；ift>break；欢迎下载精品学习资源printf"n 当前二叉树为 <逆时针旋转 90度）： n"> ；printtreet,0> ；欢迎下载精品学习资源printf"n"> ；preordert> ；printf"n"> ；printf"n 先序递归遍历序列为 :n"> ；欢迎下载精品学习资源elseprintf"n 二叉树为空！请先建立二叉树！n"> ；break；欢迎下载精品学习资源case 4: getchar>；system"cls"> ；ift>欢迎下载精品学习资源printf"n 当前二叉树为 <逆时针旋转 90度）： n"> ；printtreet,0> ；欢迎下载精品学习资源printf"n"> ；inordert> ；printf"n"> ；printf"n 中序递归遍历序列为 :n"> ；欢迎下载精品学习资源elseprintf"n 二叉树为空！请先建立二叉树！n"> ；break；欢迎下载精品学习资源欢迎下载精品学习资源case 5: getchar>；system"cls"> ；ift>欢迎下载精品学习资源printf"n 当前二叉树为 <逆时针旋转 90度）： n"> ；printtreet,0> ；欢迎下载精品学习资源printf"n"> ；printf"n 后序递归遍历序列为 :n"> ；postordert> ；printf"n"> ；欢迎下载精品学习资源elseprintf"n 二叉树为空！请先建立二叉树！n"> ；break；欢迎下载精品学习资源system"cls"> ；case 6: getchar>；ift>欢迎下载精品学习资源printf"n"> ；printf"n 当前二叉树为 <逆时针旋转 90度）： n"> ；printtreet,0> ；欢迎下载精品学习资源printf" 当前二叉树的高度为 :%dn",treedeptht>> ；欢迎下载精品学习资源elsebreak；printf"n 二叉树为空！请先建立二叉树！n"> ；欢迎下载精品学习资源欢迎下载精品学习资源system"cls"> ；case 7: getchar>；ift>欢迎下载精品学习资源printf"n"> ；printf"n 当前二叉树为 <逆时针旋转 90度）： n"> ；printtreet,0> ；printf" 当前二叉树的叶子结点数为:%dnn",leafcountt>> ；printf" 当前二叉树的叶子结点依次为:n"> ；欢迎下载精品学习资源欢迎下载精品学习资源elsebreak；case 8:paintleaft> ；printf"n"> ；printf"n 二叉树为空！请先建立二叉树！n"> ；欢迎下载精品学习资源system"cls"> ；getchar>；ift>欢迎下载精品学习资源printf"n"> ；elsebreak；case 9:printf"n 当前二叉树为 <逆时针旋转 90度）： n"> ；printtreet,0> ；exchanget>；printf"n 交换后的二叉树为 :n"> ；printtreet,0> ；printf"n"> ；printf"n 二叉树不存在！请先建立二叉树！n"> ；欢迎下载精品学习资源system"cls"> ；elsegetchar>；ift>printf"n 当前二叉树为 <逆时针旋转 90度）： n"> ；printtreet,0> ；printf"n"> ；欢迎下载精品学习资源printf"n 二叉树不存在！请先建立二叉树！n"> ；break；case 10:getchar>；system"cls"> ；printf"=哈夫曼树的建立与输出=nn">；欢迎下载精品学习资源haffman> ；break；ifcommand=0>getchar>；system"cls"> ；printf" 再见！ nn"> ；break；printf"n 请按 ENTER 键返回主菜单 .n"> ；getchar> ；system"cls"> ；whilecommand>=1&&command<=10>；欢迎下载精品学习资源欢迎下载精品学习资源欢迎下载精品学习资源欢迎下载精品学习资源欢迎下载精品学习资源欢迎下载