资源描述：
《实验五--二叉树的存储结构和基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实验五二叉树的存储表示和基本操作实验内容1.二叉树的二叉链表的存储结构—————二叉树的二叉链表存储表示————————typedefstructnode{ElemTypedata;/*数据元素*/structnode*lchild;/*指向左孩子*/structnode*rchild;/*指向右孩子*/}BTNode;2.二叉树的基本操作（1）创建操作：创建一棵二叉树。（2）查找操作：查找二叉树中值为x的结点。（3）查找左孩子操作：查找二叉树中值为x的结点的左孩子。（4）查找右孩子操作：查找二叉树中值为x的结点的右孩子。（5）求深度操作：求二叉树的深度。（6）求宽度操作：求二
2、叉树的宽度。（7）求结点个数操作：求二叉树的结点个数。（8）求叶子结点个数操作：求二叉树的叶子结点个数。（9）输出操作：以括号表示法输出二叉树。3.链式队列操作实现的步骤（1）实现将链式队列的存储结构和基本操作程序代码。（2）实现main主函数。4.程序代码完整清单#include#include#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;/*数据元素*/structnode*lchild;/*指向左孩子*/structnode*rchild;/*指
3、向右孩子*/}BTNode;//基本操作函数声明voidCreateBTNode(BTNode*&b,char*str);/*创建一棵二叉树*/BTNode*FindNode(BTNode*b,ElemTypex);/*查找二叉树的结点*/BTNode*LchildNode(BTNode*p);/*查找二叉树结点的左孩子*/BTNode*RchildNode(BTNode*p);/*查找二叉树结点的右孩子*/intBTNodeDepth(BTNode*b);/*求二叉树的深度*/voidDispBTNode(BTNode*b);/*输出二叉树*/intBTWidth(BTNod
4、e*b);/*求二叉树的宽度*/intNodes(BTNode*b);/*求二叉树结点个数*/intLeafNodes(BTNode*b);/*求二叉树叶子结点个数*/voidmain(){BTNode*b,*p,*lp,*rp;;CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");printf("");printf("(1)输出二叉树:");DispBTNode(b);printf("");printf("(2)'H'结点:");p=FindNode(b,'H');if(p!=NULL){lp=LchildN
5、ode(p);if(lp!=NULL)printf("左孩子为%c",lp->data);elseprintf("无左孩子");rp=RchildNode(p);if(rp!=NULL)printf("右孩子为%c",rp->data);elseprintf("无右孩子");}printf("");printf("(3)二叉树b的深度:%d",BTNodeDepth(b));printf("(4)二叉树b的宽度:%d",BTWidth(b));printf("(5)二叉树b的结点个数:%d",Nodes(b));printf("(6)二叉树b的叶子结点个数:%d
6、",LeafNodes(b));printf("");}voidCreateBTNode(BTNode*&b,char*str)/*由str串创建二叉链*/{BTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;b=NULL;/*建立的二叉树初始时为空*/ch=str[j];while(ch!=' ')/*str未扫描完时循环*/{switch(ch){case'(':top++;St[top]=p;k=1;break;/*为左结点*/case')':top--;break;case',':k=2;break;/*为右结点
7、*/default:p=(BTNode*)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL)/*p指向二叉树的根结点*/b=p;else/*已建立二叉树根结点*/{switch(k){case1:St[top]->lchild=p;break;case2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}BTNode*FindNode(BTNode*b,ElemTyp
