数据结构实验之二叉树实验基础

二叉树实验基础

一、实验目的

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

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

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

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

二、实验预习

说明以下概念

1、二叉树：二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 [1] 。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 [1] 。

2、递归遍历：递归一般是在函数里面把函数自己给调用一遍，通过每次调用改变条件，来结束循环。递归在数据格式一致，在数据层级未知的情况下，比普通的遍历更有优势。

3、非递归遍历： 前序遍历是指按照根左右的顺序依次遍历,使用非递归遍历,一般会用到栈,利用先进后出的特性来达到访问二叉树节点目的。

4、层序遍历： 就是将一颗树按照每一层每一层的方式进行遍历

三、实验内容和要求

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

#include<stdio.h>

#include<malloc.h>

#define MAX 20

typedef struct BTNode{

/*节点结构声明*/

char data ;

/*节点数据*/

struct BTNode *lchild;

struct BTNode *rchild ; /*指针*/

}*BiTree;

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

char s;

BiTree q;

printf("\nplease input data:(exit for #)");

s=getche();

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

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

if(q==NULL){printf("Memory alloc failure!"); exit(0);}

q->data=s;

*t=q;

createBiTree(&q->lchild); /*递归建立左子树*/

createBiTree(&q->rchild); /*递归建立右子树*/}

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

if ( p!= NULL ) {

printf("%c", p->data);

PreOrder( p->lchild ) ;

PreOrder( p->rchild) ;

}

}

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

if( p!= NULL ) {

InOrder( p->lchild ) ;

printf("%c", p->data);

InOrder( p->rchild) ;

}

}

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

if ( p!= NULL ) {

PostOrder( p->lchild ) ;

PostOrder( p->rchild) ;

printf("%c", p->data);

}

}

void Preorder_n(BiTree p){ /*先序遍历的非递归算法*/

BiTree stack[MAX],q;

int top=0,i;

for(i=0;i<MAX;i++) stack[i]=NULL;/*初始化栈*/

q=p;

while(q!=NULL){

printf("%c",q->data);

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;

createBiTree(&t);

printf("\n\nPreOrder the tree is:");

PreOrder(t);

printf("\n\nInOrder the tree is:");

InOrder(t);

printf("\n\nPostOrder the tree is:");

PostOrder(t);

printf("\n\n 先序遍历序列（非递归）:");

Preorder_n(t);

release(t);

return 0;

}

l

运行程序

输入：

ABC##DE#G##F###

运行结果：

注：getche()在头文件：<conio.h>中

二叉树形态：

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

算法代码：

int NodeCount(BiTree T){//统计树的总结点数

int nodes;

if(T==NULL)return 0;//如果树为空，则总结点数为0

else{//否则为根结点个数加上根左子树中结点个数，再加上右子树中结点个数

nodes=1+NodeCount(T->lchild)+NodeCount(T->rchild);

return nodes;

}

}

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

算法代码：

int LeafNode(BiTree T){//统计树的叶子结点(度为0)个数

int lnodes;

if(T==NULL)return 0;//如果树为空，则叶子结点数为0

else if(T->lchild==NULL&&T->rchild==NULL)return 1;//如果根节点的左右子树都为空，则叶子结点仅根结点一个

else lnodes=LeafNode(T->lchild)+LeafNode(T->rchild);//当某个结点既有左子树又有右子树时，说明该结点不是叶子结点，因此叶子结点个数等于左子树及右子树中叶子结点数之和

return lnodes;

}

四、实验小结

在求解树中不同度的结点数时，首先要搞清楚主要思想是什么，然后再进行代码的构思。以求解度为2的结点数为例：①如果树为空，则度为2的结点数为0；②如果根节点的左右孩子均为空，树中只有一个结点，且该结点度为0，则度为2的结点为0 ；③如果某一结点的左右子树中有一个为空，则需进一步判断不为空的子树中度为2的结点有多少 ；④当某结点既有左子树又有右子树时，度为2的结点数就等于该结点加上其左右子树中度为2的结点数 。