树（一）：二叉查找树

爱被打了一巴掌 2023-06-21 15:24 103阅读 0赞

### [树（二）平衡二叉树][Link 1] ###

### [树（三）红黑树与平衡二叉树的区别][Link 2] ###

### 一、二叉查找树的定义 ###

二叉查找树（BST，Binary Search Tree），也称为二叉排序树或者二叉搜索树，是二叉树的一种。二叉查找树与二叉树一样，可以为空；另外，如果不为空，作为二叉查找树需满足以下性质：

1. 非空左子树的所有键值小于其根节点的键值；

2. 非空右子树的所有键值大于其根节点的键值；

3. 左、右子树都是二叉查找树。

为什么二叉查找树会具有这样的性质，因为二叉查找树的构造就是将值小的元素放到了左子树节点，值大的元素放到了右子树节点，这样可以增加查询的效率，其思想与二分查找法是一样的。

如下图所示，就是一棵二叉查找树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70][]

### 二、二叉查找树的最大元素与最小元素 ###

二叉查找树的最大元素一定是在树的最右端节点上，最小元素一定是在树的最左端节点上。当然，最大元素与最小元素也不一定是在叶子节点上，因为最左端的最小元素可能还有右子树，而最右端的最大元素也可能有左子树，如下图所示。

13是最小的元素，它在最左端节点上，但是它不是叶子节点，它还有右子树，其元素为14；而30是最大的元素，它是最右端的节点，但是它不是叶子节点，它还有左子树,其元素为27。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 1][]

[Link 1]: https://mp.csdn.net/postedit/103533241
[Link 2]: https://blog.csdn.net/y506798278/article/details/104275033
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191213155215867.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191213161001527.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70