//二叉树的结点个数 int NodesCount(BTNode *b){
if(b==NULL) return 0;
else return NodesCount(b->lchild)+NodesCount(b->rchild)+1;
}
//先序遍历递归 void PreOrder(BTNode *b){
switch(ch){ case '(':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)
BTNode *p; BTNode *qu[MaxSize]; int front,rear; front=rear=-1; rear++; qu[rear]=b; while(front!=rear){
front=(front+1)%MaxSize; p=qu[front]; printf("%c",p->data); if(p->lchild!=NULL){
rear=(rear+1)%MaxSize; qu[rear]=p->lchild; } if(p->rchild!=NULL){ rear=(rear+1)%MaxSize; qu[rear]=p->rchild; } } }
void main()
第5页共7页
{ BTNode *b,*p,*lp,*rp; char str[]="A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";//根据树形图改写成的 //二叉树括号表示法的字符串*str
五、指导教师评议
成绩评定：
指导教师签名：
第7页共7页
实验报告
一、实验目的
1、熟悉二叉树树的基本操作。 2、掌握二叉树的实现以及实际应用。 3、加深二叉树的理解，逐步培养解决实际问题的编程能力。
二、实验环境
1 台 WINDOWS 环境的 PC 机，装有 Visual C++ 6.0。
三、实验内容
【问题描述】 现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。
if(b!=NULL){ printf("%c",b->data); PreOrder(b->lchild); PreOrder(b->rchild);
第4页共7页
} }
//中序遍历递归 void InOrder(BTNode *b){
if(b!=NULL){ InOrder(b->lchild); printf("%c",b->data); InOrder(b->rchild);
第2页共7页
void LevelOrder(BTNode *b);//层次遍历
//创建 void CreateBTNode(BTNode *&b,char *str){
BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch; b=NULL; ch=str[j]; while(ch!='\0'){
/*数据元素*/ /*指向左孩子*/ /*指向右孩子*/
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);//中序遍历递归 void PostOrder(BTNode *b);//后序遍历递归
//char str[100];scanf("%s",&str);//自行输入括号表示的二叉树
CreateBTNode(b,str); //创建树 b printf("\n");
printf("输出二叉树:");//输出二叉树 b DispBTNode(b); printf("\n");
printf("'H'结点:");//找到'H'节点，输出其左右孩子值 p=FindNode(b,'H'); printf("\n"); if (p!=NULL){
return p; else
return FindNode(b->rchild,x); } }
//求高度 int BTNodeHeight(BTNode *b){
int lchildh,rchildh; if(b==NULL)
return (0); else{
lchildh=BTNodeHeight(b->lchild); rchildh=BTNodeHeight(b->rchild); return(lchildh>rchildh)?(lchildh+1):(rchildh+1); } }
b=p; else{
switch(k){ case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++; ch=str[j]; } }
//输出 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 PostOrder(BTNode *b){
if(b!=NULL){ PostOrder(b->lchild); PostOrder(b->rchild); printf("%c",b->data);
} }
//层次遍历 void LevelOrder(BTNode *b){
C(F,G(,I)))
程序: #include <stdio.h> #include <malloc.h> #define MaxSize 100 typedef char ElemType;
typedef struct node {
ElemType data; struct node *lchild; struct node *rchild; } BTNode;
} }
第3页共7页
//查找节点 BTNode *FindNode(BTNode *b,ElemType x){
BTNode *p; if(b==NULL)
return b; else if(b->data==x)
return b; else{
p=FindNode(b->lchild,x); if(p!=NULL)
其中操作函数包括： 1> 创建二叉树 CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str 生成对应的链 式存储结构。 2> 输出二叉树 DispBTNode(*b)：以括号表示法输出一棵二叉树。 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(BTNode *b)
printf("左孩子节点的值"); printf("%c",p->lchild->data);printf("\n"); printf("右孩子节点的值"); printf("%c",p->rchild->data);printf("\n"); //此处输出 p 的左右孩子节点的值 } printf("\n");
第6页共7页
四、实验心得与小结
通过实验，我熟悉二叉树树的基本操作，掌握二叉树的实现以及实际应用。 加深了对二叉树的理解，逐步培养解决实际问题的编程能力以及进一步了解了二 叉树图转化为括号表示法。递归的使用，要注意，初始时的状态以及如何使用递 归，注意普遍性，思考时从普通的开始。通过这次上机操作，让我明白书本上的 程序一定要自己去调试，这样才能将书本程序与老师讲的内容融会贯通，达到温 故而知新。