数据结构与算法之 —— 二叉树和二叉搜索树
二叉树
01. 什么是二叉树
定义：每个节点都最多只能有两个子节点的树结构
特点： 通常子树被称作“左子树”（left subtree）和“右子树”（right subtree） 任何一个树都可以转成二叉树
02. 完全二叉树
定义：一棵二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k层所有的结点都连续集中在最左边。
特点： 深度为k的完全二叉树，至少有2^(k-1)个节点，至多有2^k-1个节点 
03. 满二叉树
定义：一棵二叉树深度为k，则第k层有2^(k-1)个节点的树是满二叉树。
特点： 所有内部节点都有两个子节点，叶子节点全都在最底层； 第k层的结点数是：2^(k-1); 总结点数是：2^k-1，总结点数一定是奇数 
04. 为什么定义这样特殊的二叉树？
因为一颗完全二叉树是可以用数组来存储的，不会浪费内存空间。
如下数组，根节点 A 的下标是 0，那么它的左孩子就是 (2 * 0 + 1)，右孩子就是 (2 * 0 + 2)。以此类推，0 替换为变量 i 后，就可以推导每个节点的左右孩子，而不需要特别定义节点类，使用两个左右指针去指向左右孩子，这也是一种更高效的存储方案。此处可以延伸到二叉堆，它无论何时都是一颗符合堆的性质的完全二叉树，所以它的最优存储方案就是用数组
05. 二叉树的遍历方式
二叉树有先序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）、层序遍历四种方式。
i. 先序遍历（根左右） 
遍历规则： 先访问根结点 然后先序遍历左子树 然后先序遍历右子树
实现：
遍历结果：ABDHIECFJG
ii. 中序遍历（左根右） 
遍历规则： 先中序遍历左子树 访问根结点 然后中序遍历右子树
实现：
遍历结果：HDIBEAFJCG
iii. 后序遍历（左右根） 
遍历规则： 先后序遍历左子树 然后后序遍历右子树 然后访问根结点
实现：
遍历结果：HDIBEACFJG
iv. 层序遍历 
遍历规则：从上到下，从左到右遍历。
实现：
遍历结果：ABCDEFGHIJ
二叉搜索树（BST）
01. 基本概念
二叉搜索树BST（Binary Search/ Sort Tree），也称为二叉查找树，二叉排序树，顾名思义是二叉树的特种树，专注于检索，特点是让节点按照数据的一定的规律摆放，从而让搜索某个节点特别的高效
特点： 左子树上所有结点的值均小于等于它的根结点的值 右子树上所有结点的值均大于等于它的根结点的值
02. 代码实现
1、定义
首先定义两个类，一个节点类，一个树类：
2、新增
新增节点时，需要保证无论增加多少个节点，都不被破坏二叉搜索树的定义（即左小右大）。
步骤： 新节点与根节点进行比较 若新节点 < 根节点，将根节点指向根节点的左孩子，返回第一步 若新节点 > 根节点，将根节点指向根节点的右孩子，返回第一步 若根节点不存在，此处即为新节点的位置
3、查询
步骤： 新节点与根节点进行比较 若新节点 < 根节点，将根节点指向根节点的左孩子，返回第一步 若新节点 > 根节点，将根节点指向根节点的右孩子，返回第一步 若新节点 === 根结点，找到啦！ 若根节点不存在，说明树中不存在要查询的节点
4、删除 叶子节点：直接删除 只有一边有孩子节点：让孩子节点接替被删除节点的位置 两边都有孩子节点： 在待删除节点的左子树里面找到最大的值替代 在待删除节点的右子树里面找到最小的值替代
03. 优缺点
优点：增删查速度快，平均时间复杂度均为O(logn)
缺点：可能出现类似线性链表的结构，查找的时间复杂度会变成O(n)
平衡二叉树（AVL）
01. 基本概念
平衡二叉树（AVL）全称平衡二叉搜索树，是一种可以自平衡的树，是从上面二叉搜索树升级过来的。
以二叉搜索树为基础，增加平衡的规定：左子树和右子树的高度差不得超过1，并且左右两个子树都是一棵平衡二叉树。
02. 如何实现平衡？
通过左旋或右旋两种方法。 
03. 优缺点
优点：解决了二叉查找树退化为近似链表的缺点，最坏的查找时间复杂度也为 O(logn)。
缺点：因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，很容易会破坏平衡树的平衡的规则，进而我们需要频繁地通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁进行调整，这会使平衡树的性能大打折扣。
激活谷谷主为您准备了激活教程，为节约您的时间请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/97213.html
