有关二叉树的问题
时间:2010-06-23
来源:互联网
请设计一个算法,把二叉树的叶子结点按从左到右的顺序连成一个单链表。二叉树用二叉链存储,链接时用叶子结点的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;
}
看一下这个程序哪边有错,谢谢了!
#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
首先,你这个能编译码?
作者: donglongchao 发布时间: 2010-06-24
相关阅读 更多
热门阅读
-
office 2019专业增强版最新2021版激活秘钥/序列号/激活码推荐 附激活工具
阅读:74
-
如何安装mysql8.0
阅读:31
-
Word快速设置标题样式步骤详解
阅读:28
-
20+道必知必会的Vue面试题(附答案解析)
阅读:37
-
HTML如何制作表单
阅读:22
-
百词斩可以改天数吗?当然可以,4个步骤轻松修改天数!
阅读:31
-
ET文件格式和XLS格式文件之间如何转化?
阅读:24
-
react和vue的区别及优缺点是什么
阅读:121
-
支付宝人脸识别如何关闭?
阅读:21
-
腾讯微云怎么修改照片或视频备份路径?
阅读:28