树、二叉树和搜索二叉树详解

树、二叉树和搜索二叉树详解

引用

CSDN

1.

https://blog.csdn.net/2301_79697326/article/details/138905475

本文将带你深入了解树、二叉树和搜索二叉树的基本概念和结构。从树的基本概念到二叉树的定义、特殊二叉树的类型，再到二叉树的存储结构，最后简要介绍搜索二叉树。通过图文结合的方式，帮助你全面掌握这些数据结构的核心知识。

1. 树的概念及其结构

1.1 树的概念

树是一种非线性的数据结构，它是由N个数据元素组成的层次结构集合。树的逻辑结构类似于一颗倒过来的树，根节点向上，叶子节点向下。

• 有一个特殊的节点称为根节点，根节点没有前驱节点。
• 除根节点以外，其余M个节点被分为（M>0）个互不相交的集合T1, T2, T3......Tm，每个集合又是与结构相似的子树。每颗子树的根节点只有一个前驱，可以有0个或者多个后继。
• 树是递归定义的。

注意：树形结构中子树之间不能有交集，否则就不是树形结构。

1.2 树相关的概念

• 结点的度：一个结点含有子树的个数称为该结点的度。例如，上图中A的度为6。
• 叶结点或终端结点：度为0的结点称为叶子结点。例如，上图中的B，C，H，I等节点为叶子结点。
• 非终端结点或分支结点：度不为0的结点。例如，上图中的D, E, F, G等结点为分支结点。
• 双亲结点或父结点：若一个结点有子结点，这个结点就成为这个节点的双亲结点或者父结点。例如，上图中A是B的父亲结点。
• 孩子结点或子结点：一个结点含有子树的结点称为该结点的子结点。例如，上图中B是A的孩子结点。
• 兄弟结点：具有相同父结点的结点互称为兄弟结点。例如，上图中C是B的兄弟结点。
• 树的度：一颗树中最大结点的度称为树的度。例如，上图中树的度为6。
• 结点的层次：从根开始，根为第一层，根的子结点为第二层，依次类推。
• 树的高度或深度：树的结点的最大层次。例如，上图中树的高度为4。
• 堂兄弟结点：双亲在同一层的结点互为堂兄弟结点。例如，上图中H, I互为兄弟结点。
• 结点的祖先：从根到该结点的所经分支上的所有结点。例如，上图中所有结点都是A的子孙。
• 森林：有m（m>0）颗互不相交的树的集合称为森林。

1.3 树的表示

树的结构相比线性结构更为复杂，需要保存值域以及结点之间的关系。实际中树有多种表示方式，如双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法。这里主要介绍最简单的孩子兄弟表示法。

typedef int DataType;
struct Node
{
    struct Node* firstchild;    // 第一个孩子结点
    struct Node* pnextbrother;  // 下一个兄弟结点
    DataType _Data;             // 该结点储存数据
};

2. 二叉树概念及其结构

2.1 概念

一棵二叉树是节点的一个有限集合，该集合：

1. 或者为空
2. 由一个根结点加上两个别称为左子树和右子树的二叉树组成

从上图可以看出：

1. 二叉树不存在有度大于二的结点
2. 二叉树的子树有左右结点之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意二叉树都是由以下几种情况复合而成的：

2.2 现实中的二叉树

2.3 特殊的二叉树

1. 满二叉树：一个二叉树，如果每一层节点数都达到了最大值，则这个二叉树就是满二叉树。也就是说一个二叉树的层数为K，总结点的个数是，则它是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树引出来的，对于深度为K的，有n个结点的二叉树，当且仅当每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

2.4 二叉树的性质

1. 若规定根节点的层数是1，则一棵非空二叉树的第i层上最多有个结点。
2. 若规定根节点的层数是1，则深度为h的二叉树的最大结点数是。
3. 对任何一个二叉树，如果度为0其叶结点个数为，度为二的结点分支个数为，则有。
4. 若对规定根节点的层数是1，具有n个结点的满二叉树的深度。
5. 对具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号，则对于序号为i的结点有：

• 若i>0，i位置结点的双亲序号：，i=0，i为根节点编号，无双亲结点
• 若2i+1<n，左孩子序号：2i+1，2i-1>=n否则无左孩子
• 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

2.5 二叉树存储结构

想要实现二叉树的存储，可以用到前面所学到两种存储方法：链式存储和顺序存储。

2.5.1 链式存储

我们对每个结点设立两个指针，一个左孩子一个右孩子，同时存储数据。

typedef int DataNode;
struct Node
{
    struct Node *leftchild;
    struct Node *rightchild;
    DataNode val;
};

还可以使用三叉链的结构，多一个指针指向双亲结点。

typedef int DataNode;
struct Node
{
    struct Node *leftchild;
    struct Node *rightchild;
    struct Node* parent;
    DataNode val;
};

2.5.2 顺序存储

我们可以运用到前面的2.4中的第四点的结论，我们可以利用他们在顺序表中的编号来确定它们相互之间的关系，结构上是一个数组实际逻辑上是一个二叉树。

3. 搜索二叉树

搜索二叉树是一种特殊的二叉树，它的特点在于每一个结点的左结点总是小于右结点且右子树大于它的双亲结点。这里只是简单说一下不做多余的讲解。

它的结构如下图所示：