实验二二叉树的存储结构及各种运算的实现第一题：
#include "stdio.h"
#include "malloc.h"
#define maxsize 66
typedef int datatype;
typedef struct node
{
datatype data ;
struct node *lchild,*rchild;
} bitree;
bitree *Q[maxsize];
bitree *creatree()
{
char ch;
int front,rear;
bitree *root,*s;
root=NULL;
front=1;rear=0;
ch=getchar();
while (ch!='#')
{
s=NULL;
if(ch!='@')
{
s=malloc(sizeof(bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=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();
}
return root;
}
preorder(bitree *t) //前{
if (t)
{
printf(" %c ",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
inorder(bitree *t) //中{
if (t)
{
inorder(t->lchild);
printf(" %c ",t->data);
inorder(t->rchild);
}
}
postorder(bitree *t) //后{
if (t)
{
postorder(t->lchild);
postorder(t->rchild);
printf(" %c ",t->data);
}
}
int height(bitree *t) //高度{
int hl,hr;
if(!t) return 0;
else
{
hl=height(t->lchild);
hr=height(t->rchild);
return ((hl>hr?hl:hr)+1);
}
}
int leaf(bitree *t) //叶子{
static int s;
if(t)
{
leaf(t->lchild);
leaf(t->rchild);
if(t->lchild==NULL&&t->rchild==NULL)
s=s+1;
}
return s;
}
main()
{
bitree *t;
int x,y;
printf("输入数据，以#做结尾:\n");
t=creatree();
printf("preorder:\t");preorder(t);
printf("\ninorder:\t");inorder(t);
printf("\npostorder:\t");postorder(t);
x=height(t);
y=leaf(t);
printf("\n高度:%d",x);
printf("\n叶子:%d",y);
printf("\n");
}
第二题：
#include <stdio.h>
#include <malloc.h>
#define maxsize 40
typedef struct node{
char data;
struct node *lchild,*rchild;
int ltag,rtag;
} bitree;
bitree *Q[maxsize]; /*队列*/
bitree *pre=NULL;
bitree *creatree()
{ char ch;
int front,rear; /*队头、队尾*/
bitree *root,*s;
root=NULL; /*空树*/
front=1; rear=0; /*空队*/
ch=getchar();
while(ch!='#')
{ s=NULL;
if(ch!='@') /*建立新结点*/
{ s=(bitree *)malloc(sizeof(bitree));
s->data=ch;
s->lchild=s->rchild=NULL;
s->ltag=s->rtag=0;
}
rear++;
Q[rear]=s; /*入队*/
if(rear==1) root=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();
}
return root;
}
//中序遍历;
void inorder(bitree *t)
{ if(t)
{ inorder(t->lchild);
printf("%c",t->data);
inorder(t->rchild);
}
}
//中序线索划;
void INTHREAD(bitree *p)
{if(p!=NULL)
{INTHREAD(p->lchild);
if(p->lchild==NULL) p->ltag=1;
if(p->rchild==NULL) p->rtag=1;
if(pre!=NULL)
{ if(pre->rtag==1) pre->rchild=p;
if(p->ltag==1) p->lchild=pre; } pre=p;
INTHREAD(p->rchild);
}
}
//中序线索二叉树中求中序后继结点;
bitree * inordernext (bitree *p)
{
bitree *q;
if(p->rtag==1) return p->rchild;
else
{ q=p->rchild;
while(q->ltag==0) q=q->lchild;
return q;
}
}
//中序遍历;
void traverseinthread(bitree *p)
{
if(p!=NULL)
{while (p->ltag==0 )
p=p->lchild;
do {printf("%c",p->data);
p=inordernext(p);
}while(p!=NULL);
}
}
void main()
{ bitree *t;
t=creatree();
printf("中序遍历结果是:\n:");
inorder(t);
printf("\n");
INTHREAD(t);
printf("线索化中序遍历的结果是：\n");
printf("\n");
traverseinthread(t);
printf("\n")；}
输入数据为：abfcd@g@@e#。