用队列实现按层次创建二叉树的源代码，最好是C语言

Question

如题所述

Answer 1

队列？？你每输入一个节点将其存入队列中，再输入它的左孩子，它的左孩子也会入队，我们取的时候应先取该节点的左孩子，

LZ一定要用队列也行，但绝对不是正确的选择！

队列如下：

#include <iostream>
using namespace std;
typedef struct bitnode
{
    char data;
    struct bitnode *lchild,*rchild;
}*bitree,tree;
int number=0;
void createbitree(bitree &t)
{
    char c;
    int i=0,r=0,f=0;//r,f分别指向队首和队尾
    bitree p=NULL,temp=NULL,pre=NULL,s[100];
    s[0]=NULL;
    int lflag[100]={0};
    int rflag[100]={0};
    printf("请输入根节点：");
    t=new tree;
    t->lchild=t->rchild=NULL;
    scanf("%c",&t->data);
    temp=pre=t->lchild;
    s[++i]=t;
    f=i;
    p = t;
    while(f!=r)
    {
        if(p->lchild==NULL&&lflag[i]==0)
        {
            printf("请输入%c的左孩子:",p->data);
            fflush(stdin);
            scanf("%c",&c);
            if(c!='#')
            {
                p->lchild = new tree;
                p = p->lchild;
                p->lchild=p->rchild=NULL;
                p->data = c;
                s[++f]=p;
                i = f;
                lflag[i]=rflag[i]=0;
            }
            else
                lflag[i]=1;
        }
        else if(p->rchild==NULL&&rflag[i]==0)
        {
            printf("请输入%c的右孩子:",p->data);
            fflush(stdin);
            scanf("%c",&c);
            if(c!='#')
            {
                p->rchild = new tree;
                p = p->rchild;
                p->lchild=p->rchild=NULL;
                p->data = c;
                s[++f]=p;
                i=f;
                lflag[i]=rflag[i]=0;
            }
            else
            {
                rflag[i]=1;
                p=s[++r];
                i=r;
            }
        }
        else
        {
            p=s[++r];
            i=r;
        }
    }
}
void preorder(bitree &t)//遍历二叉树，输出函数
{
    if (t!=0)
    {
        cout<<t->data<<",";
        preorder(t->lchild);
        preorder(t->rchild);
    }
}
void main()
{
    bitree t;
    t=0;
    createbitree(t);
    cout<<"the value of the preorder value is:";
    preorder(t);
}

在此，强烈建议LZ用栈，更符合树的输入层次：

#include <iostream>
using namespace std;
typedef struct bitnode
{
    char data;
    struct bitnode *lchild,*rchild;
}*bitree,tree;
int number=0;
void createbitree(bitree &t)
{
    char c;
    int i=0;
    bitree p=NULL,temp=NULL,pre=NULL,s[100];
    s[0]=NULL;
    int lflag[100]={0};
    int rflag[100]={0};
    printf("请输入根节点：");
    t=new tree;
    t->lchild=t->rchild=NULL;
    scanf("%c",&t->data);
    temp=pre=t->lchild;
    s[++i]=t;
    p = t;
    while(s[i]!=NULL)
    {
        if(p->lchild==NULL&&lflag[i]==0)
        {
            printf("请输入%c的左孩子:",p->data);
            fflush(stdin);
            scanf("%c",&c);
            if(c!='#')
            {
                p->lchild = new tree;
                p = p->lchild;
                p->lchild=p->rchild=NULL;
                p->data = c;
                s[++i]=p;
                lflag[i]=rflag[i]=0;
            }
            else
                lflag[i]=1;
        }
        else if(p->rchild==NULL&&rflag[i]==0)
        {
            printf("请输入%c的右孩子:",p->data);
            fflush(stdin);
            scanf("%c",&c);
            if(c!='#')
            {
                p->rchild = new tree;
                p = p->rchild;
                p->lchild=p->rchild=NULL;
                p->data = c;
                s[++i]=p;
                lflag[i]=rflag[i]=0;
            }
            else
            {
                rflag[i]=1;
                p=s[--i];
            }
        }
        else
            p=s[--i];
    }
}
void preorder(bitree &t)//遍历二叉树，输出函数
{
    if (t!=0)
    {
        cout<<t->data<<",";
        preorder(t->lchild);
        preorder(t->rchild);
    }
}
void main()
{
    bitree t;
    t=0;
    createbitree(t);
    cout<<"the value of the preorder value is:";
    preorder(t);
}

不懂追问！你的疑问往往是我要学习的地方！

追问

能不能用上面的算法帮我写个范例，我也知道用栈比较好，但这毕竟是老师布置的作业，我刚学不久，很多不懂

追答

百度限制字数，贴不出来：

附件！

算法是一样的，昨天是我自己想叉了……

程序都是自己敲的，难免有缺漏，有问题Hi我！

2013 5 23 7:34

追问

附件失效了

追答

逗……服了百度……老是出事

不行啊，传不上去，

你QQ多少……我发邮件