[已解决]礼貌求助，二叉树

wangyuans

#include <stdio.h>
#include <stdlib.h>

typedef char Elemtype;

typedef struct BiTreeNode
{
        char data;
        struct BiTreeNode *lchild,*rchild;
}BiTreeNode, *BiTree;
//创建二叉树
void CreateBiTree(BiTree &T)
{
        char c;
        scanf("%c",&c);
        if('#'== c)
        {
                T = NULL;
        }
        else
        {
                T = (BiTreeNode *)malloc (sizeof(BiTreeNode));
                T->data = c;
                CreateBiTree(T->lchild);
                CreateBiTree(T->rchild);
        }
}
//访问二叉树结点
void visit(char c, int level)
{
        printf("%c 在第 %d 层\n",c,level);
}
//前序遍历二叉树
void PreOrder(BiTree T,int level)
{
        if(T)
        {
                visit(T->data,level);
                PreOrder(T->lchild,level+1);
                PreOrder(T->rchild,level+1);
        }
}


//求叶子结点个数
void Number(BiTree T,int count)
{
        if(T)
        {
                if(T->lchild == NULL && T->rchild ==NULL)
                {
                        count++;
                        Number(T->lchild,count);
                        Number(T->rchild,count);
                }
        }
}
int main(void)
{
        int level = 1;
        int count = 0;
        BiTree T;
        CreateBiTree(T);
        printf("前序遍历二叉树：\n");
        PreOrder(T,level);

        Number(T,count);
        printf("二叉树叶子结点个数：%d\n",count);
        getchar();
        getchar();
        getchar();
        return 0;
}

这里的count输出一直是0，然后我改动了代码：
int  Number(BiTree T,int count)
{
        if(T)
        {
                if(T->lchild == NULL && T->rchild ==NULL)
                {
                        count++;
                        Number(T->lchild,count);
                        Number(T->rchild,count);
                }
        }
       return count；
}
main函数里是count = Number(T,count);这样还是0，不知道是哪里出错了，我们老师说计数器要用应用型参数，&count。但是我不太明白代码要怎么改动

最佳答案

月排行榜 / 总排行榜

sunrise085

2020-3-27 10:57:15

wangyuans 发表于 2020-3-27 10:44
我想的是统计叶子节点数，当它的左右子树都为空，计数器就加一。在这个小子树里面，只有根结点，没有左右 ...

哦哦，明白了，你是只统计叶子。
那么问题来了

1. if(T->lchild == NULL && T->rchild ==NULL)
   
2. {
   
3.     count++;
   
4.     count+=Number(T->lchild);
   
5.     count+=Number(T->rchild);
   
6. }

复制代码

既然T->lchild == NULL，那么还有必要去调用Number(T->lchild)吗？
我认为应该是当该节点不是叶节点的时候才去进行递归调用吧？
不知道我有没有想错

1. //Number函数实现过程如下
   
2. int  Number(BiTree T)
   
3. {
   
4.         int count=0;
   
5.         if(T)
   
6.         {
   
7.                 if(T->lchild == NULL && T->rchild ==NULL)
   
8.                         count++;
   
9.                 else
   
10.                 {
    
11.                         if (T->lchild)
    
12.                                 count+=Number(T->lchild);
    
13.                         if (T->rchild)
    
14.                                 count+=Number(T->rchild);
    
15.                 }
    
16.         }
    
17.        return count；
    
18. }
    
19. //主函数中的调用如下：
    
20. count=Number(T);

复制代码

跳转到最佳答案楼层

sunrise085

你这个有两种修改方式
一种是按照你老师说的，实际上就是把值传递改为址传递，也就是在函数Number中修改count直接修改的就是主函数中的count，这样也不用有什么返回值了

1. //Number函数实现过程如下
   
2. void  Number(BiTree T,int *count)
   
3. {
   
4.         if(T)
   
5.         {
   
6.                 if(T->lchild == NULL && T->rchild ==NULL)
   
7.                 {
   
8.                         (*count)++;
   
9.                         Number(T->lchild,count);
   
10.                         Number(T->rchild,count);
    
11.                 }
    
12.         }
    
13. }
    
14. //主函数中的调用如下：
    
15. Number(T,&count);

复制代码

另外一种就是，调用Number函数时不传递参数count，让其作为返回值传回主函数

1. //Number函数实现过程如下
   
2. int  Number(BiTree T)
   
3. {
   
4.         int count=0;
   
5.         if(T)
   
6.         {
   
7.                 if(T->lchild == NULL && T->rchild ==NULL)
   
8.                 {
   
9.                         count++;
   
10.                         count+=Number(T->lchild);
    
11.                         count+=Number(T->rchild);
    
12.                 }
    
13.         }
    
14.        return count；
    
15. }
    
16. //主函数中的调用如下：
    
17. count=Number(T);

复制代码

以上是在你的函数基础上帮你修改的。
但是我怎么感觉你的函数最大的问题不是语法问题而是逻辑问题呢
你自己在看一下逻辑问题
Number函数是为了统计叶子节点数吧？
那为什么是当T->lchild == NULL && T->rchild ==NULL进行统计呢？
难道不应该是有节点的时候进行统计吗？
我没有仔细看你的完整程序，片面理解，不知是否正确

wangyuans

sunrise085 发表于 2020-3-27 09:17
你这个有两种修改方式
一种是按照你老师说的，实际上就是把值传递改为址传递，也就是在函数Number中修改co ...

我想的是统计叶子节点数，当它的左右子树都为空，计数器就加一。在这个小子树里面，只有根结点，没有左右子树

sunrise085

wangyuans 发表于 2020-3-27 10:44
我想的是统计叶子节点数，当它的左右子树都为空，计数器就加一。在这个小子树里面，只有根结点，没有左右 ...

哦哦，明白了，你是只统计叶子。
那么问题来了

1. if(T->lchild == NULL && T->rchild ==NULL)
   
2. {
   
3.     count++;
   
4.     count+=Number(T->lchild);
   
5.     count+=Number(T->rchild);
   
6. }

复制代码

既然T->lchild == NULL，那么还有必要去调用Number(T->lchild)吗？
我认为应该是当该节点不是叶节点的时候才去进行递归调用吧？
不知道我有没有想错

1. //Number函数实现过程如下
   
2. int  Number(BiTree T)
   
3. {
   
4.         int count=0;
   
5.         if(T)
   
6.         {
   
7.                 if(T->lchild == NULL && T->rchild ==NULL)
   
8.                         count++;
   
9.                 else
   
10.                 {
    
11.                         if (T->lchild)
    
12.                                 count+=Number(T->lchild);
    
13.                         if (T->rchild)
    
14.                                 count+=Number(T->rchild);
    
15.                 }
    
16.         }
    
17.        return count；
    
18. }
    
19. //主函数中的调用如下：
    
20. count=Number(T);

复制代码

wangyuans

sunrise085 发表于 2020-3-27 09:17
你这个有两种修改方式
一种是按照你老师说的，实际上就是把值传递改为址传递，也就是在函数Number中修改co ...

我还是调不通这个程序，应该就是你说有逻辑问题那个地方出错了，好迷茫呀

wangyuans

sunrise085 发表于 2020-3-27 10:57
哦哦，明白了，你是只统计叶子。
那么问题来了

1. void Number(BiTree T,int &count)
   
2. {
   
3.         if(T)
   
4.         {
   
5.                 if(T->lchild == NULL && T->rchild ==NULL)
   
6.                 {
   
7.                         count++;
   
8.                        
   
9.                 }else
   
10.                 {
    
11.                         Number(T->lchild,count);
    
12.                         Number(T->rchild,count);
    
13.                 }
    
14.         }
    
15. }

复制代码

这样就调通了，太感谢你了