二叉树操作 实验日志
指导教师: 黎贵友 实验时间: 2010 年 某 月 某 日 学院 : 计算机科学与技术学院 专业: 计算机科学与技术 班级: 3110903 学号 : 2009214458 姓名: 骆潇龙 实验室: S331-b 实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。
实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。
实验主要步骤：
1、分析、理解程序 #include\"stdio.h\" #include\"string.h\" #include\"stdlib.h\" #include\"ctype.h\" #define Max 20
//结点的最大个数 typedef struct node { char data;
struct node *lchild,*rchild; }BinTNode;
//自定义二叉树的结点类型 typedef BinTNode *BinTree;
//定义二叉树的指针
int NodeNum,leaf;
//NodeNum为结点数，leaf为叶子数
//==========基于先序遍历算法创建二叉树============== //=====要求输入先序序列，其中加入虚结点\"#\"以示空指针的位置===== BinTree CreatBinTree(void) {
BinTree T;
char ch;
if((ch=getchar())==\'#\') return(NULL);
//读入#，返回空指针
else {
T=(BinTNode *)malloc(sizeof(BinTNode));
//生成结点
T->data=ch;
T->lchild=CreatBinTree();
//构造左子树
T->rchild=CreatBinTree();
//构造右子树
- 1
{
int hl,hr,max;
if(T) {
hl=TreeDepth(T->lchild);
//求左深度
hr=TreeDepth(T->rchild);
//求右深度
max=hl>hr? hl:hr;
//取左右深度的最大值
NodeNum=NodeNum+1;
//求结点数
if(hl==0&&hr==0)
leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
} else return(0); }
//====利用\"先进先出\"（FIFO）队列，按层次遍历二叉树========== void Levelorder(BinTree T) {
int front=0,rear=1;
BinTNode *cq[Max],*p;
//定义结点的指针数组cq
cq[1]=T;
//根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front];
//出队
printf(\"%c\",p->data);
//出队，输出结点的值
if(p->lchild!=NULL)
{
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild;
//左子树入队
}
if(p->rchild!=NULL)
{
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild;
//右子树入队
} } }
- 3
default: exit(1);
}
printf(\"\\n\"); } while(i!=0); }
2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数.实验结果：
1.当输入测试数据（输入完全二叉树的先序序列,用#代表虚结点，如ABD###CE##F##）时（如图1-1），回车运行时，结果如图1-2所示；
图1-1
图1-2
2.按层次遍历之前，输入数字4(如图2-1,)；回车运行时，求出测试数据的深度、结点数及叶子数分别为3，6，3（如图2-2）；
图2-1
- 6789 -
