二叉查找树

分享人：韩亚博

1.背景介绍

2.知识剖析

3.常见问题

4.编码实战

5.扩展思考

6.参考文献

7.更多讨论

1.背景介绍

我曾经推荐一个学生到某知名公司，没多久，学生给我说了应聘的事情：“我介绍我开发了企业管理系统、在线商城系统等等，没想到他问我使用了什么数据结构和算法，我懂很多技术，那么多功能我都实现了，他不问，却问我使用了什么数据结构和算法，你说搞笑不？数据结构、算法我早就忘了，我会开发软件还不行吗？”人力资源总监也反馈过来意见：“很搞笑，这个学生做了不少系统，却说根本没用到数据结构和算法。”

遇到一个实际问题，需要解决两个事情：

（1） 如何将数据存储在计算机中；

（2） 用什么方法策略解决问题。

前者是数据结构，后者是算法。只有数据结构没有算法，相当于只把数据存储到计算机中而没有有效的方法去处理，就像一幢只有框架的烂尾楼；若只有算法，没有数据结构，就像沙漠里的海市蜃楼，只不过是空中楼阁罢了。

数据是一切能输入到计算机的信息总和，结构是指数据之间的关系，数据结构就是将数据及其之间的关系有效地存储在计算机中。算法是指对特定问题求解步骤的一种描述，说白了就是解决问题的方法策略。

2.知识剖析

2.1 二叉排序树是什么？

2.2 二叉排序树的特点

2.1 二叉排序树是什么？

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

二叉排序树也是一棵二叉树，所谓二叉树，就是“任何节点最多只允许两个子节点”，这两个子节点称为左右子节点。如下便是一个二叉树。

2.2 二叉排序树的特点

（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

3.常见问题

三种遍历

三种遍历

前序遍历：访问根节点，前序遍历左子树，前序遍历右子树

中序遍历：中序遍历左子树，访问根节点，中序遍历右子树

后序遍历：后序遍历左子树，后序遍历右子树，访问根节点

4.编码实战

实现一个二叉排序树

简单讲解实现方法

5.扩展思考

二叉排序树的应用

TreeSet底层数据结构是二叉树

6.参考文献

https://blog.csdn.net/rainchxy/article/details/79454465

https://www.jianshu.com/p/7db18d3d5d05

https://www.cnblogs.com/skywang12345/p/3576452.html#a1

演示网站

7.更多讨论

分享到此结束

欢迎大家讨论