二叉搜索树的遍历

作者:超人汪小建(seaboat)

出处:https://blog.csdn.net/wangyangzhizhou/column/info/25184/2


二叉搜索树

二叉搜索树(Binary Search Tree,简写BST),又称为二叉排序树,属于树的一种,通过二叉树将数据组织起来,树的每个节点都包含了健值 key、数据值 data、左子节点指针、右子节点指针。其中健值 key 是最核心的部分,它的值决定了树的组织形状;数据值 data 是该节点对应的数据,有些场景可以忽略,举个例子,key 为身份证号而 data 为人名,通过身份证号找人名;左子节点指针指向左子节点;右子节点指针指向右子节点。

二叉搜索树特点

  • 左右子树也分别是二叉搜索树。
  • 左子树的所有节点 key 值都小于它的根节点的 key 值。
  • 右子树的所有节点 key 值都大于他的根节点的 key 值。
  • 二叉搜索树可以为一棵空树。
  • 一般来说,树中的每个节点的 key 值都不相等,但根据需要也可以将相同的 key 值插入树中。

image

中序遍历

我们知道对于二叉树来说,遍历的方式一般有三种:前序遍历、中序遍历和后序遍历。但对于二叉搜索树,比较常用的是中序遍历,因为通过该种方式遍历出来的元素属于一个递增序列。

开始中序遍历,即是以“左根右”方式遍历,先找到“A”,

image

接着找到“B”,

image

往下一个个获取,

image

image

image

image

image

image

树的最小key值

二叉搜索树的最小 key 值节点从根节点开始一直沿着左子节点搜索,直到遇到节点的左子节点指针为空,即找到最小值节点。因为二叉搜索树中左边的节点总是小于右边的节点,所以一直往左寻找。

从根节点开始,

image

往左查找,

image

再往左,到达“A”节点,没有左子节点了,停止搜索,找到最小值。

image

树的最大key值

二叉搜索树的最大 key 值节点从根节点开始一直沿着右子节点搜索,直到遇到节点的右子节点指针为空,即找到最大值节点。因为二叉搜索树中右边的节点总是大于左边的节点,所以一直往右寻找。

从根节点开始,

image

往右查找,

image

再往右,到达“H”节点,没有右子节点了,停止搜索,找到最大值。

image

赞(0) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 二叉搜索树的遍历
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏