数据结构树和二叉树实验报告

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#i nclude <stdio.h>#in elude <malloc.h>#defi ne MaxSize 100typedef char ElemType;typedef struct nodeElemType data;struct node *lchild;struct node *rchild; BTNode;void CreateBTNode(BTNode *&b,char *str)BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0;char ch;b=NULL;

4、ch=strj;while (ch!='0')switch(ch)case '(':top+;Sttop=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;elseswitch(k)case 1:Sttop->lchild=p;break; case 2:Sttop

5、->rchild=p;break; j+;ch=strj;BTNode *Fi ndNode(BTNode *b,ElemType x)BTNode *p;if (b=NULL)return NULL;else if (b->data=x) return b;elsep=Fi ndNode(b->lchild,x);if (p!=NULL)return p;elseretur n Fin dNode(b->rchild,x);BTNode *LchildNode(BTNode *p)retur n p->lchild;BTNode *RchildNode(BTNo

6、de *p)return p->rchild;int BTNodeDepth(BTNode *b)int lchilddep,rchilddep;if (b=NULL) return(0);else lchilddep=BTNodeDepth(b->lchild); rchilddep=BTNodeDepth(b->rchild);return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1); void DispBTNode(BTNode *b)if (b!=NULL)prin tf("%c",b

7、->data);if (b->lchild!=NULL | b->rchild!=NULL) prin tf("(");DispBTNode(b->lchild);if (b->rchild!=NULL) pri ntf(",");DispBTNode(b->rchild);prin tf(")");int BTWidth(BTNode *b)structint Ino;BTNode *p; QuMaxSize;int fron t,rear;int lnum ,max,i, n;fron t=re

8、ar=0;if (b!=NULL)rear+;Qurear.p=b;Qurear.l no=1;while (rear!=fro nt)fron t+;b=Qufr on t.p;lnum=Qufr ont.lno;if (b->lchild!=NULL)rear+;Qurear.p=b->lchild;Qurearno=lnu m+1;if (b->rchild!=NULL)rear+;Qurear.p=b->rchild;Qurear.l no=1 nu m+1;max=0;l num=1;i=1;while (i<=rear)n=0;while (i<

9、=rear && Qui.l no=lnum)n+;i+;lnum=Qui.l no;if (n> max) max=n;return ma x;elsereturn 0;int Nodes(BTNode *b)int nu m1, nu m2;if (b=NULL) return 0;else if (b->lchild=NULL && b->rchild=NULL) return 1;elsenu m仁Nodes(b->lchild);nu m2=Nodes(b->rchild); retur n (nu m1+ nu m2+1

10、);int LeafNodes(BTNode *b)int nu m1, nu m2;if (b=NULL) return 0;else if (b->lchild=NULL && b->rchild=NULL) return 1;elsenu m仁LeafNodes(b->lchild);nu m2=LeafNodes(b->rchild);retur n (nu m1+ nu m2);void mai n()BTNode *b,*p,*lp,*rp;CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N),C(F,G(,l

11、)"); printf(” 输出二叉树:");DispBTNode(b);printf("n”); printf("'H'结点:");p=Fi ndNode(b,'H');if (p!=NULL)lp=LchildNode(p);if (lp!=NULL)printf("左孩子为 %c ",lp->data);elseprintf("无左孩子”)；rp=RchildNode(p);if (rp!=NULL)printf("右孩子为 %c",rp->da

12、ta);elseprintf("无右孩子”)；prin tf("n");printf("二叉树 b 的深度：dn",BTNodeDepth(b); printf("二叉树 b 的宽度:%dn",BTWidth(b);printf("二叉树 b 的结点个数:%dn",Nodes(b); printf("二叉树 b 的叶子结点个数：dn",LeafNodes(b);7-2#i nclude <stdio.h>#in clude <malloc.h>#defi ne

13、MaxSize 100typedef char ElemType;typedef struct nodeElemType data; struct node *lchild; struct node *rchild; BTNode;void CreateBTNode(BTNode *&b,char *str)BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0;char ch;b=NULL;ch=strj;while (ch!='0')switch(ch)case '(':top+;Sttop=p;k=1; break;c

14、ase ')':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;elseswitch(k)case 1:Sttop->lchild=p;break; case 2:Sttop->rchild=p;break; j+;ch=strj;void DispBTNode(BTNode *b)if (b!=NULL)prin tf("

15、;%c",b->data);if (b->lchild!=NULL | b->rchild!=NULL)prin tf("(");DispBTNode(b->lchild); if (b->rchild!=NULL) pri ntf(","); DispBTNode(b->rchild); prin tf(")");void PreOrder(BTNode *b)if (b!=NULL)prin tf("%c ”,b->data);PreOrder(b->lchild

16、); PreOrder(b->rchild);void PreOrder1(BTNode *b)BTNode *StMaxSize,*p;int top=-1;if (b!=NULL)top+;Sttop=b;while (top>-1)p=Sttop;top-;prin tf("%c ",p->data);if (p->rchild!=NULL)top+;Sttop=p->rchild;if (p->lchild!=NULL)top+;Sttop=p->lchild;prin tf("n");void InO

17、rder(BTNode *b)if (b!=NULL)In Order(b->lchild);prin tf("%c ”,b->data);In Order(b->rchild);void InO rder1(BTNode *b)BTNode *StMaxSize,*p;int top=-1;if (b!=NULL)p=b;while (top>-1 | p!=NULL)while (p!=NULL)top+;Sttop=p; p=p->lchild;if (top>-1) p=Sttop; top-;prin tf("%c "

18、,p->data); p=p->rchild;prin tf("n");void PostOrder(BTNode *b)if (b!=NULL)PostOrder(b->lchild);PostOrder(b->rchild);prin tf("%c ”,b->data);void PostOrder1(BTNode *b)BTNode *StMaxSize;BTNode *p;int flag,top=-1;if (b!=NULL)dowhile (b!=NULL)top+;Sttop=b; b=b->lchild;p=NU

19、LL;flag=1;while (top!=-1 && flag)b=Sttop;if (b->rchild=p)prin tf("%c ",b->data); top-;p=b; elseb=b->rchild; flag=0; while (top!=-1);prin tf("n");void LevelOrder(BTNode *b) BTNode *p;BTNode *quMaxSize;int fron t,rear;fron t=rear=-1;rear+;qurear=b;while (fron t!=rear)fron t=(fro nt+1)%MaxSize;p=qu fron t;prin tf("%c ",p->data);if (p->lchild!=NULL) rear=(rear+1)%MaxSize; qurear=p->lchild;if (p->rchild!=NULL) r