关于二叉树叶子结点个数有关问题

关于二叉树叶子结点个数问题!

C/C++ code

#include<stdio.h> //有的树运行结果不对#include<malloc.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define NULL 0typedef int Status;typedef int ElemType;//二叉树的链式存储结构typedef struct CSNode{    ElemType data;    struct CSNode *firstchild,*nextsibling;}CSNode,*CSTree;Status CreateCSTree(CSTree &T){    //按先序次序输入二叉树中节点的值（一个字符），空格字符表示空树    //构造二叉链表表示二叉树    char d;    //-----------------------------------------------    //-----------------------------------------------    //-----------------------------------------------    //-----------------------------------------------    scanf("%d",&d);//输入一个数要空一个格,例如:1 2 3 0 0 1 0 0 0    //--------------------------------------    //-----------------------------------------------    //-----------------------------------------------    //-----------------------------------------------    //-----------------------------------------------    if(d==0)        T=NULL;    else    {        if(!(T=(CSNode*)malloc(sizeof(CSNode)))) exit(OVERFLOW);        T->data=d;//生成根节点        CreateCSTree(T->firstchild);//构造第一个孩子结点        CreateCSTree(T->nextsibling);//构造兄弟结点    }    return OK;}Status Visit(ElemType e){    printf("%d ",e);    return OK;}Status PreOrderTraverse(CSTree T,Status(* Visit)(ElemType e)){//采用先序遍历二叉树的递归算法，对每个数据元素条用Visit    if(T)    {        if(Visit(T->data))            if(PreOrderTraverse(T->firstchild,Visit))                if(PreOrderTraverse(T->nextsibling,Visit)) return OK;                return ERROR;    }    else         return OK;}int LeafCount_CSTree(CSTree T){//求二叉链表树的叶子结点个数    if(!T) return 0;    if(!(T->firstchild) && !(T->nextsibling)) return 1;//叶子结点    int count;CSNode *child;    count=0;    for(child=T->firstchild;child;child=child->nextsibling)        count+=LeafCount_CSTree(child);    return count;}void main(){    CSTree T;int count;    CreateCSTree(T);    printf("该树的先序遍历序列是：");    PreOrderTraverse(T,Visit);    count=LeafCount_CSTree(T);    printf("该树的叶子节点数是：%d\n",count);}

这个在输出叶子结点时出错了，请大家看看是哪里错了？调了一阵子，没有弄出来！
例如，你可以输入: 1 2 3 0 0 0 0

[解决办法]
int LeafCount_CSTree(CSTree T)
 函数中的 用来计数的count你不应该定义成局部变量

 否者，每次递归，count都重新置0
[解决办法]
Status CreateCSTree(CSTree &T)
{
//按先序次序输入二叉树中节点的值（一个字符），空格字符表示空树
//构造二叉链表表示二叉树
//char d;
-->
ElemType d; //为int型

[解决办法]
int LeafCount_CSTree(CSTree T)
{//求二叉链表树的叶子结点个数
if(!T) 
return 0;
if(!(T->firstchild) && !(T->nextsibling)) 
return 1;//叶子结点返回1，否则递归进行计算左右孩子的叶子结点，ok
return LeafCount_CSTree(T->firstchild) + LeafCount_CSTree(T->nextsibling);
}

[解决办法]

C/C++ code

//建立二叉树typedef struct bitnode{    char data;    struct bitnode *lchild;    struct bitnode *rchild;}bitnode,*bitree;//初始化二叉树void createbitree(bitree &t){    char ch;    scanf("%c",&ch);    if(ch==' ')        t=NULL;    else    {        t=(bitnode *)malloc(sizeof(bitnode));        t->data=ch;        createbitree(t->lchild);        createbitree(t->rchild);    }}//先序遍历二叉树void preordertraverse(bitree &t){    if(t)    {        printf("%c",t->data);        preordertraverse(t->lchild);        preordertraverse(t->rchild);    }}//中序遍历二叉树void inordertraverse(bitree &t){    if(t)    {        inordertraverse(t->lchild);        printf("%c",t->data);        inordertraverse(t->rchild);    }}//后序遍历二叉树void postordertraverse(bitree &t){    if(t)    {        postordertraverse(t->lchild);        postordertraverse(t->rchild);        printf("%c",t->data);    }}//二叉树叶子结点int leafnumber(bitree &t){    if(!t)        return 0;    else if(!t->lchild && !t->rchild)        return 1;    else        return leafnumber(t->lchild)+leafnumber(t->rchild);}//二叉树的深度int depth(bitree &t){    int depthval,depthleft,depthright;    if(!t)        depthval=0;    else    {        depthleft=depth(t->lchild);        depthright=depth(t->rchild);        depthval=1+(depthleft>depthright?depthleft:depthright);    }    return depthval;}//树的深度int treedepth(bitree &t){    int h1,h2,h;    if(!t)        return 0;    else    {        h1=treedepth(t->lchild);        h2=treedepth(t->rchild);        h=(h1+1)>h2?(h1+1):h2;    }    return h;}//二叉树的复制void copybitree(bitree t,bitree &newt){    if(t)    {        newt=(bitnode *)malloc(sizeof(bitnode));        newt->data=t->data;        copybitree(t->lchild,newt->lchild);        copybitree(t->rchild,newt->rchild);    }    else        newt=NULL;}//队的建立typedef struct qnode{    bitree data;    struct qnode *next;}qnode,*queueptr;typedef struct{    queueptr front;    queueptr rear;}linkqueue;// 队的初始化int initqueue(linkqueue &q){    q.front=q.rear=(queueptr)malloc(sizeof(qnode));    if(!q.front)        return 0;    q.front->next=NULL;    return 1;}//进队int enqueue(linkqueue &q,bitree e){    queueptr p=(queueptr)malloc(sizeof(qnode));    if(!p)        return 0;    p->data=e;    p->next=NULL;    q.rear->next=p;    q.rear=p;    return 1;}//出队int dequeue(linkqueue &q,bitree &e){    if(q.front==q.rear)        return 0;    queueptr p=q.front->next;    e=p->data;    q.front->next=p->next;    if(q.rear==p)        q.rear=q.front;    free(p);    return 1;}//判断队是否为空int emptyqueue(linkqueue &q){    if(q.rear==q.front)        return 1;    else        return 0;}// 二叉树层次遍历void layerorder(bitree e){    linkqueue q;    initqueue(q);    if(e)        enqueue(q,e);    while(!emptyqueue(q))    {        dequeue(q,e);        printf("%c",e->data);        if(e->lchild)            enqueue(q,e->lchild);        if(e->rchild)            enqueue(q,e->rchild);    }} 
  

 

查看更多 下一篇