敲黑板！数据结构精讲之二分搜索树

      童鞋们好！今天，我们来学习面试常考知识点：数据结构之二分搜索树！记得做好笔记哦！

      关于二分搜索树

二分搜索树是一颗二叉树，满足二叉树的所有定义。

二分搜索树每个节点左子树值都小于该节点值，每个节点右子树值都大于该节点值。

任意节点每颗子树都满足二分搜索树定义。

      二分搜索树如此定义的意义何在？

      二分搜索树实际上是做数据整理。因为左右子树的值和根节点关系，我们每次查找元素在根节点进行对比后，每次几乎能排除掉近一半的查找范围，大大加快了查询速度。插入元素时也一样，比如，如果我们知道超市二楼卖水果，就不用在一楼找了，大大加快了购买速度。

      为了达到这样的高效，树结构也需要每个节点间具备可比较性。而链表数据结构就没有这类要求，所以有得必有失。

      定义二分搜索树类

      添加属性及相应接口；

      因二分搜索树节点不能为null，所以添加判断方法；

     add方法，添加节点设计。添加步骤如下：

找到父节点

创建新节点 node

parent.left = node 或 parent.right = node

     相等的值怎么处理？方案：return或覆盖

      现在创建测试类；

      此时别忘了，compare的方法还没实现；

      如何实现呢？如果数字还好，可直接通过运算符直接比较；但如果是自定义数据类型呢？例如：比较两个Student类型对象

      第一种处理方式：新建Comparable接口

      该接口的意义是：如果想把元素存入二分搜索树，必须实现该接口；

      然后修改BinarySearchTree及compare方法

      再将Student实现Comparable接口 ，补充重写方法

      然而，这种设计存在一些“瑕疵”。

      比如，在不同情况下，希望比较的规则也对应变换，例如：我们现在希望年龄大一点的去左子树，即年龄大的我们认为它小，正好与上例中的规则相反；则需要第二种处理方式。

      第二种处理方式：新建比较器接口

      将这个比较器传进二叉树类里，同时不再必须实现Comparable接口

      Main

      这样，在不同情况下就有了不同的比较方式。但很多时候并不需要这样，此时为了代码保证正确，还必须传一个比较器进去，有些麻烦，较完美的处理方式是兼容以上两种情况。

      此时我们用的这两个接口，其实Java官网提供了，可直接使用官方的。再比较时，就可以有多种方式了。

      这里，可以采取一些网站测试： http://520it.com/binarytrees/

      采取打印工具类，测试一下： https://github.com/CoderMJLee/BinaryTrees/tree/master/BinaryTreePrinter/src/com/mj/printer

      BinaryTreeInfo的四个实现方法

      值相等问题

      之前我们采取的是return方案，但需求更多的是第二种方案，即覆盖。

      这样可覆盖原有内容

      测试结果

      以上，就是关于二分搜索树的知识点，你学会了吗？如果有疑问，请在后台留言给我们哦！