+ -
当前位置:首页 → 问答吧 → 有关二叉树的问题

有关二叉树的问题

时间: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;
}


看一下这个程序哪边有错,谢谢了!

作者: 紫箩   发布时间: 2010-06-23

首先,你这个能编译码?

作者: donglongchao   发布时间: 2010-06-24