你好，我是王健伟。
前面讲解过的线性表，是以线性结构来组织数据的，数据之间只是简单的前后次序关系。但问题在于，线性结构对数据的组织结构过于单一，对于数据的访问速度也过于缓慢，在一些复杂的应用领域中，这种简单的线性结构不足以表达问题。
这个时候，我们就要引入“树形结构”这个概念了。
树形结构的应用场合非常多，比如计算机某块硬盘下的目录结构、一个公司的组织架构划分、一个家族的族谱等等。在计算机领域，树形结构也被广泛应用，比如编译器、数据库里都会用到，也因此，树形结构非常重要。而在众多树形结构中，最常用的一种，就是二叉树了。
树形结构的基本概念
在日常生活中，树是一种随处可见的植物，它由树根、树枝、树叶这些主要结构组成。而“树形结构”，就是基于日常生活中的树而得名的一种非线性数据结构。
什么是“非线性的数据结构”？想象一下，一根树枝可以分叉出很多树枝、树叶，我们也可以将“非线性的数据结构”理解成一种一对多的关系，而不是像一条线一样，按顺序排列的一对一关系。
在绘制树这种数据结构时，人们往往会从上向下绘制，也就是将树根绘制在最上面，图1就是一棵树：
在这幅图中，所有标有字母的圆圈就是树的节点。树（Tree）是n（n≥0）个节点的有限集。这里有了一个限定范围，n≥0。你可以尝试想象几种不同的情况，比如n=0，n=1，以及n>1这三种。
当n=0时，树就是一棵空树。如果树为非空，那么就会有两种情况。一种，就是n=1的时候，有且只有唯一一个称为根/树根（Root）的节点；另一种，就是n>1时，其余节点可以分为m（m>0）个互不相交的有限集T1、T2、…、Tm，其中每个集合自身又是一棵树，它们叫做根的子树（SubTree）。而节点A就是树根/根节点，注意，一棵树可以只有树根而没有其他节点。
子树的概念比较难理解，我们举个例子。图1中，B、D、E、F、H、I、J、K，也就是左半边，构成了以B为根节点的子树。
根据树的定义：有限集T1由B、D、E、F、H、I、J、K构成。C、G，也就是右半边，构成了以C为根节点的子树。根据树的定义：有限集T2由C、G构成。
子树，又可以看成是由更多更小的、互不相交的子树构成，所以我们也把树称为是一种递归定义的数据结构。如果树中节点的各子树从左到右是有次序的、不能互换的，则称该树为有序树，否则就叫做无序树。
注意，如果子树存在，那么子树之间不能相交，比如图2所列的情形就不是一棵树，节点E和F之间以及节点G和K之间都不应该有连线：
树的节点包含一个数据元素以及若干指向其子树的分支（分支也可以称为指针或索引），这里会经常用到一些概念，我们先来预习一下这些内容。这些概念不需要死记硬背，只需要理解就好，将来忘记了可以随时来回顾。
- 节点拥有的子树的个数，叫做节点的度（Degree），比如图1中节点A的度是2，节点B的度为3，节点C的度为1。
- 如果度为0，那么这个节点就叫做叶节点（Leaf）或终端节点，图1中节点H、I、J、K、G节点都是叶节点。相反，度不为0的节点称为分支节点或非终端节点。除根节点外的分支节点也称为内部节点。
- 树的度是树内各节点度的最大值，图1中节点B或者节点D的度都为3，是节点度的最大值，因此，树的度也是3。
- 节点的子树的根称为该节点的子节点（Child），图1中节点A的子节点是节点B、C，而节点B的子节点是节点D、E、F。同样，节点B、C的父节点（Parent）就是节点A，节点D、E、F的父节点就是节点B。
这里注意，某个节点只能有一个父节点，在图2中，节点E和节点F之间有连线，那么节点B和节点E都可以被认为是节点F的父节点；节点G和节点K之间有连线，那么节点F和节点G都可以被认为是节点K的父节点。因此图2是一个非法的树，这种数据结构应该称为图（后面会讲）。注意，根节点没有父节点。
- 节点的层次（Level）是从树根开始算起的，根为第一层，根的孩子为第二层，以此类推，某个节点位于第i层，其子树就位于第i+1层。图1中节点A为第一层，节点B、C为第二层，节点D、E、F、G为第三层，节点H、I、J、K为第四层。树的高度或深度（Depth）是树中节点最大层数，因此图1树的深度是4。
- 相同父节点的孩子之间互称兄弟节点（Sibling），比如D、E节点是兄弟节点，H、I节点也是兄弟节点。层次相同但父节点不同的孩子之间互称堂兄弟节点，比如图1中节点F与节点G，节点J与节点K。
二叉树的基本概念
树的结构多种多样，对树的操作也各不相同，但最常用是二叉树，因为大部分树都可以转换为二叉树。
那什么是二叉树呢？二叉树的特点是每个节点最多有两棵子树（左子树和右子树），这意味着每个节点的度都不大于2。它的两棵子树有左右之分。想象一下，人的脚是分左右的，右脚不能穿左侧的鞋，和二叉树两棵子树的左右之分是一个道理。另外，次序也是不能随意颠倒的，这表明二叉树是一棵有序树。
这里，我们给二叉树下一个明确的定义：二叉树是n（n≥0）个节点的有限集合，该集合或者为空集（即n=0，叫做空二叉树），或者由一个根节点和两个互不相交的该根节点的左子树和右子树构成，左子树和右子树又分别是一棵二叉树。
除空二叉树外，图3列出了其他四种形态的二叉树，分别是只有根节点的二叉树、只有左子树的二叉树、只有右子树的二叉树、既有左子树又有右子树的二叉树。
注意，即使只有一棵子树，我们依然要区分是左子树还是右子树，所以图3中只有左子树的二叉树和只有右子树的二叉树是两棵不同的二叉树。
你可以思考一下，有三个节点的二叉树会有几种形态呢？答案是有5种形态，如图4所示，你答对了吗？
特殊二叉树
二叉树有一些特殊的形态在后面会经常被提到或者用到，这里我先带你认识一下满二叉树、完全二叉树以及斜树。
满二叉树
图5就是一棵满二叉树：
观察图5，我们先说下满二叉树有什么特点。
- 所有的分支节点都存在左子树和右子树（非叶节点的度一定是2）。
- 所有的叶子都在同一层上（这也意味着叶节点只能出现在最下一层）。
- 不存在度为非0和非2的节点。
可以看到，满二叉树看上去是很平衡的。在同样高度的二叉树当中，满二叉树一定是节点个数最多，叶子数最多的二叉树。
那要怎么去定义“满二叉树”呢？观察一下，图5中，第一层有1个节点，第二层有2个节点，第三层有4个节点，第四层有8个节点，所以总共的节点数为1+2+4+8=15个，即$2^{4}$-1个。
由此，我们可以给出满二叉树的定义：满二叉树是指一棵高度为h，且含有$2^{h}$-1个节点的二叉树。
最后，我们说一下编号的特点。按照图5的顺序给每个满二叉树的节点从上到下从左到右进行编号，比如图中的1-15，不难发现，编号为i的分支节点，它的左孩子的编号为2i，右孩子的编号为2i+1。如果节点i存在父节点，则其父节点的编号是i/2的结果，如果没整除，那么去掉小数部分即可。
完全二叉树
完全二叉树理解起来有一点难度。我们先看图，图6就是一棵完全二叉树。
观察图6，想一想，完全二叉树有什么特点呢？
- 叶节点都在最底下两层。
- 最后一层的叶节点都靠左侧排列（左侧连续），并且除最后一层，其他层的节点个数都要达到最大。
- 倒数第二层如果有叶节点，则叶节点都靠右侧排列（右侧连续）。
- 如果节点度为1，则该节点只有左子树，不可以只有右子树。而且最多只有一个度为1的节点。
可以看到，满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满二叉树。
现在，我们可以借助满二叉树的概念，给出完全二叉树的定义：一棵高度为h的完全二叉树，当且仅当其每个节点都与高度为h的满二叉树中编号为1~n的节点一一对应时，称为完全二叉树。
按照图6的顺序，我们给每个完全二叉树的节点从上到下从左到右进行编号，不难发现，编号为i的分支节点，其左孩子的编号为2i，右孩子的编号为2i+1。如果节点i存在父节点，则其父节点的编号是i/2的结果，如果没整除则去掉小数部分。
按照图6的顺序给每个完全二叉树的节点从上到下从左到右进行编号，随便拿出一个节点比如编号为9的节点，会发现该节点是编号为4的节点的右子树。此时观察图5这棵满二叉树，会发现，编号为9的节点与图6编号为9的节点位置完全相同，并且同样是编号为4的节点的右子树。
图7所示的几棵二叉树就都不是完全二叉树：
图7中第一棵树的节点5缺少左子树（编号10），第二棵树的节点3缺少两棵子树（编号6、7），第三棵树的节点5缺少两棵子树（编号10、11）。
所以，如何判断是否是完全二叉树，就可以按照下面的步骤去做。
- 在看到一棵树后，按照满二叉树的情形给该二叉树的节点进行逐层按顺序编号，如果编号出现了空缺，就不是完全二叉树，否则就是完全二叉树。
- 一棵满二叉树，依次把编号最大的1到多个节点去掉（比如去掉图5的15、14、13节点），得到的就是一棵完全二叉树。
- 如果一个完全二叉树有n个节点，那么当“节点的编号”≤(n/2)时，这些节点就是分支节点，而当“节点的编号”>(n/2)时，这些节点就是叶节点。注意，n/2如果没有整除则去掉小数部分。
斜树
所有节点都只有左子树的二叉树叫左斜树。所有节点都只有右子树的二叉树叫右斜树。这两种树统称斜树。
斜树的特点是每一层只有一个节点，节点个数与二叉树深度相同。这种树看起来更像线性表。图4中第2棵是左斜树，第5棵树是右斜树。
二叉树的性质
在对二叉树进行编码过程中，尤其是涉及开辟多少空间保存数据的时候，往往会用到二叉树的性质。我们一个一个来说。
- 性质一：在二叉树的第i层上，最多有$2^{i-1}$个节点（i≥1）
满二叉树可以认为是第i层上节点最多的二叉树了。观察图5并回忆一下满二叉树的定义——满二叉树是指一棵高度为h，且含有$2^{h}$-1个节点的二叉树。图5中，第一层有1个节点，第二层有2个节点，第三层有4个节点，第四层有8个节点，满足二叉树的性质一。
- 性质二：高度为k的二叉树至多有$2^{k}$-1个节点（k≥1）
满二叉树可以认为是有最多个节点的二叉树了。图5的满二叉树的高度为4层，第一层有1个节点，第二层有2个节点，第三层有4个节点，第四层有8个节点，总共的节点数为1+2+4+8=15个，即$2^{4}$-1个节点，满足二叉树的性质二。
- 性质三：二叉树节点的总数量等于节点的总度数+1
观察一棵二叉树不难发现，除根节点外，每个节点头上都有一个分支/树枝（每个节点都有一个父节点），那么一棵二叉树节点总数量其实就是这些分支的总数量+1，之所以+1，是因为根节点头上没有分支。一棵二叉树节点的总度数，其实就是每个节点头上分支的总数量，所以得出性质三的结论：二叉树节点的总数量 = 节点的总度数 + 1。
- 性质四：对任何一棵二叉树，如果其叶节点数量为$n_{0}$，度为2的节点数量为$n_{2}$，则叶节点的数量比有两棵子树的节点数量多一个，即：$n_{0}$=$n_{2}$+ 1。
观察图5的满二叉树或图6的完全二叉树以及图7的非完全二叉树，除了叶节点（度为0），其他的节点度数要么为1要么为2，如果假设度为1的节点数量是$n_{1}$，那么该二叉树的节点总数量n = $n_{0}$ + $n_{1}$ + $n_{2}$。
再算一算节点的总度数，节点的总度数应该等于2度节点数量*2+1度节点数量*1，因此，节点的总度数 = 2$n_{2}$ + $n_{1}$。
再根据性质三，节点的总数量 = 节点的总度数 + 1，就有：
节点总数量n = 2$n_{2}$ + $n_{1}$+ 1。
结合刚才的节点总数量式子，可以得到：$n_{0}$ + $n_{1}$ + $n_{2}$ = 2$n_{2}$ + $n_{1}$+ 1。
两边同时减少一个$n_{1}$和一个$n_{2}$，不难得到：$n_{0}$ = $n_{2}$+ 1，得出了性质四的结论。
试想一下，如果有一个完全二叉树，知道了其节点总数n，那么如何求出$n_{0}$（叶节点数量）、$n_{1}$（度为1的节点数量）、$n_{2}$（度为2的节点数量）的值呢？
首先，完全二叉树最多只有一个度为1的节点，即$n_{1}$= 0或者$n_{1}$= 1。
其次，根据前面的公式n = 2$n_{2}$ + $n_{1}$+ 1。该公式中的2$n_{2}$+ 1的结果肯定是奇数（不能被2整除的整数）。
那么，如果该完全二叉树节点总数是偶数（能够被2所整除的整数）个，那么$n_{1}$必定是奇数也就是值1。如果该完全二叉树节点总数是奇数，那么$n_{1}$必定是偶数也就是值0。
最后，n值已知，$n_{1}$值上步已推出，根据公式n = 2$n_{2}$ + $n_{1}$ + 1，$n_{2}$值就可以求得。再根据性质4的$n_{0}$= $n_{2}$+ 1，$n_{0}$的值就可以求得。
- 性质五：具有n（n>0）个节点的完全二叉树的高度为⌈$log_{2}^{(n+1)}$⌉ 或者 ⌊$log_{2}^{n}$⌋ +1。
这里要注意：
第一，符号⌈X⌉表示向上取整，也就是比X大的最小整数。如果X本身是整数，那么⌈X⌉就等于本身。
第二，符号⌊X⌋表示向下取整，也就是比X小的最大整数。如果X本身是整数，那么⌊X⌋就等于本身。
我们先来看一看第一个式子是如何推导的：
再看一看第二个式子是如何推导的。
所以，不妨扩展一下性质五：一个完全二叉树的第k的节点的高度为⌈$log_{2}^{(k+1)}$⌉ 或者 ⌊$log_{2}^{k}$⌋ +1。
- 性质六：如果对一棵有n个节点的完全二叉树的节点按层从1开始编号（从上到下从左到右编号，如图6），对任意节点i（1≤i≤n），有：
如果i=1，则节点i是二叉树的根，无父节点，如果i>1，则其父节点编号是⌊i/2⌋。
如果 2i>n，则节点i为叶子节点（无孩子节点），否则，其左孩子是节点2i。
如果2i+1>n，则节点i无右孩子（但可能有左孩子），否则其右孩子是节点2i+1。
小结
因为你可能初次接触树这种数据结构，所以这节课的内容就说这么多。
这节课，我们尝试描述了树形结构，也给出了许多和它相关的基本概念，其中比较重要的概念是树根、子树、节点的度，叶节点、子节点、父节点、兄弟节点、树的高度这几个部分。
之后引入了二叉树的概念。可以说，二叉树在树形结构中最常用，所以本节以及后面课节都会用很多篇幅讲述二叉树相关的知识。这节课我们将重点放在了认识各种形态的二叉树上，比如理解满二叉树、完全二叉树、斜树的概念。
最后，则是二叉树性质的学习。也许你会觉得这些性质离实际应用太过遥远，但其实它对于后面编写程序时决定内存空间分配多少、二叉树的高度和节点数量如何计算以及如何寻找某个节点的父或子节点等都具有重要的指导意义，这一点在后续编写代码时你会越来越清楚。
当然，这些性质不要死记硬背，理解性记忆即可，后面的课节中编程时会偶尔用到二叉树的性质。如果你忘记了这些性质，随时复习一下本节内容也就可以了。
课后思考
“度为2的有序树”与“二叉树”的区别是什么？
欢迎你在留言区和我探讨。如果你觉得有所收获，也可以把课程分享给更多的朋友一起学习进步，我们下一讲见！
- peter 👍（2） 💬（1）
请教老师几个问题： Q1：有序是指什么？ 从左到右有序，这个有序是根据什么？ Q2：节点不需要包含指向其父节点的指针（或索引）吗？ Q3：C++的库是否封装了对二叉树的操作？
2023-03-07 - Yj.yolo 👍（0） 💬（1）
思考题：“度为 2 的有序树”与“二叉树”的区别是什么？ 我的答案： （1）度为2的有序树是不区分左子树和右子树，而二叉树是要分左子树和右子树的。 理解：①有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序。②二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。比如：如果二叉树中的某节点子树只有一个孩子时，这个孩子结点必须区分是左孩子还是右孩子。 （2）度为2的有序数不包含空树，而二叉树是可以有空树的。 理解：①度为2的有序树不存在度大于2的结点，且一定要存在某节点的度为2。②二叉树有五种基本形态：空二叉树、仅有根节点的二叉树、左子树为空的二叉树、右子树为空的二叉树、左右子树均不为空的二叉数；即二叉树也不允许存在度大于2的节点，但是不要求必须存在度为2的节点。 以上是我的理解……烦请作者大大指正不足之处
2023-06-05 - Yj.yolo 👍（0） 💬（1）
您好！性质五的第一个式子推导的图片中第三行字有误吧！ 【原文】：“因此，再次根据性质二，前 k -1层有2^(k)-1个节点，那么高度为 k 的完全二叉树的节点数量一定大于2^(k-1)-1。” 【应该是】：“因此，再次根据性质二，前 k -1层有2^(k-1)-1个节点，那么高度为 k 的完全二叉树的节点数量一定大于2^(k-1)-1。”
2023-06-05 - wu526 👍（0） 💬（1）
满二叉树的特点中，不存在度为非 0 和非 2 的节点；这个是写错了吧，叶节点的度就是0呀，除叶节点外其他节点的度都是2呀。
2023-03-20