数据结构-二分搜索树

二分搜索树

二分搜索树的每个节点的值:

• 每个节点的值都大于其左子树的所有节点的值
• 每个节点的值都小于其右子树的所有节点的值

一般二分搜索树不包含重复元素, 当然也可以定义包含重复元素的二分搜索树

二分搜索树天然的具有递归特性

下面是二分搜索树的几个样例 ?*

image.png image.png

在进行相关操作之前, 先定义一个支持泛型的节点类, 用于存储二分搜索树每个节点的信息, 这个类作为二分搜索树的一个内部类, 二分搜索树的类声明以及Node节点类声明如下:

添加元素

由于二分搜索树本身的递归特性, 所以可以很方便的使用递归实现向二分搜索树中添加元素, 步骤如下:

• 定义一个公共的add方法, 用于添加元素
• 定义一个递归的add方法用于实际向二分搜索树中添加元素

查找元素

由于二分搜索树没有下标, 所以针对二分搜索树的查找操作, 这里定义一个contains方法, 查看二分搜索树是否包含某个元素, 返回一个布尔型变量, 这个查找的操作一样是一个递归的过程, 具体代码实现如下:

遍历操作

• 遍历操作就是把所有的节点都访问一遍
• 访问的原因和业务相关
• 遍历分类

深度优先遍历 :

• 前序遍历 : 对当前节点的遍历在对左右孩子节点的遍历之前, 遍历顺序 : 当前节点->左孩子->右孩子
• 中序遍历 : 对当前节点的遍历在对左右孩子节点的遍历中间, 遍历顺序 : 左孩子->当前节点->右孩子
• 后序遍历 : 对当前节点的遍历在对左右孩子节点的遍历之后, 遍历顺序 : 左孩子->右孩子->当前节点
  广度优先遍历 :
• 层序遍历 : 按层从左到右进行遍历

前序遍历

• 最自然的遍历方式
• 最常用的遍历方式

这里一样使用递归来实现遍历, 对于一颗二分搜索树进行遍历, 如果要使用非递归方式实现的话, 可以使用一个栈来赋值进行遍历, 代码如下: