实验五 二叉树

一、实验目的

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

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

4、通过二叉树的深度和层次遍历算法，理解二叉树的基本特性

二、实验内容和要求

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

typedef struct BTNode{ /*节点结构声明*/ char data ; /*节点数据*/ struct BTNode *lchild;

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

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

printf(\ s=getche();

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

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

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

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

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; createBiTree(&t);

printf(\ PreOrder(t);

printf(\ InOrder(t);

printf(\

PostOrder(t);

printf(\先序遍历序列（非递归）:\ Preorder_n(t); release(t); return 0; }

运行程序 输入：

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

?

运行结果：

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

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

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

选做实验：（代码可另附纸） 5、补充二叉树层次遍历算法。（提示：利用队列实现） 6、补充二叉树中序、后序非递归算法。

三、实验小结

四、教师评语