数据结构二叉树操作实验报告

时间：2026-01-20

实验报告

指导教师 XX 实验时间：2010年11月1日学院计算机学院专业信息安全

班级 XXXXXX 学号 XXXXX 姓名 XX 实验室 S331

实验题目：二叉树操作

实验要求：

采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

示例程序：

#include"stdio.h"

#include"string.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(); //构造右子树 return(T);

}

//========NLR 先序遍历=============

void Preorder(BinTree T)

{

if(T) {

printf("%c",T->data); //访问结点

Preorder(T->lchild); //先序遍历左子树

Preorder(T->rchild); //先序遍历右子树

}

//========LNR 中序遍历===============

//==========LRN 后序遍历============

//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法======== int TreeDepth(BinTree T)

{

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; //右子树入队

}

//==========主函数=================

void main()

{

BinTree root;

int i,depth;

printf("\n");

printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列， // 用#代表虚结点，如ABD###CE##F##

root=CreatBinTree(); //创建二叉树，返回根结点

do { //从菜单中选择遍历方式，输入序号。

printf("\t********** select ************\n");

printf("\t1: Preorder Traversal\n"); printf("\t2: Iorder Traversal\n"); printf("\t3: Postorder traversal\n"); printf("\t4: PostTreeDepth,Node number,Leaf number\n"); printf("\t5: Level Depth\n"); //按层次遍历之前，先选择4，求出该树的结点数。 printf("\t0: Exit\n"); printf("\t*******************************\n"); scanf("%d",&i); //输入菜单序号（0-5） switch (i){ case 1: printf("Print Bin_tree Preorder: ");

} Preorder(root); //先序遍历 break; case 2: printf("Print Bin_Tree Inorder: "); Inorder(root); //中序遍历 break; case 3: printf("Print Bin_Tree Postorder: "); Postorder(root); //后序遍历 break; case 4: depth=TreeDepth(root); //求树的深度及叶子数 printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum); printf(" BinTree Leaf number=%d",leaf); break; case 5: printf("LevePrint Bin_Tree: "); Levelorder(root); //按层次遍历 break; default: exit(1);

printf("\n");

} while(i!=0);

}

实验内容及步骤：

1、分析、理解程序。

2、添加中序和后序遍历算法.

3、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），

如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。

4、画出所设计的二叉树，以后序遍历算法为例，画出执行踪迹示意图。给出实验结果。

5、给出实验结果。

改正后的完整程序：

#include"stdio.h"