二叉树的操作.pdf
二叉树操作实验日志
实验题目：
二叉树操作
实验目的：
掌握二叉树的定义、性质及存储方式，各种遍历算法。
实验要求：
采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操
作，求所有叶子及结点总数的操作。
实验主要步骤：
1、分析、理解程序
程序的功能是采用二叉树链表存储结构，完成二叉树的建立，先序、中序和
后序以及按层次遍历的操作。
如输入二叉树ABD###CE##F##，链表示意图如下：
A
BC
DEF
2、添加中序和后序遍历算法
//========LNR中序遍历===============
voidInorder(BinTreeT)
{
if(T){
Inorder(T-lchild);
printf(%c,T-data);
Inorder(T-rchild);
}
}
//==========LRN后序遍============
voidPostorder(BinTreeT)
{
if(T){
Postorder(T-lchild);
Postorder(T-rchild);
printf(%c,T-data);
}
}
3、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空
指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍
历序列，求所有叶子及结点总数。
四、源程序代码
#includestdio.h
#includestring.h
#includestdlib.h
#defineMax20//结点的最大个数
typedefstructnode{
chardata;
structnode*lchild,*rchild;
}BinTNode;//自定义二叉树的结点类型
typedefBinTNode*BinTree;//定义二叉树的指针
intNodeNum,leaf;//NodeNum为结点数，lea为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点#以示空指针的位置==========
BinTreeCreatBinTree(void)
{
BinTreeT;
charch;
if((ch=getchar())==#)
return(NULL);//读入#，返回空指针
else{
T=(BinTNode*)malloc(sizeof(BinTNode));//生成结点
T-data=ch;
T-lchild=CreatBinTree();//构造左子树
T-rchild=CreatBinTree();//构造右子树
return(T);
}
}
//========NLR先序遍=============
voidPreorder(BinTreeT)
{
if(T){
printf(%c,T-data);//访问结点
Preorder(T-lchild);//先序遍历左子树
Preorder(T-rchild);//先序遍历右子树