如何实现数据结构中的二分搜索树操作？

本文共计6702个文字，预计阅读时间需要27分钟。

一、二叉树+树结构在介绍这种结构之前，我们先来说一下树这种结构存在的意义。在我们现实场景中，比如图书馆，我们可以根据分类快速找到我们想要的书籍。例如，我们要找一本叫做《XXX》的书，我们可以根据书名快速定位。

一、二叉树

说树这种结构之前，我们要先说一下树这种结构存在的意义。在我们的现实场景中，比如图书馆，我们可以根据分类快速找到我们想要找到的书籍。比如我们要找一本叫做《Java编程思想》这本书，我们只需要根据，理工科 ==> 计算机 ==>Java语言分区就可以快速找到我们想要的这本书。这样我们就不需要像数组或者链表这种结构，我们需要遍历一遍才能找到我们想要的东西。再比如，我们所使用的电脑的文件夹目录本身也是一种树的结构。

 

从上面的描述我们可知，树这种结构具备天然的高效性可以巧妙的避开我们不关心的东西，只需要根据我们的线索快速去定位我们的目标。所以说树代表着一种高效。

 

在了解二分搜索树之前，我们不得不了解一下二叉树，因为二叉树是实现二分搜索树的基础。就像我们后面会详细讲解和实现AVL（平衡二叉树），红黑树等树结构，你不得不在此之前学习二分搜索树一样，他们都是互为基础的。

1.1 二叉树的定义

二叉树也是一种动态的数据结构。每个节点只有两个叉，也就是两个孩子节点，分别叫做左孩子，右孩子，而没有一个孩子的节点叫做叶子节点。每个节点最多有一个父亲节点，最多有两个孩子节点(也可以没有孩子节点或者只有一个孩子节点)。对于二叉树的定义我们不通过复杂的数学表达式来叙述，而是通过简单的描述，让大家了解一个二叉树长什么样子。

• 1、只有一个根节点。
• 2、每个节点至多有两个孩子节点，分别叫左孩子或者右孩子。