107.【C语言】数据结构之二叉树求总节点和第K层节点的个数
目录
1.求二叉树总的节点的个数
1.容易想到的方法
代码
缺陷
思考:能否在TreeSize函数内定义静态变量解决size的问题呢?
其他写法
运行结果
2.最好的方法:分而治之
代码
运行结果
2.求二叉树第K层节点的个数
错误代码
运行结果
修正
运行结果
其他写法
1.求二叉树总的节点的个数
1.容易想到的方法
借助103.【C语言】数据结构之二叉树的三种递归遍历方式文章的遍历函数的思想
以前序遍历函数的思想为例
void PreOrder(BTNode* root)
{
//先判断是否为空树(叶节点的左节点和右节点均为空树)
if (root == NULL)
{
printf("NULL ");
return;
}
//按根-->左子树-->右子树的顺序遍历
printf("%d ",root->data);
PreOrder(root->left);
PreOrder(root->right);
}设计TreeSize函数,设size存储二叉树的总的节点的个数,由于局部变量在函数返回时会发生销毁,显然应该使用全局变量size,在main函数外部写int size;(默认初始值为0)
代码
#include "Tree.h"
int size;
void TreeSize(BTNode* root)
{
if (root == NULL)//为NULL,则返回,不+1
{
return;
}
size++;//根节点+1
TreeSize(root->left);
TreeSize(root->right);
}
int main()
{
BTNode* root = CreateTree();
TreeSize(root);
printf("TreeSize==%d", size);
return 0;
} 备注:CreateTree建立的是下面这棵二叉树
递归的思想和103.【C语言】数据结构之二叉树的三种递归遍历方式文章相同,不再赘述
运行结果
缺陷
本方法有缺陷,当多次调用时必须手动为size置0
若像下面这样不置0
int main()
{
BTNode* root = CreateTree();
TreeSize(root);
printf("TreeSize==%d\n", size);
TreeSize(root);
printf("TreeSize==%d\n", size);
TreeSize(root);
printf("TreeSize==%d\n", size);
return 0;
} 运行结果会出错
每一次调用前必须手动置0,像下面这样
int main()
{
BTNode* root = CreateTree();
TreeSize(root);
printf("TreeSize==%d\n", size);
size = 0;
TreeSize(root);
printf("TreeSize==%d\n", size);
size = 0;
TreeSize(root);
printf("TreeSize==%d\n", size);
return 0;
} 思考:能否在TreeSize函数内定义静态变量解决size的问题呢?
答:不可以,理由1:无论函数调用多少次,写在函数内的静态变量只会被初始化一次,即第二,三,四,...次调用不会初始化.理由2:在函数外部无法访问静态变量
其他写法
TreeSize多传一个参数
#include "Tree.h"
void TreeSize(BTNode* root,int* psize)
{
if (root == NULL)//为NULL,则返回,不+1
{
return;
}
(*psize)++;//根节点+1
TreeSize(root->left, psize);
TreeSize(root->right, psize);
}
int main()
{
BTNode* root = CreateTree();
int size1 = 0;
TreeSize(root, &size1);
printf("TreeSize==%d\n", size1);
int size2 = 0;
TreeSize(root, &size2);
printf("TreeSize==%d\n", size2);
int size3 = 0;
TreeSize(root, &size3);
printf("TreeSize==%d\n", size3);
return 0;
}运行结果
2.最好的方法:分而治之
形象说法:找"下属"分担任务(递归),让"下属"帮忙计数,"下属"统计好个数交给"上司"(此方法不用定义size)
递推:根将任务交给左子树和右子树,左子树和右子树将任务分别交给它们的左子树和右子树,左子树和右子树将任务分别交给它们的左子树和右子树...一直到空树结束
代码
int TreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return TreeSize(root->left) + 1 + TreeSize(root->right);//+1加的是自己本身
}
int main()
{
BTNode* root = CreateTree();
printf("TreeSize=%d\n", TreeSize(root));
printf("TreeSize=%d\n", TreeSize(root));
printf("TreeSize=%d\n", TreeSize(root));
return 0;
}运行结果
可见无论TreeSize被执行多少次,打印的结果都是一样的,从而避免了要将size置为0的问题
2.求二叉树第K层节点的个数
分析:比如求下图K=3层的节点个数,按递归思想分析
递推:关键点:要以不同的视角来看待第K层
求K层-->求根节点的左右子树的第K-1层-->求根节点的左右子树的第K-2层-->...-->求根节点的左右子树的第1层
由上述分析可知TreeLevel函数需要BTNode* root和int k两个参数,这里k必须大于0(assert(k>0);)
错误代码
int TreeLevel(BTNode* root, int k)
{
assert(k>0);
if (root == NULL)
{
return 0;
}
int lnum = TreeLevel(root->left, k - 1);
int rnum = TreeLevel(root->right, k - 1);
return lnum + rnum;
}
int main()
{
BTNode* root = CreateTree();
printf("TreeLevel=%d", TreeLevel(root, 3));
return 0;
}运行结果
运行结果显然是有问题的,怎么修正?
修正
错误原因:考虑其一没有考虑其二,if判断处一直返回0,没有返回1的情况,导致0+0+...+0==0
if (root == NULL)
{
return 0;
}TreeLevel返回有两种情况:1.根节点为NULL 2.k==1
修改后
int TreeLevel(BTNode* root, int k)
{
assert(k>0);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
int lnum = TreeLevel(root->left, k - 1);
int rnum = TreeLevel(root->right, k - 1);
return lnum + rnum;
}运行结果
结果正确
其他写法
不用变量存储,直接返回相加的值
int TreeLevel(BTNode* root, int k)
{
assert(k>0);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return TreeLevel(root->left, k - 1) + TreeLevel(root->right, k - 1);
}