数据结构的课件实验五二叉树的存储结构和基本操作

实验五 二叉树的存储表示和基本操作实验内容 1. 二叉树的二叉链表的存储结构 二叉树的二叉链表存储表示typedef struct nodeElemType data; /*数据元素*/struct node *lchild; /*指向左孩子*/struct node *rchild; /*指向右孩子*/ BTNode;2. 二叉树的基本操作 （1）创建操作：创建一棵二叉树。（2）查找操作：查找二叉树中值为x的结点。（3）查找左孩子操作：查找二叉树中值为x的结点的左孩子。（4）查找右孩子操作：查找二叉树中值为x的结点的右孩子。（5）求深度操作：求二叉树的深度。（6）求宽度操作：求二叉树的宽度。（7）求结点个数操作：求二叉树的结点个数。（8）求叶子结点个数操作：求二叉树的叶子结点个数。（9）输出操作：以括号表示法输出二叉树。3. 链式队列操作实现的步骤（1）实现将链式队列的存储结构和基本操作程序代码。（2）实现main主函数。4.程序代码完整清单#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 *FindNode(BTNode *b,ElemType x); /*查找二叉树的结点*/ BTNode *LchildNode(BTNode *p); /*查找二叉树结点的左孩子*/ BTNode *RchildNode(BTNode *p); /*查找二叉树结点的右孩子*/ int BTNodeDepth(BTNode *b); /*求二叉树的深度*/ void DispBTNode(BTNode *b); /*输出二叉树*/ int BTWidth(BTNode *b); /*求二叉树的宽度*/ int Nodes(BTNode *b); /*求二叉树结点个数*/ int LeafNodes(BTNode *b); /*求二叉树叶子结点个数*/void main()BTNode *b,*p,*lp,*rp;CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I); printf(n);printf(1)输出二叉树:);DispBTNode(b);printf(n);printf(2)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(3)二叉树b的深度:%dn,BTNodeDepth(b);printf(4)二叉树b的宽度:%dn,BTWidth(b);printf(5)二叉树b的结点个数:%dn,Nodes(b);printf(6)二叉树b的叶子结点个数:%dn,LeafNodes(b);printf(n);void CreateBTNode(BTNode *&b,char *str)/*由str串创建二叉链*/BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/*建立的二叉树初始时为空*/ch=strj;while (ch!=0)/*str未扫描完时循环*/ 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) /*p指向二叉树的根结点*/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)/*查找二叉树的结点 操作结果：返回data*/ /* 域为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)/*查找二叉树结点的左孩子 操作结果：返回*p*/ /*结点的左孩子结点指针*/ return p-lchild;BTNode *RchildNode(BTNode *p)/*查找二叉树结点的右孩子 操作结果：返回*p结*/ /*点的右孩子结点指针*/ return p-rchild;int BTNodeDepth(BTNode *b)/*求二叉树b的深度*/ int lchilddep,rchilddep; if (b=NULL) return(0); /*空树的高度为0*/ else lchilddep=BTNodeDepth(b-lchild);/*求左子树的高度为lchilddep*/ rchilddep=BTNodeDepth(b-rchild);/*求右子树的高度为rchilddep*/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) /*求二叉树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;/*根结点的层次编号为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)/*求二叉树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)/*求二叉树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(