初阶数据结构 二叉树常用函数 （二）_根节点指针是非空指针吗

函数一 求二叉树叶节点的个数

这里要求我们统计叶节点的个数

我们想想 怎么统计呢？

还是老规矩 先上图

首先我们怎么判断叶节点呢？

如果这个节点它的左孩子和右孩子都是空指针

那么它就是一个叶节点

所以说当我们遇到左右节点都是空的时候返回一个一

核心代码表示如下

int BinaryTreeLeafSize(BTnode* root)
{
	// 判断极限值
	if (root==NULL)
	{
		return 0;
	}

	if (root->left==NULL && root->right==NULL)
	{
		return 1;
	}

	// 如果不是极限值怎么办 
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

接下来让我们测试下

可以完美运行

我们来看看节点个数是不是4

确实是4没错 下一题！

函数二 求二叉树第K层的节点个数

还是一样 我们假设 K就是等于一

如果说是一个空数的话就返回0

如果说有值的话就返回一个1就可以

假设这个这层既不为空 又不是第K层的话 那么就说明第K层肯定是子树下面

那么就说明是左右子树的第（K-1）层

那么只将它们相加并且返回它们的值就好了

核心代码表示如下

int BinaryTreeLevelKSize(BTnode* root, int k)
{
	// 极限情况 K=1
	if (root==NULL)
	{
		return 0;
	}

	if (k==1)
	{
		return 1;
	}

	// 说明这棵树的节点在root节点下面
	// 转化为求子节点的k-1节点问题 
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

我们来看看结果怎么样

符合预期

函数三 求二叉树的深度

这里还是一样 我们先来看图

我们先来看第极限的情况

假如我们的本身就是一个空树的话 我们可以直接返回0

如果不是空树的话我们可以寻找我们的左子树和右子树中的较大值（一样大返回哪一个都可以）

将它们加一后返回就可以

核心代码如下

int BinaryTreeHight(BTnode* root)
{
	// 极限情况
	if (root==NULL)
	{
		return 0;
	}

	// 后面的情况 
	int left = BinaryTreeHight(root->left);
	int right = BinaryTreeHight(root->right);

	return left > right ? left + 1 : right + 1;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

还是一样我们来看看效果

深度是4确实没错

函数四 求某个值为X的节点

还是一样 我们首先考虑极限情况

假设值就在根上

那么我们直接返回根的位置就好了

否则的话我们就往左边右边子树遍历

我们来看看核心代码

BTnode* BinaryTreeFind(BTnode* root, BTdate x)
{
	// 极限情况 
	if (root==NULL)
	{
		return NULL;
	}

	if (root->date==x)
	{
		return root;
	}


	// 找左子树
	BTnode* left = BinaryTreeFind(root->left, x);
	if (left)
	{
		return left;
	}

	// 找右子树
	BTnode* right = BinaryTreeFind(root->left, x);
	if (right)
	{
		return right;
	}

	// 都没找到
	return NULL;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

我们发现这里可以找出来了

以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够

不吝赐教 在评论区或者私信指正 博主一定及时修正

那么大家下期再见咯