数据结构之链式二叉树续

1.获取叶节点个数

获取叶子结点个数，我们这里也用递归的方法

利用分治思想去解决这个问题

●代码思想：

1. 当遇到空树或者遇到空的节点时，也就是说这是的叶子为NULL，这是我们返回0

2. 当遇到左节点或者右节点为空，当节点不为空时，此时已经到达了叶子结点，所以返回1

3. 当遇到的不是叶节点时，我们需要到递归左节点的个数和右节点的个数，并进行递归返回

●代码思想：

对于整棵树来说，当我们遇到空树或者遇到节点为空的时候，这时的叶子结点为空，我们这时返回0，当不是上中情况的时候，我们从根往下去搜索，先搜索左节点，当左节点不为空，并且左节点的左子树和右子树都是空的时候，这时候就可以确定它是叶子了，也就是返回1，当搜索完左子树就可以搜索右子树，右子树也同理 

2.获取树的高度 

获取树的高度，我们也是利用分治的思想去实现这个代码

首先就是当我们要想返回高度的时候，我们需要调用到左右子树的高度

然后比较左右子树的高度，比较出最大的一个并返回

然后加1（因为我们递归的是左右子树的高度，我们需要整个树的高度，所以还需要加上根，也就是加一）

●代码思想：

1.当我们遇到空树或者遇到的节点为NULL，这时返回0

2.然后接下来去递归左子树和右子树

3.返回时，如果左子树大于右子树，那么就是左子树高度+1，否则右子树高度+1

//获取树的高度
int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	TreeHeight(root->left);
	TreeHeight(root->right);

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

但这个代码有一定的缺陷

我们可以看到，这个代码我们调用了两次TreeHeight(root->left)和TreeHeight(root->right)

在这一树中，我们调用多次函数，大大增加了计算的难度，在一棵小树中可能不明显，可当树更大时，这时候弊端就先显示出来了

所以我们可以改进一下代码，定义两个变量去接受返回值

然后比较两个返回值

//改进代码
int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	/*TreeHeight(root->left);
	TreeHeight(root->right);

	return (TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) : TreeHeight(root->right)) + 1;*/
	int Heightleft = TreeHeight(root->left);
	int Heightright = TreeHeight(root->right);

	return (Heightleft > Heightright ? Heightleft : Heightright + 1);
}

3.计算第K层节点个数 

计算k层节点的个数，我们可以看成计算左节点的（k-1）层和右节点（k-1）层的节点个数

因为我们不算顶部节点所以应该是k-1

●代码思想：

首先是如果是空树或者当遇到叶子结点外的空节点时，返回0

当遇到k为1的时候，这时只有一个根，也就返回1

其余情况均利用递归思想，去递归左右子树，注意此时的k应该变成k-1

//计算树k层的节点个数
int TreeKCount(BTNode* root, int k)
{
	if (root == NULL || k < 1)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeKCount(root->left, k - 1) + TreeKCount(root->right, k - 1);
}

4.寻找某个节点 

寻找某个节点的话，我们也利用递归的方法，分治的思想去解决这个问题

寻找某个节点，那么这个节点如果不在根上，那么就在根的左子树和右子树上

那么就想下寻找

下边的节点也可以分为左子树和右子树和根

依次进行，就形成了递归

//寻找某个节点
BTNode* TreeFind(BTNode* root, int x)
{
	if (root == NULL)
	{
		return 0;
	}
	if (x == root->val)
	{
		return root;
	}
	TreeFind(root->left, x);
	TreeFind(root->right, x);
    return NULL;
}

很多人可能会想到这样的代码

可当我们去运行的时候，我们会发现找不到，不管x为多少都找不到

为什么呢？

原因是我们没有东西去接收

当我们找到的时候，我们递归需要往上递归

可上边的栈中没有可以接受的变量值

所以我们最终遍历完整棵树也找不到我们想找的节点

所以改一下代码

//寻找某个节点
BTNode* TreeFind(BTNode* root, int x)
{
	if (root == NULL)
	{
		return 0;
	}
	if (x == root->val)
	{
		return root;
	}
	BTNode* ret1 = TreeFind(root->left, x);
	BTNode* ret2 = TreeFind(root->right, x);
	if (ret1)
		return ret1;
	if (ret2)
		return ret2;
	return NULL;
}

这样我们利用新建立的节点去接受我们的左右子树的数据

然后如果不为空就不断返回，为空那么就返回0