二叉树基本操作--实验报告材料

1、标准实验三二叉树的基本操作学院：物理与电子学院班级：电信1105班姓名：刘岩学号：1404110729文案一、实验目的1、熟悉二叉树的基本操作，掌握二叉树的实现以及实际应用。3、加深对于二叉树的理解，逐步培养解决实际问题的编程能力。二、实验环境1 台 WINDOWS 环境的 PC 机，装有 Visual C+ 6.0。三、实验内容1、问题描述现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括：1创建二叉树CreateBTNode(*b,*str):根据二叉树括号表示法的字符串*str生成对应的链式存储结构。2 输出二叉树 DispBTNode(*b

2、):以括号表示法输出一棵二叉树。3查找结点FindNode(*b,x):在二叉树b中寻找data域值为x的结点，并返回指向该结点 的指针。4求高度BTNodeDepth(*b):求二叉树b的高度。若二叉树为空，则其高度为0;否则淇 高度等于左子树与右子树中的最大高度加l。5求二叉树的结点个数NodesCount(BTNode *b)6先序遍历的递归算法：void PreOrder(BTNode *b)7中序遍历的递归算法：void InOrder(BTNode *b)8 后序遍历递归算法：void PostOrder(BTNode *b)9 层次遍历算法 void LevelOrder(BTN

3、ode *b) 2、基本要求实现以上9个函数。主函数中实现以下功能：创建下图中的树b输出二叉树b找到'H'节点，输出其左右孩子值输出b的高度输出b的节点个数输出b的四种遍历顺序3、程序编写上图转化为二叉树括号表示法为/*数据元素*/*指向左孩子*/*指向右孩子*/A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)程序：#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;str

4、uct node *lchild;struct node *rchild; BTNode;void CreateBTNode(BTNode *&b,char *str);/ 创建 BTNode *FindNode(BTNode *b,ElemType x);/ 查找节点 int BTNodeHeight(BTNode *b);/ 求高度void DispBTNode(BTNode *b);/ 输出int NodesCount(BTNode *b);/ 二叉树的结点个数void PreOrder(BTNode *b);/ 先序遍历递归void InOrder(BTNode *b);/ 中

5、序遍历递归void PostOrder(BTNode *b);/ 后序遍历递归void LevelOrder(BTNode *b);/ 层次遍历创建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 '

6、;,':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)printf("%c",b->data);if(b->lchild!=

7、NULL|b->rchild!=NULL) printf("(");DispBTNode(b->lchild);if(b->rchild!=NULL)printf(",");DispBTNode(b->rchild); printf(")");查找节点BTNode *FindNode(BTNode *b,ElemType x)BTNode *p;if(b=NULL)return b;else if(b->data=x)return b;elsep=FindNode(b->lchild,x);if(p

8、!=NULL)return p;elsereturn FindNode(b->rchild,x);求高度int BTNodeHeight(BTNode *b)int lchildh,rchildh;if(b=NULL)return (0);elselchildh=BTNodeHeight(b->lchild);rchildh=BTNodeHeight(b->rchild);return(lchildh>rchildh)?(lchildh+1):(rchildh+1);二叉树的结点个数int NodesCount(BTNode *b)if(b=NULL)return 0;

9、elsereturn NodesCount(b->lchild)+NodesCount(b->rchild)+1; 先序遍历递归void PreOrder(BTNode *b)if(b!=NULL)printf("%c",b->data);PreOrder(b->lchild);PreOrder(b->rchild);中序遍历递归void InOrder(BTNode *b)if(b!=NULL)InOrder(b->lchild);printf("%c",b->data);InOrder(b->rchil

10、d);后序遍历递归void PostOrder(BTNode *b)if(b!=NULL)PostOrder(b->lchild);PostOrder(b->rchild);printf("%c",b->data);/层次遍历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&qu

11、ot;,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,*p,*lp,*rp;char str尸"A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)"根据树形图改写成的二叉树括号表示法的字符串*str/char str100;scanf("%s",&str); 自行

12、输入括号表示的二叉树CreateBTNode(b,str); 创建树 b printf("n");printf("输出二叉树：”);输出二叉树bDispBTNode(b);printf("n");printf("'H'结点：");/找到'H'节点，输出其左右孩子值 p=FindNode(b,'H');printf("n");if (p!=NULL)printf("左孩子节点的值");printf("%c",p->

13、lchild->data);printf("n");printf("右孩子节点的值");printf("%c",p->rchild->data);printf("n");此处输出p的左右孩子节点的值 printf("n");printf("二叉树 b 的深度:%dn",BTNodeHeight(b); 输出 b 的高度 printf("二叉树b的结点个数：dn",NodesCount(b);/输出b的节点个数 printf("n

14、");printf("先序遍历序列：n");输出b的四种遍历顺序printf("算法:");PreOrder(b);printf("n");printf("中序遍历序列：n");printf("算法:");InOrder(b);printf("n");printf("后序遍历序列：n");printf("算法:");PostOrder(b);printf("n");printf("层次遍历序列：n");printf("算法:");LevelOrder(b); printf("n");四、实验心得与小结通过本次实验