试验目的进一步掌握指针变量，动态变量的含义。
掌握二叉树的结构特征，以及各种存储结构的特点及使用范围掌握用指针类型描述，访问二叉树的运算试验内容编写交换以二叉树连表作存储结构的二茬树中所有节点的左右子树的算法。
[基本思想]设二叉树的根指针为t，且以二叉树连表表示，可以利用一个类型为seqstack的指针来实现，且设栈单元包含两个域，一个为data，一个为top，
整个栈容量为maxsize，当树为非空，将当前的树根节点入栈，同时将当前栈顶当作跟节点，然后依据当前的根节点是否具有孩子节点来判断是否将其左右指针交换；在间交换后的左指针或右指针入栈，这样反复进行，直到栈为空
[算法实现]
#define null o
typedef struct node
{
int data;
struct node lchild,rchild;
}bitree;
typedef int datatype ;//栈元素的数据类型
#define maxsize 64 //栈可能达到的最大容量
typedef struct {
datatype data[maxsize];
int top;
}seqstack//顺序栈类型定义
seqstack *s;// 顺序栈类型指针
bitree *creat()//建立二叉树
{
bitree *t;
int x;
scanf(“&x);
if(x==0)
t=null;
else
{
t=malloc(sizeof(bitree));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return t;
}
void inorder(t)//中序遍历二叉树
bitree *t;
{
if(t!=null)
{
inorder(t->lchild);
prinrf(t->data);
inorder(t->rchild);
}
exchange(t)//对二叉树t所有结点左右子树进行交换
bitree *t
{
bitree *p;
seqstack *s;//为一指针栈，类型为seqstack
if(t)
{
s->top=1;
s->data[s->top]=t;//跟指针t进栈
do
{
t=s->data[s->top];//栈顶元素退栈
s->top--;
if((t->lchild!=null)||(t->rchild!=null))
{
p=t->lchild;//节点的左右指针交换
t->lchild=t->rchild;
t->rchild=p;
}
if(t->lchild!=null)//交换后的左孩子指针入栈
{
s->top++;
s->data[s->top]=t->lchild;
}
if(t->rchild!=null)//交换后的右孩子指针入栈
{
s->top++;
s->data[s->top]=t->rchild;
}
}while(s->top==0)/栈空结束
}
}
main()
{
bitree *root;
root=creat();
inorder(root);
exchange(root);
inorder(root);
}
对于exchange算法也可以利用以下的地归算法
void exchange(t)
bitree *t;
{bitree *p;
if(t!=null)
{
p=t->lchild;
t->lchild=t->rchild;
t->rchild=p;
exchange(t->lchild);
exchange(t->rchild);
}
}
2.已知以二叉表做存储结构，试编写安层次顺序便历二叉树的算法
[算法思想]本算法要采用一个队列q，先将二叉树根节点入队列，然后退队列，输出该节点，若它有左子树，便将左子树根节点入队列，若它有右子树，边将右子树根节点入队列，如此直到队列为空为止，因为对列的特点是先进先出，从而达到安层次顺序遍历二叉树的目的
[算法实现]
#define m 100
#define null 0
typedef struct node
{ int data;
struct node lchild,rchild;
}bitree;
bitree *que[m];
int front=0,rear=0;
bitree *creat()
{
bitree *t;
int x;
scanf(&x);
if(x==0)
t=null;
else
{
t=malloc(sizeof(bitree));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return t;
}
void inorder(t)
bitree *t;
{
if(t!=null)
{
inorder(t->lchild);
printf(t->data);
inorder(t->rchild);
}
}
void enqueue(t)
bitree *t;
{
if(front!=(rear+1)%m)
{
rear=(rear+1)%m;
que[rear]=t;
}
}
bitree *delqueue()
{
if(front==rear)
return null;
front=(front+1)%m;
return (que[front]);
}
void leborder(t)
bitree *t;
{bitree *p;
if(t!=null)
{
enqueue(t);
while(front!=rear)
{
p=delqueue();
printf(p->data);
if(p->lchild!=null)
enqueue(p->lchild);
if(p->rchild!=null)
enqueue(p->rchild);
}
}
}
main()
{bitree *root;
printf(“\n”);
root=creat();
inorder(root);
printf(“\n”);
levorder(root);
}
也可以用非递归写出levorder算法。可以用一个对列que遍历过程中的各个节点。由于二叉树以二叉连表存储，所以que为一个指向数据类型为 bitree的指针数组最大容量为maxsize,下标从1开始，同层结点从左到右存放。其中front为队头指针，rear为尾指针
levlorder(t)//安层遍历 二叉树t
bitree *t;//二叉树t为类型bitree
{
bitree *que[maxsize]
//队列que为一个指向类型指针数组，下标从1开始
int rear,front;
if(t)
{
front=0;//置空对列
rear=1;
que[1]=t;
do{
front=front%maxsize+1;//出列
t=que[front];
printf(t->data);
of(t->rchild!=null)//左子树的根结点入队
{
rear=rear%maxsize+1;
que[rear]=t->lchild;
}
if(t->rchild!=null) //右子树的根结点入队
{
rear=rear%maxsize+1;
que[rear]=t->rchild;
}
}while(rear==front);
}
}
已知叉排序树一二叉表作为存储结构，试编写安从达到小的顺序输出二叉排序树的各结点算法。
[算法思想]可以先建立一颗二叉排序树，一二叉连表表示，由于安中序遍历二叉排序树即为安递增次序遍历，所以要按从达到小的顺序输出二叉排序树的各结点的值，可以对二叉排序树从树根结点右子树中最右下结点开始进行遍历，先遍历右子树，在访问根结点，最后遍历左子树这样就可以得到一个安从大到小的顺序输出的序列。
[算法实现]
#define m 100
#define null 0
typedef struct node//二叉树连表类型定义
{int data;
struct node *lchild,*rchild;
}bitree;
void destorder(t)//从右子树开始遍历二叉树
bitree *t;
{
if(t!=null)
{destorder(t->rchild);
printf(t->data);
destorder(t->lchild);
}
bitree *insertbst(t,s)//将新结点插入到t所指的二叉树中
bitree *s,*p;
{
bitree *f,*p;
p=t;
while(p!=null)
{f=p;
if(s->data==p->data)return t;
if(s->data<p->data) p=p->lchild;
else
p=p->rchild;
}
if(t==null)return s;
if(s->key<f->key)f->lchild=s;
else
f->rchild=s;
return t;
}
bitree *creatord()//返回二叉树
｛bitree *t,*s;
int x;
t=null;
scanf(&x);
while(x!=0)
{
s=malloc(sizeof(bitree));
s->data=x;
s->lchild=null;
s->rchild=null;
t=insertbst(t,s);
scanf(&x);
}
return t;
}
main()
{
bitree *root;
printf(“\n”);
root=creatord();
destorder(root);
printf(“\n”);
}
掌握二叉树的结构特征，以及各种存储结构的特点及使用范围掌握用指针类型描述，访问二叉树的运算试验内容编写交换以二叉树连表作存储结构的二茬树中所有节点的左右子树的算法。
[基本思想]设二叉树的根指针为t，且以二叉树连表表示，可以利用一个类型为seqstack的指针来实现，且设栈单元包含两个域，一个为data，一个为top，
整个栈容量为maxsize，当树为非空，将当前的树根节点入栈，同时将当前栈顶当作跟节点，然后依据当前的根节点是否具有孩子节点来判断是否将其左右指针交换；在间交换后的左指针或右指针入栈，这样反复进行，直到栈为空
[算法实现]
#define null o
typedef struct node
{
int data;
struct node lchild,rchild;
}bitree;
typedef int datatype ;//栈元素的数据类型
#define maxsize 64 //栈可能达到的最大容量
typedef struct {
datatype data[maxsize];
int top;
}seqstack//顺序栈类型定义
seqstack *s;// 顺序栈类型指针
bitree *creat()//建立二叉树
{
bitree *t;
int x;
scanf(“&x);
if(x==0)
t=null;
else
{
t=malloc(sizeof(bitree));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return t;
}
void inorder(t)//中序遍历二叉树
bitree *t;
{
if(t!=null)
{
inorder(t->lchild);
prinrf(t->data);
inorder(t->rchild);
}
exchange(t)//对二叉树t所有结点左右子树进行交换
bitree *t
{
bitree *p;
seqstack *s;//为一指针栈，类型为seqstack
if(t)
{
s->top=1;
s->data[s->top]=t;//跟指针t进栈
do
{
t=s->data[s->top];//栈顶元素退栈
s->top--;
if((t->lchild!=null)||(t->rchild!=null))
{
p=t->lchild;//节点的左右指针交换
t->lchild=t->rchild;
t->rchild=p;
}
if(t->lchild!=null)//交换后的左孩子指针入栈
{
s->top++;
s->data[s->top]=t->lchild;
}
if(t->rchild!=null)//交换后的右孩子指针入栈
{
s->top++;
s->data[s->top]=t->rchild;
}
}while(s->top==0)/栈空结束
}
}
main()
{
bitree *root;
root=creat();
inorder(root);
exchange(root);
inorder(root);
}
对于exchange算法也可以利用以下的地归算法
void exchange(t)
bitree *t;
{bitree *p;
if(t!=null)
{
p=t->lchild;
t->lchild=t->rchild;
t->rchild=p;
exchange(t->lchild);
exchange(t->rchild);
}
}
2.已知以二叉表做存储结构，试编写安层次顺序便历二叉树的算法
[算法思想]本算法要采用一个队列q，先将二叉树根节点入队列，然后退队列，输出该节点，若它有左子树，便将左子树根节点入队列，若它有右子树，边将右子树根节点入队列，如此直到队列为空为止，因为对列的特点是先进先出，从而达到安层次顺序遍历二叉树的目的
[算法实现]
#define m 100
#define null 0
typedef struct node
{ int data;
struct node lchild,rchild;
}bitree;
bitree *que[m];
int front=0,rear=0;
bitree *creat()
{
bitree *t;
int x;
scanf(&x);
if(x==0)
t=null;
else
{
t=malloc(sizeof(bitree));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return t;
}
void inorder(t)
bitree *t;
{
if(t!=null)
{
inorder(t->lchild);
printf(t->data);
inorder(t->rchild);
}
}
void enqueue(t)
bitree *t;
{
if(front!=(rear+1)%m)
{
rear=(rear+1)%m;
que[rear]=t;
}
}
bitree *delqueue()
{
if(front==rear)
return null;
front=(front+1)%m;
return (que[front]);
}
void leborder(t)
bitree *t;
{bitree *p;
if(t!=null)
{
enqueue(t);
while(front!=rear)
{
p=delqueue();
printf(p->data);
if(p->lchild!=null)
enqueue(p->lchild);
if(p->rchild!=null)
enqueue(p->rchild);
}
}
}
main()
{bitree *root;
printf(“\n”);
root=creat();
inorder(root);
printf(“\n”);
levorder(root);
}
也可以用非递归写出levorder算法。可以用一个对列que遍历过程中的各个节点。由于二叉树以二叉连表存储，所以que为一个指向数据类型为 bitree的指针数组最大容量为maxsize,下标从1开始，同层结点从左到右存放。其中front为队头指针，rear为尾指针
levlorder(t)//安层遍历 二叉树t
bitree *t;//二叉树t为类型bitree
{
bitree *que[maxsize]
//队列que为一个指向类型指针数组，下标从1开始
int rear,front;
if(t)
{
front=0;//置空对列
rear=1;
que[1]=t;
do{
front=front%maxsize+1;//出列
t=que[front];
printf(t->data);
of(t->rchild!=null)//左子树的根结点入队
{
rear=rear%maxsize+1;
que[rear]=t->lchild;
}
if(t->rchild!=null) //右子树的根结点入队
{
rear=rear%maxsize+1;
que[rear]=t->rchild;
}
}while(rear==front);
}
}
已知叉排序树一二叉表作为存储结构，试编写安从达到小的顺序输出二叉排序树的各结点算法。
[算法思想]可以先建立一颗二叉排序树，一二叉连表表示，由于安中序遍历二叉排序树即为安递增次序遍历，所以要按从达到小的顺序输出二叉排序树的各结点的值，可以对二叉排序树从树根结点右子树中最右下结点开始进行遍历，先遍历右子树，在访问根结点，最后遍历左子树这样就可以得到一个安从大到小的顺序输出的序列。
[算法实现]
#define m 100
#define null 0
typedef struct node//二叉树连表类型定义
{int data;
struct node *lchild,*rchild;
}bitree;
void destorder(t)//从右子树开始遍历二叉树
bitree *t;
{
if(t!=null)
{destorder(t->rchild);
printf(t->data);
destorder(t->lchild);
}
bitree *insertbst(t,s)//将新结点插入到t所指的二叉树中
bitree *s,*p;
{
bitree *f,*p;
p=t;
while(p!=null)
{f=p;
if(s->data==p->data)return t;
if(s->data<p->data) p=p->lchild;
else
p=p->rchild;
}
if(t==null)return s;
if(s->key<f->key)f->lchild=s;
else
f->rchild=s;
return t;
}
bitree *creatord()//返回二叉树
｛bitree *t,*s;
int x;
t=null;
scanf(&x);
while(x!=0)
{
s=malloc(sizeof(bitree));
s->data=x;
s->lchild=null;
s->rchild=null;
t=insertbst(t,s);
scanf(&x);
}
return t;
}
main()
{
bitree *root;
printf(“\n”);
root=creatord();
destorder(root);
printf(“\n”);
}
