论坛 › 数据结构与算法 › 礼貌求助，二叉树

wangyuans 发表于 2020-3-26 15:00:05

礼貌求助，二叉树

#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，然后我改动了代码：
intNumber(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 09:17:13

你这个有两种修改方式
一种是按照你老师说的，实际上就是把值传递改为址传递，也就是在函数Number中修改count直接修改的就是主函数中的count，这样也不用有什么返回值了
//Number函数实现过程如下
voidNumber(BiTree T,int *count)
{
      if(T)
      {
                if(T->lchild == NULL && T->rchild ==NULL)
                {
                        (*count)++;
                        Number(T->lchild,count);
                        Number(T->rchild,count);
                }
      }
}
//主函数中的调用如下：
Number(T,&count);
另外一种就是，调用Number函数时不传递参数count，让其作为返回值传回主函数
//Number函数实现过程如下
intNumber(BiTree T)
{
      int count=0;
      if(T)
      {
                if(T->lchild == NULL && T->rchild ==NULL)
                {
                        count++;
                        count+=Number(T->lchild);
                        count+=Number(T->rchild);
                }
      }
       return count；
}
//主函数中的调用如下：
count=Number(T);

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

wangyuans 发表于 2020-3-27 10:44:21

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

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

sunrise085 发表于 2020-3-27 10:57:15

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

哦哦，明白了，你是只统计叶子。
那么问题来了
if(T->lchild == NULL && T->rchild ==NULL)
{
    count++;
    count+=Number(T->lchild);
    count+=Number(T->rchild);
}
既然T->lchild == NULL，那么还有必要去调用Number(T->lchild)吗？
我认为应该是当该节点不是叶节点的时候才去进行递归调用吧？
不知道我有没有想错
//Number函数实现过程如下
intNumber(BiTree T)
{
      int count=0;
      if(T)
      {
                if(T->lchild == NULL && T->rchild ==NULL)
                        count++;
                else
                {
                        if (T->lchild)
                              count+=Number(T->lchild);
                        if (T->rchild)
                              count+=Number(T->rchild);
                }
      }
       return count；
}
//主函数中的调用如下：
count=Number(T);

wangyuans 发表于 2020-3-27 11:07:03

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

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

wangyuans 发表于 2020-3-27 11:11:00

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



void Number(BiTree T,int &count)
{
        if(T)
        {
                if(T->lchild == NULL && T->rchild ==NULL)
                {
                        count++;
                       
                }else
                {
                        Number(T->lchild,count);
                        Number(T->rchild,count);
                }
        }
}

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

查看完整版本: 礼貌求助，二叉树