二叉树实验基础
一、实验目的
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的结点数 。
