实验五二叉树的存储表示和基本操作
实验内容
1. 二叉树的二叉链表的存储结构
—————二叉树的二叉链表存储表示————————
typedef struct node
{
ElemType 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 <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); /*创建一棵二叉树*/ 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);
else
printf("无左孩子");
rp=RchildNode(p);
if (rp!=NULL)
printf("右孩子为%c",rp->data);
else
printf("无右孩子");
}
printf("\n");
printf("(3)二叉树b的深度:%d\n",BTNodeDepth(b));
printf("(4)二叉树b的宽度:%d\n",BTWidth(b));
printf("(5)二叉树b的结点个数:%d\n",Nodes(b));
printf("(6)二叉树b的叶子结点个数:%d\n",LeafNodes(b));
printf("\n");
}
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)。