二叉树的详解（这是我见过的最全的介绍二叉树的文章）

二叉树的详解（这是我见过的最全的介绍二叉树的文章）注意，最后一棵二叉树不是完全二叉树。一个典型的完全二叉树的例子如下图所示。这棵二叉树的深度为k（从1开始计算），有2k-1个节点。2．完全二叉树完全二叉树：除了底层节点可能没填满，其余每层的节点数都达到最大值，并且底层的节点都集中在该层最左边的若干位置。若底层为第h层，则该层包含1～2h-1个节点。

二叉树的种类

（4种：满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树）

1．满二叉树

如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树。

这棵二叉树的深度为k（从1开始计算），有2k-1个节点。

2．完全二叉树

完全二叉树：除了底层节点可能没填满，其余每层的节点数都达到最大值，并且底层的节点都集中在该层最左边的若干位置。若底层为第h层，则该层包含1～2h-1个节点。

一个典型的完全二叉树的例子如下图所示。

注意，最后一棵二叉树不是完全二叉树。

3．二叉搜索树

前面介绍的二叉树中的节点都没有数值，而二叉搜索树是有数值的。二叉搜索树是一个有序树，满足如下规则：

• 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值。
• 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值。
• 它的左、右子树也分别为二叉排序树。

下面这两棵树都是二叉搜索树。

4．平衡二叉搜索树

平衡二叉搜索树又称为AVL（Adelson-Velsky and Landis）树，它是一棵空树，或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

最后一棵二叉树不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。

C 中map、set、multimap、multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作的时间复杂度是O(logn)，而unordered_map、unordered_set、unordered_map、unordered_map的底层实现是哈希表。

在使用自己熟悉的编程语言实现算法时，一定要知道常用的容器底层都是如何实现的，最基本的就是map、set等，否则很难分析自己写的代码的性能。

遍历方式

二叉树主要有两种遍历方式：

（1）深度优先遍历：先往深处遍历，遇到叶子节点时再往回遍历。

（2）广度优先遍历：一层一层地遍历。

以上是图论中最基本的两种遍历方式，将深度优先遍历和广度优先遍历进一步拓展，有如下遍历方式：

• 深度优先遍历

— 前序遍历（递归法、迭代法）。

— 中序遍历（递归法、迭代法）。

— 后序遍历（递归法、迭代法）。

• 广度优先遍历

— 层次遍历（迭代法）。

在深度优先遍历中，前、中、后指的就是中间节点的遍历顺序，只要记住前序、中序、后序指的是中间节点的位置即可。

通过如下中间节点的顺序就可以发现，中间节点的顺序就是所谓的遍历方式：

• 前序遍历：中→左→右。
• 中序遍历：左→中→右。
• 后序遍历：左→右→中。

下面看一下自己理解的前序、中序、后序有没有问题。

下面确定递归算法的三个要素。每次写递归算法时都基于下面的“三部曲”，可以写出正确的递归算法。

（1）确定递归函数的参数和返回值。

确定哪些参数在递归过程中需要处理就在递归函数中加上这些参数，并且明确每次递归的返回值是什么，进而确定递归函数的返回类型。

（2）确定终止条件。

写完递归算法，程序运行的时候经常会遇到栈溢出的错误，原因是没写终止条件或者终止条件写得不对。操作系统也是用一个栈的结构保存每一层递归的信息的，如果递归没有终止，那么操作系统的内存栈必然会溢出。

（3）确定单层递归的逻辑。

确定每一层递归需要处理的信息。在这里会重复调用函数本身来实现递归的过程。

下面以前序遍历为例。

（1）确定递归函数的参数和返回值。

因为要打印出前序遍历节点的数值，所以参数中需要传入数组（C 中使用vector）来存放节点的数值，除了这一点，就不需要再处理其他数据了，也不需要有返回值，所以递归函数的返回类型就是void，代码如下：

void traversal(TreeNode* cur vector<int>& vec)

（2）确定终止条件。

在递归的过程中，如何确定递归结束了呢？当当前遍历到的节点为空时，说明本层递归就要结束了。如果当前遍历的这个节点为空，则直接返回，代码如下：

if (cur == NULL) return;

（3）确定单层递归的逻辑。

前序遍历是中→左→右的顺序，所以单层递归的逻辑就是先取中节点的数值，再处理左子树和右子树，代码如下：

vec.push_back(cur->val); // 中 traversal(cur->left vec); // 左 traversal(cur->right vec); // 右

完整代码如下：

class Solution { public: void traversal(TreeNode* cur vector<int>& vec) { if (cur == NULL) return; vec.push_back(cur->val); // 中 traversal(cur->left vec); // 左 traversal(cur->right vec); // 右 } vector<int> preorderTraversal(TreeNode* root) { vector<int> result; traversal(root result); return result; } };

中序和后序遍历的代码如下：

// 中序遍历 void traversal(TreeNode* cur vector<int>& vec) { if (cur == NULL) return; traversal(cur->left vec); // 左 vec.push_back(cur->val); // 中 traversal(cur->right vec); // 右 } // 后序遍历 void traversal(TreeNode* cur vector<int>& vec) { if (cur == NULL) return; traversal(cur->left vec); // 左 traversal(cur->right vec); // 右 vec.push_back(cur->val); // 中 }

好啦，二叉树暂时就学到这里了。