注册 登录
编程论坛 数据结构与算法

另一个树的问题,头疼啊.

发布于 2010-06-03 19:09, 685 次点击
计算任一一层的叶子结点数
我的代码:
#include <stdio.h>
#include <malloc.h>
#define maxsize 100

typedef char ElemType;
typedef struct node
{
    ElemType data;
    struct node *lchild,*rchild;
}BiNode,*BiTree;

BiTree CreatBiTree()
{
    BiTree T;
    ElemType x;
    scanf("%c",&x);
    if(x=='#') T=NULL;
    else
    {
        T=(BiTree)malloc(sizeof(BiNode));
        T->data=x;
        T->lchild=CreatBiTree();
        T->rchild=CreatBiTree();
    }
    return T;
}

int Leaves(BiTree T,int k)
{
    BiTree tree[maxsize];
    int i,front,rear,last,level,leaf;
    tree[1]=T;
    front=1;
    rear=2;
    level=1;
    last=2;
    leaf=0;
    while(level<k)
    {
        if(tree[front]->lchild) tree[rear++]=tree[front]->lchild;
        if(tree[front]->rchild) tree[rear++]=tree[front]->rchild;
        front++;
        if(front==last) { level++;last=rear; }
    }
    for(i=front;i<rear;i++)
    if(!tree[i]->lchild&&!tree[i]->rchild) leaf++;
    return leaf;
}

int main()
{
    BiTree T;
    int k,x;
    T=CreatBiTree();
    scanf("%d",&k);
    x=Leaves(T,k);
    printf("%d",x);
    return 0;
}
编译过了,可是运行时显示栈错误 *_*
7 回复
#2
hzh5122010-06-03 20:25
话不多说,自己看

程序代码:

//计算任一一层的叶子结点数
#include <stdio.h>
#include <malloc.h>
#define maxsize 100
typedef char ElemType;
typedef struct node
{
    ElemType data;
    struct node *lchild,*rchild;
}BiNode,*BiTree;
BiTree CreatBiTree();
int Leaves(BiTree T,int k);
int main()
{
    BiTree T;
    int k,x;
    T=CreatBiTree();
    scanf("%d",&k);
    x=Leaves(T,k);
    printf("The %dth level of tree is %d\n",k,x);
    return 0;
}
BiTree CreatBiTree()
{
    BiTree T;
    ElemType x;
    scanf("%c",&x);
    if(x=='@') T=NULL;
    else
    {
        T=(BiTree)malloc(sizeof(BiNode));
        T->data=x;
        T->lchild=CreatBiTree();
        T->rchild=CreatBiTree();
    }
    return T;
}
int Leaves(BiTree T,int k)
{
    BiTree tree[maxsize];
    int i,front,rear,last,level,leaf;
    tree[1]=T;
    front=1;
    rear=2;
    level=1;
    last=2;
    leaf=0;
    while(level<k)
    {
        if(tree[front]->lchild)
            tree[rear++]=tree[front]->lchild;
        if(tree[front]->rchild)
            tree[rear++]=tree[front]->rchild;
        front++;
        if(front==last) { level++;last=rear; }
    }
    return rear-front;
//    for(i=front;i<rear;i++)
//        if(!tree[i]->lchild&&!tree[i]->rchild) leaf++;
//        return leaf;
}

#3
2010-06-03 20:57
return rear-front 返回的应该是k层的结点数吧??
#4
hzh5122010-06-03 21:09
对,把我的注释去掉就可以计算叶子数了(我的样例是@不是#)

abc##de#g##f###
abd##e##cf##g##
#5
2010-06-03 21:29
一个很奇怪的问题,不知道你知不知道是为什呢,同样的代码在xp下编译一点问题都没有,在Ubuntu下就不行了,不是编译不成功,就是生成的程序运行结果不对就是栈错误。
#6
2010-06-03 21:30
这道题就是这个问题。
#7
hzh5122010-06-03 21:57
我在 ubuntu g++ 4.3.3中编译运行一点问题都没有
#8
hzh5122010-06-03 22:04
传上截图:
只有本站会员才能查看附件,请 登录




1