《数据结构》实验报告
班级：
学号：
姓名：
实验四二叉树的基本操作实验环境：Visual C++
实验目的：
1、掌握二叉树的二叉链式存储结构；
2、掌握二叉树的建立，遍历等操作。
实验内容：
通过完全前序序列创建一棵二叉树，完成如下功能：
1)输出二叉树的前序遍历序列；
2)输出二叉树的中序遍历序列；
3)输出二叉树的后序遍历序列；
4)统计二叉树的结点总数；
5)统计二叉树中叶子结点的个数；
实验提示：
//二叉树的二叉链式存储表示
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
一、程序源代码
#include
#include
#define MAXSIZE 30
typedef char ElemType;
typedef struct TNode *BiTree;
struct TNode {
char data;
BiTree lchild;
BiTree rchild;
};
int IsEmpty_BiTree(BiTree *T) { if(*T == NULL)
return 1;
else
return 0;
}
void Create_BiTree(BiTree *T){
char ch;
ch = getchar();
//当输入的是"#"时，认为该子树为空
if(ch == '#')
*T = NULL;
//创建树结点
else{
*T = (BiTree)malloc(sizeof(struct TNode)); (*T)->data = ch; //生成树结点
//生成左子树
Create_BiTree(&(*T)->lchild);
//生成右子树
Create_BiTree(&(*T)->rchild);
}
}
void TraverseBiTree(BiTree T) { //先序遍历
if(T == NULL)
return;
else {
printf("%c ",T->data);
TraverseBiTree(T->lchild);
TraverseBiTree(T->rchild);
}
}
void InOrderBiTree(BiTree T) { //中序遍历if(NULL == T)
return;
else {
InOrderBiTree(T->lchild);
printf("%c ",T->data);
InOrderBiTree(T->rchild);
}
}
void PostOrderBiTree(BiTree T) {
if(NULL == T)
return;
else {
InOrderBiTree(T->lchild);
InOrderBiTree(T->rchild);
printf("%c ",T->data);
}
}
int TreeDeep(BiTree T) {
int deep = 0;
if(T)
{
int leftdeep = TreeDeep(T->lchild);
int rightdeep = TreeDeep(T->rchild);
deep = leftdeep+1 > rightdeep+1 ? leftdeep+1 : rightdeep+1;
}
return deep;
}
int Leafcount(BiTree T, int &num) {
if(T)
{
if(T->lchild ==NULL && T->rchild==NULL)
{
num++;
printf("%c ",T->data);
}
Leafcount(T->lchild,num);
Leafcount(T->rchild,num);
}
return num;
}
void LevelOrder_BiTree(BiTree T){
//用一个队列保存结点信息,这里的队列采用的是顺序队列中的数组实现 int front = 0;
int rear = 0;
BiTree BiQueue[MAXSIZE];
BiTree tempNode;
if(!IsEmpty_BiTree(&T)){
BiQueue[rear++] = T;
while(front != rear){
//取出队头元素，并使队头指针向后移动一位
tempNode = BiQueue[front++];
//判断左右子树是否为空,若为空，则加入队列 if(!IsEmpty_BiTree(&(tempNode->lchild))) BiQueue[rear++] = tempNode->lchild;
if(!IsEmpty_BiTree(&(tempNode->rchild))) BiQueue[rear++] = tempNode->rchild;
printf("%c ",tempNode->data);
}
}
}
int main(void)
{
BiTree T;
BiTree *p = (BiTree*)malloc(sizeof(BiTree));
int deepth,num=0 ;
Create_BiTree(&T);
printf("先序遍历二叉树:\n");
TraverseBiTree(T);
printf("\n");
printf("中序遍历二叉树:\n");
InOrderBiTree(T);
printf("\n");
printf("后序遍历二叉树:\n");
PostOrderBiTree(T);
printf("\n层次遍历结果：");
LevelOrder_BiTree(T);
printf("\n");
deepth=TreeDeep(T);
printf("树的深度为:%d",deepth);
printf("\n");
printf("树的叶子结点为:");
Leafcount(T,num);
printf("\\n树的叶子结点个数为:%d",num);
return 0;
}
二、运行结果(截图)
三、遇到的问题总结
通过死循环的部分可以看出，在判断时是不能进入结点为空的语句中的，于是从树的构建中寻找问题，最终发现这一条语句存在着问题：
这里给T赋值为空，也就是给整个结构体地址赋值为空，但是我们的目的是给该结构体中的内容，即左孩子的地址指向的内容赋为空