二叉查找树

什么是二叉查找树

二叉查找树(BST)又名二叉查找树、二叉搜索树

  • 具备什么特性呢?

1.左子树上所有结点的值均小于或等于它的根结点的值。

2.右子树上所有结点的值均大于或等于它的根结点的值。

3.左、右子树也分别为二叉排序树。

如图示例:

R4eTqldENf.png!large

如要查找为10的节点

  1. 从根节点开始,因为10>9,找比9大的,右子树,找到13。
  2. 10<13,找左子树,找到11
  3. 10<11,找左子树,找到10

这种方式正是二分查找的思想,查找所需的最大次数等同于二叉查找树的高度。

在插入节点的时候也是利用类似的方法,通过一层一层比较大小,找到新节点适合插入的位置。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!