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

愿你

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

1. int leafcount(BiTree T)
   
2. {  
   
3.         int leafcount=0;
   
4.         if(T)
   
5.         {
   
6.                 if(T->lchild ==NULL &&T->rchild==NULL)
   
7.                         leafcount++;
   
8.                 leafcount(T->lchild);
   
9.                 leafcount(T->rchild);
   
10.                 return leafcount;
    
11.         }
    
12. }
    

复制代码

最佳答案

月排行榜 / 总排行榜

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
上代码看看，还有具体的错误提示

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. typedef struct BiNode
   
4. {
   
5.         char data;
   
6.         struct BiNode *lchild,*rchild;
   
7. }BiNode,*BiTree;
   
8. 
   
9. int  inittree(BiTree *T)  //构造空二叉树
   
10. {
    
11.         (*T)=NULL;
    
12.         printf("空树构造成功。\n");
    
13.         return 0;
    
14. }
    
15. 
    
16. void creattree(BiTree *T)  //利用递归先序创建二叉树
    
17. {
    
18.         char ch;
    
19.         scanf("%c",&ch);
    
20.         if(ch=='#')
    
21.                 (*T)=NULL;
    
22.         else
    
23.         {
    
24.                 (*T)=(BiTree)(malloc(sizeof(BiNode)));
    
25.                 (*T)->data=ch;
    
26.                 creattree(&(*T)->lchild);
    
27.                 creattree(&(*T)->rchild);
    
28.         }
    
29. }
    
30. 
    
31. 
    
32. void preordertree(BiTree T)  //递归先序遍历二叉树
    
33. {
    
34.         if(T)
    
35.         {
    
36.                 printf("%c",T->data);
    
37.                 preordertree(T->lchild);
    
38.                 preordertree(T->rchild);
    
39.         }
    
40. }
    
41. void inordertree(BiTree T)  //递归中序遍历二叉树
    
42. {
    
43.         if(T)
    
44.         {
    
45.                 inordertree(T->lchild);
    
46.                 printf("%c",T->data);
    
47.                 inordertree(T->rchild);
    
48.         }
    
49. }
    
50. void postordertree(BiTree T)  //递归后续遍历二叉树
    
51. {
    
52.         if(T)
    
53.         {
    
54.                 postordertree(T->lchild);
    
55.                 postordertree(T->rchild);
    
56.                 printf("%c",T->data);
    
57.         }
    
58. }
    
59. int isemptytree(BiTree T) //判断二叉树是否为空二叉树
    
60. {
    
61.         if(T==NULL)
    
62.         {
    
63.                 printf("该二叉树为空。\n");
    
64.                 return 0;
    
65.         }
    
66.         else
    
67.         {
    
68.                 printf("该二叉树不为空。\n");
    
69.                 return -1;
    
70.         }
    
71. }
    
72. 
    
73. void destroytree(BiTree *T) //递归销毁二叉树，即把包括头的全部节点释放，详见“https://blog.csdn.net/bzhxuexi/article/details/41721429”
    
74. {
    
75.         if(*T)
    
76.         {
    
77.                 if((*T)->lchild)
    
78.                 {
    
79.                         destroytree(&(*T)->lchild);
    
80.                 }
    
81.                 if((*T)->rchild)
    
82.                 {
    
83.                         destroytree(&(*T)->rchild);
    
84.                 }
    
85.                 free(*T);
    
86.                 (*T)=NULL; //空指针赋值0；
    
87.         }
    
88. }
    
89. 
    
90. int cleartree(BiTree *T) //清空树，即保留头结点，后面全部释放
    
91. {
    
92.         if(*T==NULL)
    
93.                 return 0;
    
94.         else
    
95.         {
    
96.                 cleartree(&(*T)->lchild);
    
97.                 cleartree(&(*T)->rchild);
    
98.                 free((*T));
    
99.                 return 1;
    
100.         }
     
101. }
     
102. 
     
103. int deeptree(BiTree T)  //求二叉树的深度，递归过程详见“https://blog.csdn.net/tackycheng/article/details/6445916”
     
104. {
     
105.         int deep=0;
     
106.         int ldeep,rdeep;  //左子树深度和右子树深度
     
107.         if(T==NULL)
     
108.                 return 0;
     
109.         else
     
110.         {
     
111.                 ldeep=deeptree(T->lchild);
     
112.                 rdeep=deeptree(T->rchild);
     
113.                 deep=ldeep>=rdeep?ldeep+1:rdeep+1;
     
114.                 return deep;
     
115.         }
     
116. }
     
117. 
     
118. int nodecount(BiTree T)
     
119. {
     
120.         int lnode,rnode,node;
     
121.         if(T==NULL)
     
122.                 return 0;
     
123.         else
     
124.         {
     
125.                 lnode=nodecount(T->lchild);
     
126.                 rnode=nodecount(T->rchild);
     
127.                 return (lnode+rnode+1);
     
128.         }
     
129. }
     
130. 
     
131. int leafcount(BiTree T)
     
132. {
     
133.         int lleaf,rleaf,leaf; //分别记录左右子树上的叶子结点总数以及叶子结点总数
     
134.         leaf=0;
     
135.         if(T==NULL)
     
136.                 return 0;
     
137.         else
     
138.         {
     
139.                 lleaf=leafcount(T->lchild);
     
140.                 rleaf=leafcount(T->rchild);
     
141.                 if(lleaf==0&&rleaf==0)
     
142.                         return 1;
     
143.                 else
     
144.                         return lleaf+rleaf;
     
145.         }
     
146. }
     
147. 
     
148. /*int leafcount(BiTree T)
     
149. { &nbsp;
     
150.         int count=0;
     
151.         if(T)
     
152.         {
     
153.                 if(T->lchild ==NULL &&T->rchild==NULL)
     
154.                         count++;
     
155.                 leafcount(T->lchild);
     
156.                 leafcount(T->rchild);
     
157.                 return count;
     
158.         }
     
159. }*/
     
160. 
     
161. char root(BiTree T) //若树存在，返回树的根。
     
162. {
     
163.         char e;
     
164.         if(T==NULL)
     
165.                 return 0;
     
166.         else
     
167.         {
     
168.                 e=T->data;
     
169.                 return e;
     
170.         }
     
171. }
     
172. 
     
173. 
     
174. 
     
175. 
     
176. 
     
177. 
     
178. 
     
179. 
     
180. 
     
181. 
     
182. 
     
183. 
     
184. 
     
185. 
     
186. 
     
187. int main()
     
188. {
     
189.         BiTree T;
     
190.         int deep;
     
191.         printf("请创建一棵二叉树：\n");
     
192.         inittree(&T);
     
193.         creattree(&T);
     
194.         //deep=deeptree(T);
     
195.         //printf("二叉树深度为%d\n",deep);
     
196.         //deep=nodecount(T);
     
197.         //printf("二叉树结点总数为%d\n",deep);
     
198.         deep=root(T);
     
199.         printf("二叉树根为%c\n",deep);
     
200.         //deep=leafcount(T);
     
201.         //printf("二叉树叶子结点总数为%d\n",deep);
     
202.         //destroytree(&T);
     
203.         //isemptytree(T);
     
204.         printf("该二叉树的前序遍历结果为：");
     
205.         preordertree(T);
     
206.         printf("该二叉树的中序遍历结果为：");
     
207.         inordertree(T);
     
208.         printf("该二叉树的后序遍历结果为：");
     
209.         postordertree(T);
     
210.         return 0;
     
211. }
     

复制代码

愿你

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: “&nbsp;”: 未声明的标识符
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的时候他的遍历结果也都是对的呀