大数据结构树和二叉树实验资料报告材料.doc

《大数据结构树和二叉树实验资料报告材料.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》课程实验报告实验名称树和二叉树实验序号5实验日期姓名院系班级学号专业指导教师成绩教师评语一、实验目的和要求(1)掌握树的相关概念，包括树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树的深度、森林等定义。(2)掌握树的表示，包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。(3)掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。(4)掌握二叉树的性质。(5)重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。(6)重点掌握二叉树的基本运算和各种遍历算法的实现。(7)掌握线索二叉树的概念和相关算法的实现。(8)掌握哈夫曼树的定义、哈夫曼树

2、的构造过程和哈夫曼编码产生方法。(9)掌握并查集的相关概念和算法。(10)灵活掌握运用二叉树这种数据结构解决一些综合应用问题。二、实验项目摘要1．编写一程序，实现二叉树的各种基本运算，并在此基础上设计一个主程序完成如下功能：（1）输出二叉树b;（2）输出H结点的左、右孩子结点值；（3）输出二叉树b的深度；（4）输出二叉树b的宽度；（5）输出二叉树b的结点个数；（6）输出二叉树b的叶子结点个数。2．编写一程序，实现二叉树的先序遍历、中序遍历和后序遍历的各种递归和非递归算法，以及层次遍历的算法。三、实验预习容二叉树存储结构，二叉树基本运算（创建二叉树、寻找结点、找孩子结点、求高度、输出二叉树

3、）三、实验结果与分析7-1#include#include#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;structnode*lchild;structnode*rchild;}BTNode;voidCreateBTNode(BTNode*&b,char*str){BTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;b=NULL;ch=str[j];while(ch!=''){switch(ch){case'(

4、':top++;St[top]=p;k=1;break;case')':top--;break;case',':k=2;break;default:p=(BTNode*)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL)b=p;else{switch(k){case1:St[top]->lchild=p;break;case2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}BTNode*FindNode(BTNode*b,ElemTypex){BTNode*p

5、;if(b==NULL)returnNULL;elseif(b->data==x)returnb;else{p=FindNode(b->lchild,x);if(p!=NULL)returnp;elsereturnFindNode(b->rchild,x);}}BTNode*LchildNode(BTNode*p){returnp->lchild;}BTNode*RchildNode(BTNode*p){returnp->rchild;}intBTNodeDepth(BTNode*b){intlchilddep,rchilddep;if(b==NULL)return(0);else{lc

6、hilddep=BTNodeDepth(b->lchild);rchilddep=BTNodeDepth(b->rchild);return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);}}voidDispBTNode(BTNode*b){if(b!=NULL){printf("%c",b->data);if(b->lchild!=NULL

7、

8、b->rchild!=NULL){printf("(");DispBTNode(b->lchild);if(b->rchild!=NULL)printf(",");DispBTNode(b->r

9、child);printf(")");}}}intBTWidth(BTNode*b){struct{intlno;BTNode*p;}Qu[MaxSize];intfront,rear;intlnum,max,i,n;front=rear=0;if(b!=NULL){rear++;Qu[rear].p=b;Qu[rear].lno=1;while(rear!=front){front++;b=Qu[front].p;lnum=Qu[