数据结构之二叉查找树（java语言）

二叉查找树的结构比较简单：

1，有一个根节点，否则就是空树

2，每个节点有一个值，一个左子节点，一个右子节点

3，每个节点的左子树的所有节点的值都比当前节点的值小

4，每个节点的右子树的所有节点的值都比当前节点的值大

代码：

测试：

最理想情况

结果：

最坏情况：


二叉查找树在最好情况下（上图左），按值查找最多需要log2（N+1）次；

最坏的情况（上图右），按值查找需要N次，和链表的结构是一样的了。

为了保证结构不退化，需要加一些条件，AVL树是其中一种比较好且容易实现的结构（以后再说）。

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容