二叉树实验报告

山东工商学院

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

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### 运行结果：