承德平台长春网站优化平台

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按照二叉查找树存储，如下图：