[已解决]这样求叶子结点数有错吗？

愿你

我明明已经定义了leafcount 可是编译器一直提示我第一个leafcount：必须是指向完整对象类型的指针；提示我第二个leafcount：返回值与函数类型不匹配？？我不都定义的整型吗？？？

int leafcount(BiTree T)
{  
        int leafcount=0;
        if(T)
        {
                if(T->lchild ==NULL &&T->rchild==NULL)
                        leafcount++;
                leafcount(T->lchild);
                leafcount(T->rchild);
                return leafcount;
        }
}

最佳答案

月排行榜 / 总排行榜

ABC23

2018-4-25 14:07:04

问题出在createtree()这个方法。
====================
void creattree(BiTree *T)  //利用递归先序创建二叉树
{
        char ch;
        printf("请输入\n");
        scanf("%c",&ch);
        if(ch=='#')
                (*T)=NULL;
        else
        {
                (*T)=(BiTree)(malloc(sizeof(BiNode)));
                (*T)->data=ch;
                creattree(&(*T)->lchild);
                creattree(&(*T)->rchild);
        }
        printf("二叉树创建完毕\n");
}

在我的机子上跑的结果：

请创建一棵二叉树：
空树构造成功。
请输入
1 2
请输入
请输入
请输入
请输入
#
二叉树创建完毕
请输入
请输入

===================
看到了吗，你在createtree()方法里调用自身，想要创建其两个孩子结点（包括NIL）。
但是，正如上面指出的，本来应该结束的地方并没有结束。
这是我写的：

首先调用initBinaryTree()，创建一棵空树（你的逻辑比较简单，应该判断if 内存不足，抛出创建空树失败），接着为它安排一个data（这不是什么难事）；

int insertNode(BiPtr ptr)
{
        BiNode newNode = (BiNode)malloc(sizeof(BiNode));
        if(BiPtr == null)
        {
                print("Out of space!");
                return 1;        // 插入失败，返回1
        }
        print("Enter data as follow.");
        scanf("%d", newNode->data);
        BiPtr pr = ptr;
        while(pr)
        {
                if((pr->leftchild || pr->right) && newNode->data > pr->data)
                {
                        pr = pr->leftchild;
                }
                else if((pr->leftchild || pr->right) && newNode->data > pr->data){
                        pr = pr->rightchild;
                }
                else{
                        print("二叉树不允许有相同元素节点!");
                        return 1;
        }
        pr ->leftchild = &newNode;
        return 0;        // 插入成功，返回0
}

createTree()方法是以insertNode为基础来写的，这样写逻辑比较清晰。

/** ptr是树根，n是想要分配的结点个数（可以自己发挥） */
int createTree(BiPtr ptr, int n)
{
        if(ptr == null)                // 如果是空树
        {
                *ptr = malloc(sizeof(BiNode));        // 就为树根创建一块内存（这里应该if判断下是否成功分配，否早返回1）
                print("Enter data as follow\n");
                scanf("%d", ptr->data);
        }
        while(n--)
        {
                insertNode(ptr);
        }
        return 0;
}

================================

可以看到都是把树根结点（的指针，这样比较轻巧）作为参数传递给二叉树的方法，可以说树根是整棵树的关键节点，掌握了树根也就掌握了整棵树。

跳转到最佳答案楼层

BngThea

不要将变量名和函数名重名

愿你

BngThea 发表于 2018-4-25 10:32
不要将变量名和函数名重名

可是我换成了别的之后，它又说我未定义标识符

BngThea

愿你 发表于 2018-4-25 10:35
可是我换成了别的之后，它又说我未定义标识符

上代码看看，还有具体的错误提示

愿你

BngThea 发表于 2018-4-25 10:48
上代码看看，还有具体的错误提示

#include <stdio.h>
#include <stdlib.h>
typedef struct BiNode
{
        char data;
        struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

int  inittree(BiTree *T)  //构造空二叉树
{
        (*T)=NULL;
        printf("空树构造成功。\n");
        return 0;
}

void creattree(BiTree *T)  //利用递归先序创建二叉树
{
        char ch;
        scanf("%c",&ch);
        if(ch=='#')
                (*T)=NULL;
        else
        {
                (*T)=(BiTree)(malloc(sizeof(BiNode)));
                (*T)->data=ch;
                creattree(&(*T)->lchild);
                creattree(&(*T)->rchild);
        }
}


void preordertree(BiTree T)  //递归先序遍历二叉树
{
        if(T)
        {
                printf("%c",T->data);
                preordertree(T->lchild);
                preordertree(T->rchild);
        }
}
void inordertree(BiTree T)  //递归中序遍历二叉树
{
        if(T)
        {
                inordertree(T->lchild);
                printf("%c",T->data);
                inordertree(T->rchild);
        }
}
void postordertree(BiTree T)  //递归后续遍历二叉树
{
        if(T)
        {
                postordertree(T->lchild);
                postordertree(T->rchild);
                printf("%c",T->data);
        }
}
int isemptytree(BiTree T) //判断二叉树是否为空二叉树
{
        if(T==NULL)
        {
                printf("该二叉树为空。\n");
                return 0;
        }
        else
        {
                printf("该二叉树不为空。\n");
                return -1;
        }
}

void destroytree(BiTree *T) //递归销毁二叉树，即把包括头的全部节点释放，详见“https://blog.csdn.net/bzhxuexi/article/details/41721429”
{
        if(*T)
        {
                if((*T)->lchild)
                {
                        destroytree(&(*T)->lchild);
                }
                if((*T)->rchild)
                {
                        destroytree(&(*T)->rchild);
                }
                free(*T);
                (*T)=NULL; //空指针赋值0；
        }
}

int cleartree(BiTree *T) //清空树，即保留头结点，后面全部释放
{
        if(*T==NULL)
                return 0;
        else
        {
                cleartree(&(*T)->lchild);
                cleartree(&(*T)->rchild);
                free((*T));
                return 1;
        }
}

int deeptree(BiTree T)  //求二叉树的深度，递归过程详见“https://blog.csdn.net/tackycheng/article/details/6445916”
{
        int deep=0;
        int ldeep,rdeep;  //左子树深度和右子树深度
        if(T==NULL)
                return 0;
        else
        {
                ldeep=deeptree(T->lchild);
                rdeep=deeptree(T->rchild);
                deep=ldeep>=rdeep?ldeep+1:rdeep+1;
                return deep;
        }
}

int nodecount(BiTree T)
{
        int lnode,rnode,node;
        if(T==NULL)
                return 0;
        else
        {
                lnode=nodecount(T->lchild);
                rnode=nodecount(T->rchild);
                return (lnode+rnode+1);
        }
}

int leafcount(BiTree T)
{
        int lleaf,rleaf,leaf; //分别记录左右子树上的叶子结点总数以及叶子结点总数
        leaf=0;
        if(T==NULL)
                return 0;
        else
        {
                lleaf=leafcount(T->lchild);
                rleaf=leafcount(T->rchild);
                if(lleaf==0&&rleaf==0)
                        return 1;
                else
                        return lleaf+rleaf;
        }
}

/*int leafcount(BiTree T)
{  
        int count=0;
        if(T)
        {
                if(T->lchild ==NULL &&T->rchild==NULL)
                        count++;
                leafcount(T->lchild);
                leafcount(T->rchild);
                return count;
        }
}*/

char root(BiTree T) //若树存在，返回树的根。
{
        char e;
        if(T==NULL)
                return 0;
        else
        {
                e=T->data;
                return e;
        }
}















int main()
{
        BiTree T;
        int deep;
        printf("请创建一棵二叉树：\n");
        inittree(&T);
        creattree(&T);
        //deep=deeptree(T);
        //printf("二叉树深度为%d\n",deep);
        //deep=nodecount(T);
        //printf("二叉树结点总数为%d\n",deep);
        deep=root(T);
        printf("二叉树根为%c\n",deep);
        //deep=leafcount(T);
        //printf("二叉树叶子结点总数为%d\n",deep);
        //destroytree(&T);
        //isemptytree(T);
        printf("该二叉树的前序遍历结果为：");
        preordertree(T);
        printf("该二叉树的中序遍历结果为：");
        inordertree(T);
        printf("该二叉树的后序遍历结果为：");
        postordertree(T);
        return 0;
}

愿你

BngThea 发表于 2018-4-25 10:48
上代码看看，还有具体的错误提示

代码是leafcount被加注释的那一段
错误提示：1>------ 已启动生成: 项目: 二叉树, 配置: Debug Win32 ------
1>生成启动时间为 2018/4/25 10:58:38。
1>InitializeBuildStatus:
1>  正在创建“Debug\二叉树.unsuccessfulbuild”，因为已指定“AlwaysCreate”。
1>ClCompile:
1>  二叉树.c
1>e:\二叉树\二叉树\二叉树.c(19): warning C4996: 'scanf': This function or variable may be unsafe. Consider using scanf_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\stdio.h(304) : 参见“scanf”的声明
1>e:\二叉树\二叉树\二叉树.c(120): warning C4101: “node”: 未引用的局部变量
1>e:\二叉树\二叉树\二叉树.c(149): error C3872: “0xa0”: 此字符不允许在标识符中使用
1>e:\二叉树\二叉树\二叉树.c(150): error C2065: “ ”: 未声明的标识符
1>e:\二叉树\二叉树\二叉树.c(150): error C2143: 语法错误 : 缺少“;”(在“类型”的前面)
1>e:\二叉树\二叉树\二叉树.c(154): error C2065: “count”: 未声明的标识符
1>e:\二叉树\二叉树\二叉树.c(157): error C2065: “count”: 未声明的标识符

ABC23

问题出在createtree()这个方法。
====================
void creattree(BiTree *T)  //利用递归先序创建二叉树
{
        char ch;
        printf("请输入\n");
        scanf("%c",&ch);
        if(ch=='#')
                (*T)=NULL;
        else
        {
                (*T)=(BiTree)(malloc(sizeof(BiNode)));
                (*T)->data=ch;
                creattree(&(*T)->lchild);
                creattree(&(*T)->rchild);
        }
        printf("二叉树创建完毕\n");
}

在我的机子上跑的结果：

请创建一棵二叉树：
空树构造成功。
请输入
1 2
请输入
请输入
请输入
请输入
#
二叉树创建完毕
请输入
请输入

===================
看到了吗，你在createtree()方法里调用自身，想要创建其两个孩子结点（包括NIL）。
但是，正如上面指出的，本来应该结束的地方并没有结束。
这是我写的：

首先调用initBinaryTree()，创建一棵空树（你的逻辑比较简单，应该判断if 内存不足，抛出创建空树失败），接着为它安排一个data（这不是什么难事）；

int insertNode(BiPtr ptr)
{
        BiNode newNode = (BiNode)malloc(sizeof(BiNode));
        if(BiPtr == null)
        {
                print("Out of space!");
                return 1;        // 插入失败，返回1
        }
        print("Enter data as follow.");
        scanf("%d", newNode->data);
        BiPtr pr = ptr;
        while(pr)
        {
                if((pr->leftchild || pr->right) && newNode->data > pr->data)
                {
                        pr = pr->leftchild;
                }
                else if((pr->leftchild || pr->right) && newNode->data > pr->data){
                        pr = pr->rightchild;
                }
                else{
                        print("二叉树不允许有相同元素节点!");
                        return 1;
        }
        pr ->leftchild = &newNode;
        return 0;        // 插入成功，返回0
}

createTree()方法是以insertNode为基础来写的，这样写逻辑比较清晰。

/** ptr是树根，n是想要分配的结点个数（可以自己发挥） */
int createTree(BiPtr ptr, int n)
{
        if(ptr == null)                // 如果是空树
        {
                *ptr = malloc(sizeof(BiNode));        // 就为树根创建一块内存（这里应该if判断下是否成功分配，否早返回1）
                print("Enter data as follow\n");
                scanf("%d", ptr->data);
        }
        while(n--)
        {
                insertNode(ptr);
        }
        return 0;
}

================================

可以看到都是把树根结点（的指针，这样比较轻巧）作为参数传递给二叉树的方法，可以说树根是整棵树的关键节点，掌握了树根也就掌握了整棵树。

愿你

ABC23 发表于 2018-4-25 14:07
问题出在createtree()这个方法。
====================
void creattree(BiTree *T)  //利用递归先序创建 ...

哇为什么我觉得好难啊
可是我执行creattree的时候他的遍历结果也都是对的呀