数据结构二叉树的生成和遍历.doc

6、二叉树的生成
建立一个二叉树是指在内存中建立二叉树的存储结构，这里讨论建立一个二叉链表的方式生成一个二叉树。要建立一个二叉链表，需按照完全二叉树的层次顺序，依次输入结点信息建立二叉链表。对于一般的二叉树，必须添加一些虚结点，使其成为完全二叉树。我用@表示虚结点，#表示输入结束标志。同时设置一个队列，队列是一个指针类型的数组，保存已输入的结点的地址。根据对为指针奇偶数的判断，来决定把字符放到左结点还是有结点中，这样就能生成想要的二叉树。
#define maxsize 100
#include “stdio.h”
#include “malloc.h”
#define NULL 0
typedef struct btnode
{
char data;
struct btonde lchild,rchild;
}
Btree;
Btree*Q[maxsize];
Btree*creatree()
{
char ch;
int front,rear;
Btree *t,*s;
t=NULL;
front=1;
rear=0;
ch=getchar();
}
while(ch!=’#’)
{
s=NULL;
if(ch!=’@’)
{
s=(btree*)mlloc(sizcof(btree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
rear++;
Q[rear]=s;
if(rear==1)T=s;
else
{
if(s&&Q[front])
If(rear%2==0)Q[front]->lchild=s;
Else
Q[front]->rchild=s;
if(rear%2==1)front++;
}
ch=getchar();
}
returnT;
}
二叉树的遍历
上面虽然已经生成二叉树，但实际上用户生成的二叉树是抽象，用户并不太确信已经生成的二叉树是否是自己想要的，于是，可以编制输出程序进一步验证这个已经存在的二叉树的正确性。
二叉树的遍历就是对二叉树的每一个结点访问一次且仅访问一次。我们通过二叉树的序遍历的非递归算法来验证其正确性。二叉树非递归遍历是用显示栈来存储二叉树的结点指针。
1、 先序遍历
使用一个栈，首先将根结点入栈，开始循环；从栈中退出当前结点，先访问它，然后将其右结点入栈，再将其左结点入栈，如此直到栈空为止。
Void porder(Btree*T)
{
Btree*stack[maxsize],*p;
int top=-1;
if(T!=NULL)
{
top++;
stack[top]=T;
while(top>-1)
{
p=stack[top];
top--;
prinft(“%c”,p->data);
if(p->right!=NULL)
{
top++;
stack[top]=p->left;
}
}
}
2、 后序遍历
先将根结点的所有左结点并入栈，出栈一个结点，将该结点的右结点入栈，再将该结点的左结点入栈，当一个结点的左右子树均访问该结点，如此，直到栈空为止。
void pmorder(Btree*T)
{
Btree*stack[maxsize],*p;
int top=-1;
do{
while(T)
{
top++;
stack[top]=T;
T=T->left;
}
p=NULL;
flag=1;
while(top!=-1 &&flag)
{
T=stack[top];
if{t->right==p
}
{
printf(“%c”,T->data);
top++;
p=T;
}
else
{
T=T->right;
flag=0;
}]
}
while(top!=-1);
}
中序遍历
先将根结点的所有左结点并入栈,出栈一个结点,访问该结点,将该结点的右结点入栈,再将该结点的左结点入栈,当一个结点的左子树均访问后再访问该结点,最后访问右结点.如此,直到栈空为止。
Void psorder(btree*T)
{
Btree*stack[maxsize],*p;
int top=-1;
do
{
while(T)
{
top++;
stack[top]=T;
T=T->left;
}
T=stack[top];
printf(“%c”,T->data);
top--;
if(t->right)
{T=T->right;
top++;
stack[top]=T;
T=T->lefti
}
}
while(top!=-1);
}