引言
这篇文章将介绍二叉树基本实现的相关函数，希望能对你的复习有帮助
小技巧
首先以我们现在的知识是很难用函数的方式写一个二叉树出来的，所以我们可以先单独开一个源文件，专门用来创建二叉树，只是单纯的创建节点，然后把它们连接起来就可以了，想用的时候直接复制粘贴到程序里就可以直接使用了！就像这样：
二叉树的遍历
具体思路：
我们这里主要使用的是递归的思路，总的来说，二叉树很多函数的实现都要运用到递归的思路，这里我们先实现前序遍历，也就是 根–>左节点–>右节点 的顺序，当我们在访问一个节点时就先把该节点对应的值打印出来，然后再访问它的左节点，将左节点访问完后再访问右节点，这就是一个大体的思路
既然我们使用的是递归思路，那么我们就要找到递归结束的条件，我们提到了要访问左节点后再访问右节点，那翻译一下就是当左节点访问到空节点时就返回，然后访问右节点，这里给出一个流程图：
具体函数实现如下：
如果我们想实现中序遍历或者后序遍历，只需要将最后三行的代码的位置换一下就可以了
二叉树节点个数
具体思路：
这里也要用到递归的思路，一句话来总结就是
当前节点个数 = 左子树节点的总个数 + 右子树节点的总个数 + 1（自己本身）
然后同样的，我们要找出递归结束的条件，比较合理的就是，当我们访问到空指针时就返回函数，因为返回的类型是int，所以我们返回0
具体实现如下：
二叉树叶子的总个数
具体思路：
其实这里的实现思路与二叉树节点的总个数的实现是有很大相似之处的，只不过换成了
当前叶子总个数 = 左子树叶子的总个数 + 右子树叶子的总个数
那我们现在就要找到递归结束的条件，这里应该有两个：
1.当前节点就是空节点，直接返回0
2.当前节点的左节点和右节点都是空节点，那么就能证明此节点是叶子，返回1
那么到函数中我们具体该怎么写呢，我们应该把第二个判断条件放在第一个判断条件后面，因为如果当前节点就是空节点的话，是无法找到空节点的左节点和右节点的，程序运行会产生错误
具体实现如下：
二叉树第k层节点个数
具体思路：
这里虽然用的也是递归的思路，但是我们要将k与递归函数联系起来，首先我们可以将第一层看作第一层，毎递归一次我们就将下一层看作第一层，然后k-1，递归结束的条件就是k == 1，这里给出一张图：
然后得出节点个数的思路也与前面的几乎相同：
当前对应k层节点个数 = 左子树的k层节点个数 + 右子树的k层节点个数
当然对于递归结束的条件不只是k == 1，如果当前节点已经为空了，也会结束，与前面相同，我们要将判空的那个条件放在之前
当k == 1且当前节点不为空时就返回1，如果当前节点为空就直接返回0
具体实现如下：
二叉树高度
具体思路：
同样使用递归，但是与前面不相同的是，这里不是相加，而是选择，用一个表达式表达就是
当前节点高度 = 左子树的高度和右子树高度中更高的那一个 + 1（自身的高度）
这里我们有些同学可能会想到直接使用三目操作符，就像写成这样：
return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) : TreeHeight(root->right);
但是我要说的是，这样的实现原理是对的，但是对于整个函数来说，会大大的增加函数的时间复杂度，因为这里相当于要多算一次函数，所以为了节省计算时间，我们要先将这两个变量存起来
具体实现如下：
二叉树查找值为x的节点
具体思路：
这里我们可以运用前序遍历的思路，如果找到了相同的值就直接返回当前节点，如果左节点找完了就找右节点，右节点找完了都没有就结束
我们也要确定递归结束的条件，第一个条件就是找到了空节点，这样我们就返回空节点，第二个条件就是找到了符合此值的节点，直接返回节点就可以了
但是这里我们要主要返回值的方式，我们先将左节点存起来，如果左节点不是空节点就返回左节点，如果左节点是空节点就返回右节点存的节点，不同的是右节点不用提前存了，因为不管右节点是不是空节点都可以返回了
具体实现如下：
包含的库函数和函数声明
大家可以对照这里的函数声明进行自我练习实现
总结
目前来说，我们使用函数来创建二叉树和销毁二叉树等函数都是比较困难的，但是要掌握本篇文章的内容也是要好好学习的，特别是递归的思想，一定要多画图，加油加油！
评论（1）