Java数据存储结构——二叉查找树
文章目录
- 22.1.2二叉查找树
- 22.1.2.1 概述
- 22.1.2.1二叉查找树添加节点
- 22.1.2.2二叉查找树查找节点
- 22.1.2.3 二叉树遍历
- 22.1.2.4 二叉查找树的弊端
22.1.2二叉查找树
22.1.2.1 概述
二叉查找树,又称二叉排序树或者二叉搜索树
二叉查找树的特点：
- 每一个节点上最多有两个子节点
- 任意节点左子树上所有节点的值都小于根节点的值
- 任意节点右子树上所有节点的值都大于根节点的值
22.1.2.1二叉查找树添加节点
- 小的存左边
- 大的存右边
- 一样的不存
案例：将 7 4 10 5依次 按照二叉树存储
22.1.2.2二叉查找树查找节点
从根节点依次比较，比较根节点大的话往右子树比较，比根节点小的话往左子树走。
22.1.2.3 二叉树遍历
- 前序遍历： 根 左 右
从根节点开始，先遍历根节点，再左子节点，最后右子节点的顺序遍历。
如图，遍历结果为 20、18、16、19、23、22、24
- 中序遍历：左 根 右
先遍历左子树 ，再遍历根节点 ，最后遍历右子树
中序遍历获取的结果是从小到大的数据
如图，遍历结果：16、18、19、20、22、23、24
- 后序遍历：左 右 根
先遍历左子树，再遍历右子树 ，最后遍历根节点
如图，遍历结果：16、19、18、22、24、23、20
- 层序遍历：从根节点一层一层开始
上图按照层序遍历结果为：20、18、23、16、19、22、24
22.1.2.4 二叉查找树的弊端
如，将7 、10、11、12、13按照二叉查找树存储，如下图：
