文章目录
引言
在大家期末考试和笔试甚至面试中，数据结构作为必考的内容，而二叉树是数据结构中一个很重要的概念，在计算机科学中占据重要地位，根据这段时间的学习，我总结了二叉树中重要的考点和对应的解题方法。
二叉树的性质
首先复习巩固一下二叉树的基础知识内容——二叉树的性质
性质一 结点数与层数的关系
在二叉树的第 i 层上
最多有个结点（i >= 1)。
性质二 结点数与层数的关系
深度为 k 的二叉树
最多有个结点。
性质三 叶子节点与度为2的节点关系
对于任何一棵二叉树 T，如果这棵树的终端结点数为n0（也就是叶子结点的个数为 n0），若度数为 2 的结点数为 n2
则n0 = n2 + 1
性质四 深度与节点数的关系
具有 n 个结点的完全二叉树的的深度为
两种特殊的二叉树
满二叉树
若一颗二叉树有 k 层，并且这颗树共有个结点，或者该树对应的第 i 层(包括最后一层)共有个结点，则该树就为满二叉树。满二叉树中除了叶子结点没有子结点，其他结点都有左右两个结点。
例如上图这个二叉树结构，该树有 3 层，结点数为 (2^3) - 1 = 7
完全二叉树
完全二叉树的定义是：除了最后一层外，每一层都被完全填满，并且所有结点都尽可能地向左对齐。这种结构意味着，在完全二叉树中，除了最后一层可能不完全填满外，其他层都是完全填满的。
以上两个树结构都是完全二叉树结构，它们除了最后一层(第三次)以外其他层都被完全填满。
二叉树的遍历顺序
在笔试中二叉树遍历方式的考察主要是三种：前序遍历（根 - 左 - 右）、中序遍历（左- 根 - 右）、后序遍历（左- 右- 根）。 这些遍历方式定义了访问树中每个结点的顺序，接下来将对这三种遍历方式做出介绍。
前序遍历
在前序遍历中，需要遵循“根节点-左子树-右子树”的顺序来访问结点。具体来说，对于树中的任意节点，我们首先访问该节点，然后递归地进行前序遍历其左子树，最后递归地进行前序遍历其右子树。
算法步骤：
1.访问根节点。
2.前序遍历左子树。
3.前序遍历右子树
中序遍历
在中序遍历中，需要遵循“左子树-根节点-右子树”的顺序来访问结点。这种遍历方式在二叉搜索树中特别有用，因为它会按照升序访问树中的所有节点。
算法步骤：
1.中序遍历左子树。
2.访问根节点。
3.中序遍历右子树。
后序遍历
在后序遍历中，需要遵循“左子树-右子树-根节点”的顺序来访问结点。即首先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。
算法步骤：
1.后序遍历左子树。
2.后序遍历右子树。
3.访问根节点。
常考内容及详细解法
题型一、基本概念与性质
这类题型基本都是考察一个人对二叉树性质的理解和掌握情况，想要顺利求解出这类题目的结果，需要熟练掌握上文中所提到的几个二叉树性质！ 下面通过例题来牢固对二叉树性质的理解和应用。
题目内容
一个完全二叉树有1001个结点，那么这棵树的叶子结点个数是多少（）？
A.250 B.500 C.254 D.501
首先画一幅完全二叉树的结构图便于后面方法介绍的理解
方法一
我们知道一颗二叉树的结点数是与该树的层数相关联的，若一颗树有 k 层，那么这棵树最多有
2^9 = 512
2^10 = 1024 而 512 < 1001 < 1024
所以这颗完全二叉树有10层
接着利用该性质可以得到前 9 层的结点数为 （2^9）- 1 = 511 个
那么第十层上的叶子结点个数为 1001 - 511 = 490
由性质一：在二叉树的第 i 层上最多有
.
因为这颗完全二叉树前面几层都已经被完全填满了，除了第十层以外都满足第 i 层上有
.
然后 通过第十层上叶子结点的个数求出第九层上的非叶子节点个数
490 / 2 = 245
由此得到第九层上叶子结点的个数就是（该层的结点个数 - 非叶子结点个数） 256 - 245 = 11个
最后得出最终的叶子结点个数就是 第十层上的叶子结点加上第九层上的叶子结点 = 490 + 11 = 501.
总结：
方法二
通过使用二叉树的性质三来求解
我们设二叉树中度为0的结点个数为 n0，度为1的结点个数为 n1，度为2的结点个数为n2，
所以 n0 + n1 + n2 = 1001
性质三中可以得到等式 n0 = n2 + 1
由这两个等式可以得到 n0 + n0 + n1 = 1002
.
由于 n1 只能为 0 或 1 所以可以将两个值分别带入 n1 中进行检验 n0 的结果
①当 n1 = 1时 可以得到 n0 = 500.5 结点的个数一定为整数所以这个结果是错误的
②当 n1 = 0时 可以得到 n0 = 501 ✔ 这个就是最后的正确结果
题型二、二叉树遍历方式
在这一类题型中的考察方法主要是给出前序、中序遍历的结点顺序推出后序遍历的结点顺序，或者是给出后序、中序便利的结点顺序退出前序遍历的结点顺序。
例一
已知二叉树后序遍历序列是 bfegcda，中序遍历序列是 badefcg，它的前序遍历序列是（）:
A. abcdefg
B. abdcefg
C. adbcfeg
D. abecdfg
常规解法比较繁琐，单纯使用文字表达不是很方便，所以下面主要介绍的是一种使用技巧的方法来解决这类题目。
解题方法
首先我们在草稿纸上将对应遍历顺序的结点序列画成类似图标的形式，如下图所示
在这里需要注意的是：
中序遍历的结点序列按照原来的序列顺序写在下面，前序遍历也按照原结点序列的顺序依次竖着写下来，写在左侧，后序遍历需要逆序依次竖着写在左侧，就像上面这道题，已知后序遍历为 bfegcda，那么他的逆序就是 adcgefb ，按照这个顺序依次竖着写在左侧，最后写出来就是上图这样。
接下来在横竖坐标下，将相同结点在对应位置写下来，如下图所示，然后对这几个新画出来的结点进行连线，这样就得到了该二叉树的结构。
连线
需要从上到下按照每一层的顺序进行连线！
这样其实就可以根据前序遍历的遍历顺序得到前序遍历的结果，为了方便理解我重新画出一幅该二叉树的结构如下图。
按照根节点-左子树-右子树”的顺序访问结点得到前序遍历结果为：abdcefg
例二
若已知一棵二叉树的先序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是什么？画出该二叉树。
结果为：
后序遍历序列：FEGHDCB
首先在纸上写出对应的遍历顺序的结点序列，例二中给出的是先序(前序)遍历的序列，所以左侧是按照该顺序序列直接写出，如下图所示
接下来在对应两种不同遍历顺序的结点序列中对应相同的坐标下画出该结点。得到如下图所示。
得到二叉树的结构以后想要什么样的遍历顺序序列都一目了然了！
总结
总结
这篇文章主要是根据我个人最近准备秋招时，在二叉树内容方面的整理总结。
标签：结点,遍历,前序,note,顺序,二叉树,Learning,节点 From： https://blog.csdn.net/m0_63650113/article/details/140605580