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

-数据结构课程实验报告实验名称树和二叉树实验序号5实验日期姓 名院系班 级学 号专 业指导教师成 绩教师评语一、实验目的和要求(1)掌握树的相关概念，包括树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树的深度、森林等定义。(2)掌握树的表示，包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。(3)掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。(4)掌握二叉树的性质。(5)重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。(6)重点掌握二叉树的基本运算和各种遍历算法的实现。(7)掌握线索二叉树的概念和相关算法的实现。(8)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。(9)掌握并查集的相关概念和算法。(10)灵活掌握运用二叉树这种数据结构解决一些综合应用问题。二、实验项目摘要1编写一程序，实现二叉树的各种基本运算，并在此基础上设计一个主程序完成如下功能：（1） 输出二叉树b;（2） 输出H结点的左、右孩子结点值；（3） 输出二叉树b的深度；（4） 输出二叉树b的宽度；（5） 输出二叉树b的结点个数；（6） 输出二叉树b的叶子结点个数。2编写一程序，实现二叉树的先序遍历、中序遍历和后序遍历的各种递归和非递归算法，以及层次遍历的算法。三、实验预习内容二叉树存储结构，二叉树基本运算（创建二叉树、寻找结点、找孩子结点、求高度、输出二叉树）三、实验结果与分析 7-1#include #include #define 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;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) case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;BTNode *FindNode(BTNode *b,ElemType x)BTNode *p;if (b=NULL) return NULL;else if (b-data=x) return b;elsep=FindNode(b-lchild,x);if (p!=NULL) return p;else return FindNode(b-rchild,x);BTNode *LchildNode(BTNode *p) return p-lchild;BTNode *RchildNode(BTNode *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 (lchilddeprchilddep)? (lchilddep+1):(rchilddep+1); void DispBTNode(BTNode *b)if (b!=NULL)printf(%c,b-data);if (b-lchild!=NULL | b-rchild!=NULL)printf();DispBTNode(b-lchild);if (b-rchild!=NULL) printf(,);DispBTNode(b-rchild);printf();int BTWidth(BTNode *b)struct int lno;BTNode *p; QuMaxSize;int front,rear;int lnum,max,i,n;front=rear=0; if (b!=NULL) rear+;Qurear.p=b;Qurear.lno=1;while (rear!=front)front+;b=Qufront.p;lnum=Qufront.lno;if (b-lchild!=NULL)rear+;Qurear.p=b-lchild;Qurear.lno=lnum+1;if (b-rchild!=NULL)rear+;Qurear.p=b-rchild;Qurear.lno=lnum+1;max=0;lnum=1;i=1;while (i=rear)n=0;while (imax) max=n;return max;elsereturn 0;int Nodes(BTNode *b)int num1,num2; if (b=NULL) return 0; else if (b-lchild=NULL & b-rchild=NULL) return 1; else num1=Nodes(b-lchild); num2=Nodes(b-rchild); return (num1+num2+1);int LeafNodes(BTNode *b)int num1,num2; if (b=NULL) return 0; else if (b-lchild=NULL & b-rchild=NULL) return 1; else num1=LeafNodes(b-lchild); num2=LeafNodes(b-rchild); return (num1+num2);void main()BTNode *b,*p,*lp,*rp;CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I); printf(输出二叉树:);DispBTNode(b);printf(n);printf(H结点:);p=FindNode(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-data);elseprintf(无右孩子 );printf(n);printf(二叉树b的深度:%dn,BTNodeDepth(b);printf(二叉树b的宽度:%dn,BTWidth(b);printf(二叉树b的结点个数:%dn,Nodes(b);printf(二叉树b的叶子结点个数:%dn,LeafNodes(b);7-2#include #include #define 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;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) case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;void DispBTNode(BTNode *b)if (b!=NULL)printf(%c,b-data);if (b-lchild!=NULL | b-rchild!=NULL)printf();DispBTNode(b-lchild);if (b-rchild!=NULL) printf(,);DispBTNode(b-rchild);printf();void PreOrder(BTNode *b)if (b!=NULL) printf(%c ,b-data);PreOrder(b-lchild);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-; printf(%c ,p-data); if (p-rchild!=NULL) top+; Sttop=p-rchild; if (p-lchild!=NULL) top+; Sttop=p-lchild;printf(n);void InOrder(BTNode *b)if (b!=NULL) InOrder(b-lchild);printf(%c ,b-data);InOrder(b-rchild);void InOrder1(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-;printf(%c ,p-data);p=p-rchild;printf(n);void PostOrder(BTNode *b)if (b!=NULL) PostOrder(b-lchild);PostOrder(b-rchild);printf(%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=NULL;flag=1;while (top!=-1 & flag)b=Sttop;if (b-rchild=p)printf(%c ,b-data);top-;p=b;elseb=b-rchild;flag=0; while (top!=-1);printf(n); void LevelOrder(BTNode *b) BTNode *p; BTNode *quMaxSize;int front,rear;front=rear=-1;rear+;qurear=b; while (front!=rear) front=(front+1)%MaxSize;p=qufront;printf(%c ,p-data);if (p-lchild!=NULL) rear=(rear+1)%MaxSize;qurear=p-lchild;if (p-rchild!=NULL) rear=(rear+1)%MaxSize;qurear=p-rchild; void main()BTNode *b;CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I); printf(二叉树b:);DispBTNode(b);printf(n);printf(先序遍历序列:n);printf(递归算法:);PreO