数据结构之二叉树

二叉树

二叉树（Binary Tree）是每个节点最多只有两个子节点的结构，通常左边的叫左子树，右边的叫右子树，二叉树的节点是具有左右次序的，不能随意颠倒。

二叉树的 4 种形态

1. 仅仅只有一个根节点，没有子节点。
2. 根节点只有左子树。
3. 根节点只有右子树。
4. 根节点既有左子树，又有右子树。

二叉树的分类

1. 完全二叉树
假设其深度为 d（d>1）。除了第 d 层外，其它各层的节点数目均已达最大值，且第 d 层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树。

2. 满二叉树
所有叶子节点全都出现在最底层的完全二叉树就叫满二叉树。就相当于这棵树的第一层是 1 个节点，第二层是 2 个节点，第三层是 4 个节点，第五层是 8 个节点，以此类推。

3. 斜树
所有的节点都只有左子树的二叉树叫左斜树，所有的节点都只有右子树的二叉树叫右子树，它们都叫斜树。实际上这棵二叉树看起来像一撇或者一捺。

4. 二叉搜索树（也叫二叉查找树或者二叉排序树）
若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值；它的左、右子树也分别是二叉排序树。说明它是一颗有顺序的树，左子树节点的值小于根节点的值，右子树节点的值大于根节点的值。

5. 平衡二叉树
它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

二叉树的存储

以下面的二叉树为例

1. 顺序存储
二叉树的顺序存储结构就是用一维数组存储二叉树中的节点，并且节点的存储位置，也就是数组的下标要能体现节点之间的逻辑关系。如果某个节点的索引为 i，（假设根节点的索引为 0）则在它左子节点的索引会是 2i+1，以及右子节点会是 2i+2。

2. 链式存储
因为在二叉树中，一个父节点最多只允许 2 个子节点，所以我们只需要一个存储数据和左右子节点的指针，这样的结构就是链式存储，也叫二叉链表。

二叉树的遍历

以下面的二叉树为例

1. 前序遍历

先访问根节点，然后前序遍历左子树，再前序遍历右子树。根据上面的二叉树前序遍历结果是 ECBADGFH。

2. 中序遍历
从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树。根据上面的二叉树中序遍历结果是 ABCDEFGH。

3. 后序遍历
从左到右先叶子节点后父节点的方式遍历访问左右子树，最后是访问根节点。根据上面的二叉树后序遍历结果是 ABDCFHGE。

4. 层序遍历
从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对节点逐个访问。根据上面的二叉树层序遍历结果是 ECGBDFHA。

总结

二叉树有多种形态，多种类型，多种存储方式和多种遍历方法。完全二叉树和满二叉树还是难以理解的，满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满二叉树，主要是「满」和「完全」的区别分清楚。

由于线性查找需要遍历全部数据，在数据量大的时候效率就非常低下，到底有多低，在数据库有几百万几千万以上数据量写过查询语句的就知道有索引和没索引的区别。那为什么有索引的就那么快呢？当然数据库的索引不是用二叉树来实现的，想想如果使用二叉树来实现，那这个索引树得多高啊。而是采用更适合数据库查找的 B+ 树 来实现的，不过 B+ 树 也是由二叉树进化而来的。

二叉搜索树由于它是有序的，左子树节点的值小于根节点的值，右子树节点的值大于根节点的值，那么就可以利用二分查找来查找对应的值，也叫折半查找。但二叉搜索树最坏的情况下可能变异成斜树，斜树的查找时间复杂度就是 O(n)，就跟线性查询没区别了。那么平衡二叉树就是来解决这个问题的，因为它限定了左右两个子树的高度差的绝对值不超过 1，当插入和删除时，不满足这种情况时，通过左旋和右旋来保持这个规则。所以，它是时间复杂度是 O(log(n));

PS:
清山绿水始于尘，博学多识贵于勤。
我有酒，你有故事吗？
微信公众号：「清尘闲聊 」。
欢迎一起谈天说地，聊代码。