算法与数据结构二叉树的性质（数据结构系列5树与二叉树）

算法与数据结构二叉树的性质（数据结构系列5树与二叉树）A，B，C等都是结点，结点不仅包含数据元素，而且包含指向子树的分支。结点术语描述举例

前言

二叉树可以说是数据结构中的重头戏，不止是因为其在数据结构中所占的篇幅较大，更重要的是它在生活中的应用十分广泛，尤其体现在查找，排序等方面。而且在相关面试题中也是频频出现。如果只可以用一个词来概括二叉树，那么这个词我选择递归，二叉树真的可以说是递归的典型代表。递归这种东西，写出来的代码十分简单，但是要深刻理解却是要花点功夫，本文也是着重说明这一点，不止用文字讲述，而且用动图加以详细说明。如果喜欢，可以收藏，希望能给你带来收获。

一：树（1）树的概念

树是一种非线性的数据结构，是有n个（n⩾ \geqslant⩾ 0，当n为0时叫做空数）有限结点组成的一个具有层次关系的集合。把它称为树，是因为它和现实中的树木十分相像，只不过是倒挂的树

如下，树中有一个非常特殊的结点，称其为根节点，根节点没有前驱，除根结点外，剩余每个结点又可以看作是以它为根节点所组成的子树 因此每一个结点都可以说是一个子树的根节点，所以树的定义时具有递归性质的

（2）树的一些基本术语

下面的这些概念，了解即可，不用刻意记忆

术语	描述	举例
结点	A，B，C等都是结点，结点不仅包含数据元素，而且包含指向子树的分支。	A结点不仅包含元素A，而且包含三个指向子树的指针
结点的度	结点拥有的子树或分支个数	A结点有三颗子树，A的度为3
树的度	树中各结点度的最大值	A D结点的度最大为3，故树的度为3
叶子结点	度为0的结点	F G I J K L M均为叶子结点
非叶结点	度不为0的结点	A B C D E H 均为非叶结点
孩子	某结点子树的根	A结点的孩子为B C D
双亲	与孩子的定义对应	B C D的双亲都是A
兄弟	同一个双亲的孩子互为兄弟	B C D互为兄弟
祖先	从根到某结点的路径上所有的结点，都是该结点的祖先	K的祖先是A B E
子孙	以某结点为根的子树中的所有结点	D的子孙是H I J M
层次	根节点为第一层，根的孩子是第二层次，以此类推	结点F处在第三层
结点的深度	是指从根节点到该结点路径上的结点个数	\
结点的高度	从某结点往下走可能到达多个叶子结点，对应了通往这些叶子结点的路径，其中最长的那条路径上的结点的个数称其为结点的高度	D的高度为3
树的高度(深度)	树中结点的最大层次	根节点的高度就是树的高度
堂兄弟	双亲在同一层的结点互为堂兄弟	G和H互为堂兄弟
有序树	树中结点的子树从左至右是有次序的，不能交换	\
无序树	树中结点的子树没有顺序，可以任意交换	\
丰满树	除了最底层外，其他层都是满的	\
森林	若干互不相交的树的集合	上面的树，将根结点A去除，剩余的就一个森林

（3）树的表示

很多时候，树的度是不能够确定的，也就是说一个结点有多少个孩子是不可知的。Windows系统的目录采用的就是树形结构，我们从没有听过在一个文件夹里最多可以创建多少个文件等这样的限制（前提是不受存储限制）。所以使用单纯的线性对应的结构去存储树，是不可行的。
树的存储结构主要有：孩子兄弟表示法，双亲表示法和孩子表示法

A：孩子兄弟表示法

树的孩子兄弟表示法：一个结点有三个域，一个数据域和两个指针域，第一个指针指向该结点的第一个孩子结点，第二个指针域指向该结点的兄弟结点。对于其孩子结点也是如此定义。

B：双亲表示法

树的双亲表示法：使用一组连续的存储空间来存放结点，结点按一定顺序（一般是从上到下，从左到右）依次存放在数组中，数组的下标表示了该结点的位置，每个结点有一个数据域和一个指针域，指针域保存的是该结点的双亲结点在数组中的下标。

C：孩子表示法

树的孩子表示法其实就是图的邻接表存储结构，这里不再详细叙述了

二：二叉树（1）二叉树的概念

二叉树应该是这样一棵树：每个结点最多有两颗子树，也即二叉树的度最大为2，同时二叉树的子树有次序之分，不能颠倒

（2）特殊的二叉树

• 满二叉树：满二叉树它的每一层的结点数都达到了最大值。如果一个二叉树有k层，且其结点总数为2k-1个，那么它就是满二叉树

• 完全二叉树：完全二叉树概念有点抽象。简单点来说：一个完全二叉树是由对应的满二叉树进行删除而来的，删除的时候必须从上到下，从右向左，不能跳着删除。

（3）二叉树的性质

• 1：规定根节点层数为1，则一颗非空二叉树第i层最多有2i-1个结点

2：规定根节点的层数为1，则深度为h的二叉树最大结点数为2h-1个。
题目：在具有 2n 个结点的完全二叉树中，叶子结点个数为？

• 3：对任意一颗二叉树，叶子结点（度为0的结点）总比度为2的结点多1个

• 4：关于高度

（4）二叉树的顺序存储结构A：二叉树顺序存储结构

对于一颗完全二叉树，从根节点开始，从上到下，从左至右依次编号，按照编号存放在一个数组里，这就是完全二叉树的顺序存储结构。比如一个完全二叉树，根节点编号为0，那么它的左孩子编号就是2×0 1，右孩子编号就是2×0 2，该二叉树中任意一个结点（假设编号为i），其左孩子编号为2×i 1，右孩子为2×i 2.

之所以这里要限定为完全二叉树，并不是说普通的二叉树不能用数组存储。既然一颗二叉树要用数组存，那么它就一定要发挥数组的优势，比如说通过索引确定孩子的编号，而对于一个普通的二叉树说来说，其结点分布可能是不均匀的，所以要使用数组存储普通的二叉树，必须要把这个树转化为其对应的完全二叉树的形态，势必会造成大量空间的浪费

其实，数组在这里的真正用处是存储堆，因为堆就是完全二叉树。

B：堆

堆和堆排序的内容，篇幅较长，且比较重要，期待后续文章

（5）链式存储结构A：二叉树的链式存储结构

使用二叉链表可以有效的存储二叉树。二叉链表中的每一个结点，有一个数据域和两个指针域，这两个指针域分别指向该结点的左孩子和右孩子。

二叉链表结构定义如下

typedef struct BTNode { stuct BTNode* lchild;//左孩子指针 stuct BTNode* rchild;//右孩子指针 DataType val;//数据域 }B：二叉树的遍历

如果要用一个词来概括二叉树的话，那么我选择“遍历”。遍历可谓是二叉树中最重要的运算，是其他一切运算的前提。

所谓遍历，通俗的理解就是全部访问一遍，在单链表那一章为什么不过度强调遍历这个词呢，因为单链表的遍历就只有一种情况。对于二叉树来讲，其逻辑结构的特点，导致了它有不同的遍历方法，每个遍历又有其特定的应用场景。

遍历从大的方面来讲可以分为两种：广度优先遍历（BFS），深度优先遍历（DFS）。对于二叉树来说，它有四种遍历方法，层次遍历属于BFS，先序，中序，后序遍历属于DFS

①：层次遍历

一句话概括：自上而下，先左后右

②：深度优先遍历

以下动图来自天勤计算机考研

天勤计算机考研

大部分人其实都知道一些二叉树的遍历的口诀，例如先序遍历是“根左右”，中序遍历“左根右”，或许遍历左右根。通过这样的口诀，也能够很快地写出树的各种遍历方式，但如果问到为什么是这样，很多人却无法说清楚。

呈现出不同的遍历的方式的原因在于二叉树的递归结构和访问时机的不同。
如下图，这三种遍历方式本质是一样的，每个结点都会经历三次访问，二叉树默认递归时其实就是先序遍历，也就是先根节点，再左，后右。在其递归的过程，在不同时机访问，就会造成不同的遍历结果。

先序遍历是指：第一次遇到这个结点访问，第二次遇到或第三次遇到跳过该结点直接访问下一个结点

中序遍历是指：第一次遇到结点跳过，第二次再遇到结点访问，第三次遇到跳过

后序遍历是指：前两次遇见结点不访问，最后一次遇见时访问

三：二叉树相关问题

二叉树不像链表，栈队列那些结构一样，对于二叉树，考察的主要是它的应用。二叉树的应用一定与递归离不开，递归代码简单，但是十分抽象。递归包括两点：子问题和返回条件，要写出递归代码，首先不能把问题看得太复杂，要把问题细化，细化成最小的问题。对于二叉树来说，其子问题就是划分左子树和右子树，返回条件为空树

为了方便说明，建立这样一颗树

（1）基础问题

1：三种遍历（递归）
下面的三种遍历采用递归的方式，递归的方法代码短小精悍，但是理解起来较为抽象

• 先序遍历

• 中序遍历

• 
  
• 后序遍历

2：求解树的结点个数

更优的写法（分治法思想）

3：求解树的叶子结点个数
假如没有结点(root=NULL)，那么就是0，假如只有一个结点A（叶子结点），那么它就是叶子结点，然后A的叶子结点就是其左子树 右子树

4：求解树的高度
如果没有结点(root=NULL)，那么高度为0，如果只有一个结点A（叶子结点），那么高度为1，所以A的高度就是A的左子树高度和右子树高度之比，取大者 1

5：求二叉树第K层的结点个数
也是一个递归过程。比如要求某个树的第三层的结点个数，那么就等于求其子树的第二层的结点个数，再等价于求其子树的子树的第一层的结点个数。传入下一层时，让k-1，同时传入的是其孩子结点，这样一旦root不等于空，k不等于1，就能一直递归下去，直到k=1时，不断向上返回即可

6：找寻某个结点
如果root为空，返回NULL，如果root的值是X，则返回root；否则，该节点找不到，该去其孩子结点找，先定义一个左寻找结点，递归进入左孩子，如果左孩子找不到则什么也不返回，如果左孩子返回则不执行右孩子，否则再去右孩子找。如果左右孩子都不返回，那么这棵树没有该节点

7：销毁二叉树
后序销毁

8：二叉树的层次遍历
二叉树的层次遍历需要借助到队列。先将根节点入队列，然后如果队列不空，就出队，出队时看其孩子是否存在，如果存在就将其孩子入队列，然后迭代即可。

所以下面的操作中，会借助到队列的相关操作，具体见
数据结构-线性表之栈和队列
同时需要注意，队列中结点的数据域，也即val，可以设置为BTNode*，也就是数据存储的是树节点指针。

9：判断是否为完全二叉树
判断是否为完全二叉树可以从层序遍历入手

所以，首先让其按照层序遍历次序入队，同时出队，如果遇到NULL，跳出循环，接着再对后半部分进行出队，如果出队的过程中出现非空元素，那么它就不是完全二叉树，反之则是

如下

（2）相关oj题

二叉树和链表一样，面试题中的几乎必考，期待后续的专题