这样求叶子结点数有错吗？,数据结构与算法,技术交流,鱼C论坛

愿你发表于 2018-4-25 09:55:31

这样求叶子结点数有错吗？

我明明已经定义了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;
}
}

BngThea 发表于 2018-4-25 10:32:55

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

愿你发表于 2018-4-25 10:35:36

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

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

BngThea 发表于 2018-4-25 10:48:23

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

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

愿你发表于 2018-4-25 10:59:05

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

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

intinittree(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;
}

愿你发表于 2018-4-25 11:00:13

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 发表于 2018-4-25 14:07:04

本帖最后由 ABC23 于 2018-4-25 14:09 编辑

问题出在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;
}

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

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

愿你发表于 2018-4-25 20:57:35

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

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

页: [1]

鱼C论坛's Archiver

这样求叶子结点数有错吗？