- 论坛徽章:
- 0
|
请设计一个算法，把二叉树的叶子结点按从左到右的顺序连成一个单链表。二叉树用二叉链存储，链接时用叶子结点的rchild 域存放指针。
#include<stdio.h>
#include<string.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
char data;
struct node *lchild,*rchild;//左右孩子的指针
}bitnode,*bitree;
typedef struct lnode
{
char data;
struct lnode *next;
}linklist;
typedef struct quenode
{
bitnode *a;
struct quenode *next;
}qnode;
typedef struct qu//队列
{
qnode *front;
qnode *rear;
}queue;
void initqueue(queue *q)//队列初始化
{
q->front=q->rear=(qnode*)malloc(sizeof(qnode));
q->front->next=NULL;
}
void ing(queue *q,bitnode *e)
{
qnode *s;
s=(qnode*)malloc(sizeof(qnode));
s->a=e;
q->rear->next=s;
s->next=NULL;
q->rear=s;
}
void deq(queue *q,bitnode *e)
{
qnode *p;
p=(qnode*)malloc(sizeof(qnode));
e=q->front->next->a;
p=q->front->next;
q->front->next=q->front->next->next;
free(p);
}
static createtree(bitree t)//按先序遍历建立的二叉树
{
char ch;
scanf("%c",&ch);
if(ch=='*') t=NULL;
else
{
if(!(t=(bitnode*)malloc(sizeof(bitnode)))) exit(0);
t->data=ch;
createtree(t->lchild);
createtree(t->rchild);
}
return 1;
}
linklist *head;
void transformlink(bitree t,queue *q)//将树通过队列，从上到下储存到链表中
{
ing(q,t);
linklist *p2,*p3;
head=(linklist*)malloc(sizeof(linklist));
p2=head;
while(1)
{
bitnode e;
if(q->front==q->rear) break;
if(q->front->next->a->lchild!=NULL)
{
ing(q,q->front->next->a->lchild);
}
if(q->front->next->a->rchild!=NULL)
{
ing(q,q->front->next->a->rchild);
}
deq(q,&e);
p3=(linklist*)malloc(sizeof(linklist));
p3->data=e.data;
p3->next=NULL;
p2->next=p3;
p2=p3;
}
}
void input()
{
linklist *p;
p=head->next;
while(p!=NULL)
{
printf("%c",p->data);
p=p->next;
}
}
int main()
{
queue q;
bitnode t;
initqueue(&q);
createtree(&t);
transformlink(&t,&q);
input();
return 0;
}
看一下这个程序哪边有错，谢谢了！ |
|
免费注册
发表于 2010-06-23 23:10
