二叉树实验报告

山东工商学院

《数据结构》实验指导及报告书

2012 / 2013 学年

姓名： 学号： 班级： 指导教师：

Xx学院

2012年11月25日

第 一 学期

实验三 二叉树

一、实验目的

1、掌握二叉树的基本特性

2、掌握二叉树的先序、中序、后序的递归遍历算法 3、理解二叉树的先序、中序、后序的非递归遍历算法

4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉树的基本特性

二、实验预习

说明以下概念

1、二叉树：是另一种树型结构，它的特点是每个结点至多只有两棵子树，并且二叉树有左右之分，其次序不能任意颠倒。 2、递归遍历：

1、 非递归遍历：

4、层序遍历：

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的形态。 #include #include

#define MAX 20

typedef struct BTNode{ /*节点结构声明*/

char data ; /*节点数据*/ struct BTNode *lchild;

struct BTNode *rchild ; /*指针*/ }*BiTree;

BiTree createBiTree(BiTree t){ /* 先序遍历创建二叉树*/ char s;

printf(\s=getche();

if(s=='#'){t=NULL; return t;}

t=(BiTree)malloc(sizeof(struct BTNode));

if(t==NULL){printf(\ t->data=s;

t->lchild=createBiTree(t->lchild); /*递归建立左子树*/ t->rchild=createBiTree(t->rchild); /*递归建立右子树*/ return t; }

void PreOrder(BiTree p){ /* 先序遍历二叉树*/ if ( p!= NULL ) {

printf(\ PreOrder( p->lchild ) ; PreOrder( p->rchild) ; } }

void InOrder(BiTree p){ /* 中序遍历二叉树*/ if( p!= NULL ) {

InOrder( p->lchild ) ; printf(\ InOrder( p->rchild) ; } }

void PostOrder(BiTree p){ /* 后序遍历二叉树*/ if ( p!= NULL ) {

PostOrder( p->lchild ) ; PostOrder( p->rchild) ; printf(\ } }

void Preorder_n(BiTree p){ /*先序遍历的非递归算法*/ BiTree stack[MAX],q; int top=0,i;

for(i=0;i

while(q!=NULL){

printf(\

if(q->rchild!=NULL) stack[top++]=q->rchild; if(q->lchild!=NULL) q=q->lchild; else

if(top>0) q=stack[--top]; else q=NULL; } }

void release(BiTree t){ /*释放二叉树空间*/ if(t!=NULL){

release(t->lchild); release(t->rchild);

free(t); } }

int main(){

BiTree t=NULL; int e,m,g;

t=createBiTree(t);

printf(\ PreOrder(t);

printf(\ InOrder(t);

printf(\ PostOrder(t);

printf(\先序遍历序列（非递归）:\

Preorder_n(t);

printf(\输出结点总数:\e=PreOrder_num(t); printf(\

printf(\输出树的深度:\m=BTNodeDepth(t); printf(\

printf(\输出树叶子总数:\g=LeafNodes(t); printf(\ release(t); return 0; }

?

运行程序

输入：

ABC##DE#G##F### 运行结果：

画出该二叉树的形态：

2、在上题中补充求二叉树中求结点总数算法（提示：可在某种遍历过程中统计遍历的结点数），并在主函数中补充相应的调用验证正确性。 算法代码：

int PreOrder_num(BiTree p){ int j=0;

BiTree stack[MAX],q; int top=0,i;

for(i=0;i

q=p;

while(q!=NULL){ j++;0

if(q->rchild!=NULL) stack[top++]=q->rchild; if(q->lchild!=NULL) q=q->lchild; else

if(top>0) q=stack[--top]; else q=NULL; } }

return j;

3、在上题中补充求二叉树中求叶子结点总数算法（提示：可在某种遍历过程中统计遍历的叶子结点数），并在主函数中补充相应的调用验证正确性。 算法代码：

int LeafNodes(BiTree p){

int num1,num2; if(p==NULL)

return 0;

else if(p->lchild==NULL&&p->rchild==NULL) return 1; else {

num1=LeafNodes(p->lchild); num2=LeafNodes(p->rchild); return (num1+num2);

}

}

4、在上题中补充求二叉树深度算法，并在主函数中补充相应的调用验证正确性。 算法代码：

int BTNodeDepth(BiTree p){ int lchilddep,rchilddep;

if(p==NULL) return 0;

else{

lchilddep=BTNodeDepth(p->lchild); rchilddep=BTNodeDepth(p->rchild); }

return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1); }

选做实验：（代码可另附纸） 2、 补充二叉树层次遍历算法。（提示：利用队列实现）

3、 补充二叉树中序、后序非递归算法。

四、实验小结

五、教师评语

本文来源：https://www.bwwdw.com/article/d0mv.html