假设二叉树采用二叉链存储结构存储

《假设二叉树采用二叉链存储结构存储》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、假设二叉树采用二叉链存储结构存储，分别实现以下算法，并在程序中完成测试： （1）计算二叉树节点个数；（2）输出所有叶子节点； （3）求二叉树b的叶子节点个数；（4）求二叉树b的宽度 #include#include#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;//数据元素structnode*lchild;//指向左孩子structnode*rchild;//指向右孩子}BTNode;voidCreateBTNode(BTNode*&b,char*

2、str);//由str串创建二叉链BTNode*FindNode(BTNode*b,ElemTypex);//返回data域为x的节点指针BTNode*LchildNode(BTNode*p);//返回*p节点的左孩子节点指针BTNode*RchildNode(BTNode*p);//返回*p节点的右孩子节点指针intBTNodeDepth(BTNode*b);//求二叉树b的深度voidDispBTNode(BTNode*b);//以括号表示法输出二叉树voidDestroyBTNode(BTNode*&b);//销毁二叉树voidLevelOrder(BTNode*b)

3、{BTNode*p;BTNode*qu[MaxSize];//定义环形队列,存放节点指针intfront,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;}

4、if(p->rchild!=NULL)//有右孩子时将其进队{rear=(rear+1)%MaxSize;qu[rear]=p->rchild;}}}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')'

5、: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){case1:St[top]->lchild=p;break;case2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}BTNode*FindNode(BTNode*b,ElemTypex)//返回data

6、域为x的节点指针{BTNode*p;if(b==NULL)returnNULL;elseif(b->data==x)returnb;else{p=FindNode(b->lchild,x);if(p!=NULL)returnp;elsereturnFindNode(b->rchild,x);}}BTNode*LchildNode(BTNode*p)//返回*p节点的左孩子节点指针{returnp->lchild;}BTNode*RchildNode(BTNode*p)//返回*p节点的右孩子节点指针{returnp->rchild;}intBTNodeDepth(BTNod

7、e*b)//求二叉树b的深度{intlchilddep,rchilddep;if(b==NULL)return(0);//空树的高度为0else{lchilddep=BTNodeDepth(b->lchild);//求左子树的高度为lchilddeprchilddep=BTNodeDepth(b->rchild);//求右子树的高度为rchilddepreturn(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);}}voidDispBTNode(BTNode*b)/