数据结构-二叉查找树

二叉查找树定义：二叉查找树就是一种数据的存储结构，有一个根节点，里面的每一个节点都能存储两个节点，对于结构中任意一个节点的左孩子节点小于这个节点，右孩子节点大于这个节点。如下图

二叉树能干什么？

在人们没有发现二叉树这种结构的时候，用链表或者数组存储数据，每次查找一个指定数据，需要几乎遍历整个链表或者数组，随着数据的越来越多，几十上百亿甚至更多更多怎么办？难道要进行几十上百亿次的遍历？很明显如果这样，那互联网早就慢像一坨屎。

二叉树就能解决大数据量查询的问题，很明显，二叉树的数据存储可以一层一层的来看，至顶而下每层最多能存储的数据个数，1，2，4，8，16......2^n（2的n次幂），二叉树的层数，就是从这颗二叉树中找到某一个节点的最大查询次数，很明显，数据量越大，使用二叉树查询数据与用链表或者数组查询数据的效率相比，提升的就越明显。

你可能回想，假如有100W个数据，根节点为这100W个数里面的最大值或者最小值，如果将100W个数从小到大依次通过根节点添加到二叉树里面，那这棵二叉树不就完全没有意义，变成一个链表了吗？如下图：

没错，这种问题当然会发生，因为二叉查找数是最基本的二叉树，后面还有红黑树，AVL树它们每次在添加和删除节点的时候需要进行左旋转或者右旋转来改变二叉树的结构，达到一种平衡状态，说白啦，就是改变根节点的值，让根节点的值一直是一个中间值，并且保持这棵树的叶子节点的高度不要相差太多。这些都是后面要复习的东西，慢慢来......

怎样写二叉树呢？

其实二叉树只有三种最基本的操作，添加，删除 和 遍历，一些其它扩展功能都是利用这三种基本功能来实现的。

添加操作的思路：将要添加的节点先和根节点root比较，如果比root小，进入root的左子树，如果比root大，进入root的右子树，重复上诉操作，直到为遇到某个节点的子节点为null，则将要添加的节点放到null的位置。

删除操作的思路：这个比添加操作难了很多，因为被删除的节点有三种情况：

（1）被删除的节点没有子节点，直接将被删除节点赋值null就可以啦。

（2）被删除节点有一个子节点，这种和情况（1）类似，只不过是把被删除节点的子节点覆盖掉被删除节点就OK啦。

（3）被删除节点有两个子节点，这种情况难度比情况（1）和（2）大了很多倍，首先，你要找到被删除节点的右子树的最小值将其删除，然后用这个最小值覆盖掉被删除节点。听起来很简单，你实际操作时候就知道啦，涉及到一个断开旧连接，添加新连接的过程，是不是听着很像链表的删除操作？这也就是很多人说二叉树是一种变形的链表的原因之一啦。这种操作是《算法第四版》里面的实现方式，网上应还有其它的实现方式，但是我只学了这一种

。

遍历操作的思路：大部分二叉树的遍历操作都相似，反正二叉查找树和红黑树，AVL树的遍历操作是一样一样的。有三大类遍历方式：

（1）最基本的遍历，前序遍历，中序遍历，后续遍历。这个网上自己收索吧，虽然写起来很简单，但是描述起来真的超级麻烦。

（2）一般叼的遍历，层级遍历，这个就是把二叉树一层一层的打印，实现起来需要一个队列，先将根节点放入队列，然后死循环判断队列是否为Null，每次进入循环会先把下一层的节点放入队列，这样就能保证源源不断的将二叉树里面的数据放入队列，然后我们再源源不断的从队列里面取出数据（提示：每次放入队列的是下层数据，而取出是这一层的数据，估计你看不懂我说啥，还是好好看代码吧）

（3）最叼的遍历，从小到大输出二叉树中的数据，这个是《算法第四版》里面的实现方式，代码没几行，但是两个递归应用和输出节点的时机真的太巧妙啦，比如，第一个递归的第一次弹栈，添加了第一个值，进入队列的只能是左孩子节点和当前节点，而右侧节点会跟着第二个递归进入右子树，然后在第二个递归弹栈的时候，右孩子节点变成当前节点输出，自己看吧，因为这种实现，我只能读懂，然后让我自己想是肯定想不出来的。

一点学习感悟：（1）可以把递归的结束想象成一个弹栈的过程。

（2）将二叉树的操作，想象成一个动态的画面，比如一辆在道路上奔跑的汽车。

具体代码地址：https://github.com/sunjiming/Data_Struct.git