实验二二叉树的操作
一、实验目的
1、熟悉二叉树结点的结构和对二叉树的基本操作；
2、掌握对二叉树每一种操作的具体实现；
3、学会递归方法和非递归方法实现二叉树的运算某重操作。

二、实验要求
1．认真阅读理解每一种操作算法。

2．编写主程序文件，建立二叉树、遍历二叉树（三种方法之一）。

3．写出自己运行的结果。

画出自己建立的二叉树，给出输入序列、输出结果。

二、实验内容
（1）通过键盘输入的扩充二叉树的层次遍历序列, 建立二叉树(序列:2,5,6,0,0,10,11,0,0,0,0 )。

（设二叉树结点的数据为int型，其中扩充结点用'0'号表示。

）
然后按中序和后序输出此二叉树，(附加:求该树的叶结点个数和度数为2的结点个数。

) 分析程序中变量r1,r2,q的作用？
（2）画出自己的一颗二叉树，给出输入序列；把中序或后序的遍历算法改为非递归算法；给出遍历序列。

三，实验结果
1. 程序实现:
#include"stdio.h"
#include"malloc.h"
typedef struct treenode
{int data;
struct treenode *lchild,*rchild;
}TREENODE,*TREENODEPTR;
#define N 50
void creattree(TREENODEPTR * root)
{int value,r1,r2;
TREENODEPTR t ,q[N];
scanf("%d",&value);
if (value)
{*root=( TREENODEPTR)malloc(sizeof(TREENODEPTR));
(*root)->data=value;
r2=r1=1;
q[r1]=*root;
}
else
{printf("input error\n");return;}
while(r2<=r1)
{t=q[r2];r2++;
scanf("%d",&value);
if (value==0)
t->lchild=NULL;
else
{t->lchild=( TREENODEPTR)malloc(sizeof(TREENODEPTR));
t->lchild->data=value;
r1++;q[r1]=t->lchild;
}
scanf("%d",&value);
if (value==0)
t->rchild=NULL;
else
{ t->rchild=( TREENODEPTR)malloc(sizeof(TREENODEPTR));
t->rchild->data=value;
r1++;q[r1]=t->rchild;
}
}
}
/*非递归中序遍历二叉树*/
void InOrder(TREENODEPTR root)
{
TREENODEPTR q[N];
int top=0;
TREENODEPTR p;
p=root;
do{
while(p!=NULL)
{
if(top>N)
return;
top=top+1;
q[top]=p;
p=p->lchild;
};
if(top!=0)
{
p=q[top];
top=top-1;
printf("%3d",p->data);
p=p->rchild;
}
}while(p!=NULL||top!=0);
}
/*非递归后序遍历二叉树*/
void PostOrder(TREENODEPTR root) {
TREENODEPTR p,r,q[N] ;
int top=0;
r=NULL;
p=root;
while(p!=NULL||top!=0)
{
while(p!=NULL)
{top++;
if(top>=N)
return;
q[top]=p;p=p->lchild;
}
if(top>0)
{p=q[top];
if((p->rchild==NULL)||(p->rchild==r)) {printf("%3d",p->data);
r=p;
top--;
p=NULL;
}
else
p=p->rchild;
}
}
}
main()
{TREENODEPTR root;
root=NULL;
printf("输入的扩充二叉树的层次遍历序列为:\n");
creattree(&root);
printf("非递归中序遍历二叉树:\n");
InOrder(root);
printf("\n");
printf("非递归后序遍历二叉树:\n");
PostOrder(root);
printf("\n");
}
3.变量r1的作用是：栈尾
变量r2的作用是：栈头
变量q 的作用是：设置一个栈，用以保留结点指针。

4.二叉树图形如下所示
1
3
2
10
7
5
11
15。