数据结构与算法高级：树的概念与二叉查找树详解

数据结构与算法高级：树的概念与二叉查找树详解

引用

CSDN

1.

https://m.blog.csdn.net/qq_37481675/article/details/139962193

在计算机科学领域，数据结构是算法的基础。其中，树作为一种非线性数据结构，在实际应用中扮演着重要角色。本文将详细介绍树的概念、分类以及二叉查找树的特性，帮助读者更好地理解这一基础数据结构。

树的概念

在实际场景中，很多数据的逻辑关系并不是线性的，常常存在着一对多，甚至是多对多的情况。这种数据结构被称为树。

在数据结构中，树的定义如下：

• 树（tree）是n（n≥0）个节点的有限集。
• 当n=0时，称为空树。
• 在任意一个非空树中，有如下特点：
• 有且仅有一个特定的称为根的节点。
• 当n>1时，其余节点可分为m（m>0）个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

如上图所示，一颗标准的树包含以下节点类型：

• 根节点（root）：没有父节点，这里是节点1。
• 叶子节点（leaf）：树的末端，没有“孩子”，这里是节点5、6、7、8。
• 中间节点或枝节点：有父节点，也有孩子，这里是节点2、3、4。

树的最大层级数被称为树的高度或深度。上图这个树的高度是4。

树的分类

二叉树

二叉树（binary tree）是树的一种特殊形式。每个节点最多有2个孩子节点，可能只有1个，也可能没有孩子节点。

满二叉树

一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。

完全二叉树

对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。

二叉树的存储

二叉树属于逻辑结构，可以使用链表和数组进行存储。

链式存储

二叉树的每一个节点包含3部分：

• 存储数据的data变量
• 指向左孩子的left指针
• 指向右孩子的right指针

数组存储

使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺，则数组的相应位置也空出来。

寻址方式：一个父节点的下标是n，那么它的左孩子节点下标就是2×n+1、右孩子节点下标就是2*(n+1)。对于一个稀疏的二叉树（孩子不满）来说，用数组表示法是非常浪费空间的。所以二叉树一般用链表存储实现（二叉堆除外）。

二叉查找树

二叉查找树（binary search tree）在二叉树的基础上增加了以下几个条件：

• 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
• 如果右子树不为空，则右子树上所有节点的值均大于根节点的值
• 左、右子树也都是二叉查找树