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

假设二叉树采用二叉链存储结构存储，分别实现以下算法，并在程序中完成测试： （1）计算二叉树节点个数； （2）输出所有叶子节点； （3）求二叉树 b 的叶子节点个数； （4）求二叉树 b 的宽度 #include stdio.h #include malloc.h #define MaxSize 100 typedef char ElemType ; typedef struct node { ElemType data; //数据元素 struct node *lchild; //指向左孩子 struct node *rchild; //指向右孩子 } BTNode ; void CreateBTNode(BTNode *b,char *str); //由str串创建二叉链 BTNode *FindNode(BTNode *b,ElemType x); //返回data域为x的节点指针 BTNode *LchildNode(BTNode *p); //返回*p节点的左孩子节点指针 BTNode *RchildNode(BTNode *p); //返回*p节点的右孩子节点指针 int BTNodeDepth(BTNode *b); //求二叉树b的深度 void DispBTNode(BTNode *b); //以括号表示法输出二叉树 void DestroyBTNode(BTNode *b); //销毁二叉树 void LevelOrder(BTNode *b) { 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 CreateBTNode(BTNode *b,char *str) //由str串创建二叉链 { BTNode *St[MaxSize],*p=NULL ; int top=-1,k,j=0; char ch; b=NULL ; //建立的二叉树初始时为空 ch=str[j]; while (ch!=\0) //str未扫描完时循环 { switch(ch) { case (: top++; St[top]=p; k=1; break ; //为左节点 case ): top--; break ; case ,: k=2; break ; //为右节点 default: p=(BTNode *