数据结构与算法之美-二叉树

树是一种非线性表数据结构，相对于栈、队列等线性表结构较为复杂。二叉树是一种特殊的树，要求父节点最多有两个子节点。

相关概念

• 节点的高度：节点到叶子节点的最长路径（边数）。
• 节点的深度：根节点到这个节点所经历的边的个数。
• 节点的层数：节点深度+1。
• 树的高度：根节点的高度。

二叉树的存储方式

基于指针或者引用的二叉链式存储法

这种方式要求每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。

基于数组的顺序存储法

这个方式把根节点存储在下标i = 1的位置，那根节点左子节点存储在下标2 * i = 2的位置，根节点右子节点存储在2 * i + 1 = 3的位置。以此类推，存储在下标为i的节点的左子节点存储在2 * i 的位置，右子节点存储在2 * i + 1的位置。

二叉树的遍历方式

经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。也可采用分层打印的方式。

• 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
• 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
• 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
• 分层遍历是指，首先打印第一层的数据，然后依次打印下一层的数据，直至最后一层。

前、中、后序遍历采用的是递归的思想，分层遍历可借助一个队列，采用广度优先遍历思想。具体编码实现点击这里查看

常见二叉树

满二叉树

二叉树的叶子节点都在最底层，除了叶子节点外，每个节点都有左右两个子节点，这种二叉树被称为满二叉树。

完全二叉树

二叉树的叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。

满二叉树是特殊的完全二叉树，且满二叉树的特征很明显，为啥要把完全二叉树单拎出来分个类呢？我们知道二叉树用链式存储的方式要额外存储节点的左右孩子指针，这无疑会造成内存空间的浪费。如果采用顺序存储的方式，当节点不存在孩子节点时也会导致数组中部分节点空闲导致浪费。但是完全二叉树的特点保证了顺序存储只会浪费下标为0的一个节点，所以完全二叉树是完全适合采用顺序存储方式的二叉树。

二叉搜索树（二叉查找树）

二叉查找树中，每个节点的值都大于等于其左子树上节点的值，小于等于其右子树上节点的值。

查找元素

二叉查找树就是为了方便查找而出现的，支持最好O(logn)，最差O(n)的时间复杂度。查找过程：我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

插入元素

二叉查找树的插入过程有点类似查找操作，新插入的数据一般都是在叶子节点上，所以我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。

如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

删除元素

删除操作需要分为三种情况进行不同的操作。

1. 待删除节点无子节点，则直接将父节点中指向该节点的指针置空即可。
2. 待删除节点只有一个子节点，则需要将父节点中指向该节点的指针指向该节点的子节点即可。
3. 待删除节点有两个子节点，需要找到该节点左子树中的最大值或右子树中的最小值，然后将待删除节点的值替换成在子树中找到的节点值，然后将找到的节点从树中删除（采用方式1进行删除）。

刚才讨论的操作都是针对树中元素不存在相同值的情况，如果树中元素存在相同值，在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。

当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点为止。

对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。