《二叉树》——2

目录

前言：

树的节点个数：

树的叶子节点个数：

树的高度:????????

树的第K层节点个数：

?二叉树查找值为x的节点:

?二叉树的销毁：

总结：

---

前言：

我们在之前的blog中对于前中后的遍历有了深层次的了解，相信通过递归展开图能更好的对递归算法有更深的理解，接下来我们将对剩下的二叉树内容进行补充，内容包含《树的节点个数》《树的叶子节点个数》《树的高度》《树的第K层节点个数》《二叉树查找值为x的节点》《二叉树的销毁》

上一篇blog：《二叉树》——1-CSDN博客

?

树的节点个数：

int TreeSize(TreeNode* root)//树的节点个数
{
	return (root == NULL) ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

也可以写成：

int TreeSize(TreeNode* root)//树的节点个数
{
    if (root == NULL)
    {
        return 0;
    }
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

我们在分析递归问题的时候一定要清楚“分治子问题”和“返回条件 ”。

对于这一个函数而言，我们可以理解为：

左子树的节点数 + 右子树的节点数 + 1（根节点）

同时当我们的root指针访问到NULL时要选择返回！

?

树的叶子节点个数：

首先先复习一下什么是叶子节点，

叶节点或终端节点：度为0的节点称为叶节点

节点的度：一个节点含有的子树的个数称为该节点的度

int TreeLeafSize(TreeNode* root)//树的叶子节点个数
{
	if (root == NULL)
		return 0;

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

	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

?我们首先还是需要了解此函数的“分治子问题”以及“返回条件”

“左子树叶子节点数” + “右子树叶子节点数”

条件有：

1、空树返回0

2、叶子节点返回1（root->left == NULL && root -> right == NULL）

树的高度:????????

int TreeHeight(TreeNode* root)//树的高度
{
	if (root == NULL)
		return 0;

	int LeftHeight = TreeHeight(root->left);
	int RightHeight = TreeHeight(root->right);

	return (LeftHeight > RightHeight) ? (LeftHeight + 1) : (RightHeight + 1);
}

首先我们依然需要进行回顾，什么是高度？

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次

综上我们不难发现，所谓的高度，就是对左子树和右子树的高度进行比较，取最大的高度+根节点（即+1）即可，因为根节点是第一层。

同时我们要注意的是，切勿写成以下这种：

int TreeHeight(TreeNode* root)//树的高度
{
	if (root == NULL)
		return 0;

	return (TreeHeight(root->left) > TreeHeight(root->right)) ? (TreeHeight(root->left) + 1) : (TreeHeight(root->right) + 1);
}

这个代码的逻辑没有问题，但是问题就出现在每次比较的时候都要进行多次递归操作，多次开辟建立函数栈帧，数据一旦大或者较为难处理时往往会发生“栈溢出”

因此我们需要向第一次的代码那样定义两个变量来接受左子树的高度和右子树的高度。

?

树的第K层节点个数：

int TreeK(TreeNode* root, int k)//树的第K层节点个数
{
	if (root == NULL)
		return 0;
	if (root != NULL && k == 1)
		return 1;

	return TreeK(root->left, k - 1) + TreeK(root->right, k - 1);
}

还是一如既往找出“分治子问题”和“返回条件”

1、root为空时，返回0

2、若root不为空时，k == 1时返回1

这里提供一个思路，如图：

?

?

?以上就是下面代码的由来

return TreeK(root->left, k - 1) + TreeK(root->right, k - 1);

?二叉树查找值为x的节点:

TreeNode* TreeFind(TreeNode* root, BTDataType x)// 二叉树查找值为x的节点
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;

	TreeNode* tmp1 = TreeFind(root->left, x);
	TreeNode* tmp2 = TreeFind(root->right, x);

	if (tmp1)
		return tmp1;
	if (tmp2)
		return tmp2;
	return NULL;
}

该函数与刚刚所讲的大相径庭

对于“分治子问题”不难得出

1、若是空则返回空

2、若root -> data = x则返回root

同样也是先在左子树中找，再在右子树找，这里一样也是定义一个临时变量来接受递归下来的返回值。

若tmp1 和tmp2均为NULL则代表没找到相应的节点，直接返回NULL

?

?二叉树的销毁：

void TreeDestory(TreeNode* root)// 二叉树销毁
{
	if (root == NULL)
		return;


	TreeDestory(root->left);
	TreeDestory(root->right);
	root->left = root->right = NULL;
	free(root);
}

对于上面的铺垫和讲解，相信对于销毁函数也不难理解。

同样也是先销毁左子树再去销毁右子树，最后当左右子树都销毁完后只剩下了一个根节点，则最后我们只需要将根节点进行释放和另左右指针指向空。

总结：

以上就是我们对于二叉树的链式结构的基本功能的实现了，其中设计许许多多的递归算法思想，对于刚开始的递归学习我们还需要不断学习和磨炼，思路最需要先锻炼出来，需要把分治子问题想清楚，

刚开始思路绕不明白的可以看看我以前写的一篇关于汉诺塔问题的blog：利用递归详解《汉诺塔游戏》_ucode汉诺塔游戏-CSDN博客

下节内容我们将涉及二叉树的层序遍历，利用栈来实现，希望大家可以继续坚持下来在二叉树的学习中。?