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++;//根节点+1TreeSize(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)++;//根节点+1TreeSize(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);
}