大家好，这里是彩妙呀~

今天给大家带来数据结构中的一个新概念：树。

本篇博客只是简单讲述一下有关树的知识点，不深入研究。如果想深入了解这方面的知识，可以看彩妙其他文章。

什么是树

想象一下一棵树的样子:

这棵树有树根、树干、树枝、树叶。而计算机中的树与这棵树大差不差，区别是：计算机中的树是倒着长的。根在上，叶子在下（其实更像族谱图）：

那么，如上图所示，就是我们计算机中的树。

树的概念

树是一种非线性的数据结构，它由n（n≥0）个有限节点组成，呈现出明确的层次关系。

为什么叫它“ 树 ”呢？你想象一下一棵倒着长的树就懂了——根在最上面，叶子在下面，和我们平时看到的自然树正好相反。最顶端的那个特殊节点叫根节点，它是整棵树的起点，没有所谓的“前驱”，也就是没有父节点。

下面，彩妙带着大家来看看树由哪些元素组成的：

• 首先，树有一个根部的节点（也就是顶部的节点），这个节点就是根节点。而我们的树就是从这个根开始发展。
• 由这个根节点衍生出的节点（通常就是用线段表示链接），就是子节点。而子节点也可以有属于自己的子节点，从而往下衍生。
• 不难发现，一个根节点可以连接许多的子节点。而对于这些处于同一层的子节点，叫做兄弟节点。
• 而对于最底部的节点，我们称他们为：叶子节点（也叫做终端节点）。

当然，树的概念不止于此，接下来，彩妙将带着大家详细拆解树的相关概念吧~

节点的度与树的度  与  叶节点（终端结点）/ 分支节点（非终端节点）

术语	定义
节点的度	一个节点所含有子树（即直接子节点）的个数
树的度	一棵树中，所有节点的度的最大值
叶节点（终端节点）	度为0的节点，即没有子节点的节点
分支节点（非终端节点）	度不为0的节点，即至少有一个子节点的节点

父亲节点 -- 孩子节点 -- 兄弟节点 -- 堂兄弟节点 -- 节点的祖先 -- 子孙

术语	定义
双亲结点（父结点）	若一个结点含有子结点，则这个结点称为其子结点的父结点
孩子结点（子结点）	一个结点含有的子树的根结点，即该结点的直接下层节点
兄弟结点	具有相同父结点的结点互称为兄弟结点
堂兄弟节点	双亲在同一层，但父结点不同的结点互为堂兄弟（亲兄弟不算堂兄弟）。
节点的祖先	从根到该结点所经分支上的所有结点（包括根，不包括自身）。
子孙	以某结点为根的子树中任一结点（不包括自身）。

树的高度 --- 森林

术语	定义
树的高度	树中结点的最大层次数。（上图中，层数为4）
森林	由 m（m > 0）棵互不相交的树的集合称为森林。（可理解为多个数在一起，但没有共同的祖先）

树的表示

相对于前面学过的顺序表、链表，树的存储结构相对而言要比较复杂：

我们需要一个结构体，既要保存数据，也要保存数据之间的联系。

而我们最常用的就是孩子兄弟保护法：

typedef int DataType;
struct Node
{
 struct Node* firstChild1; // 第一个孩子结点
 struct Node* pNextBrother; // 指向其下一个兄弟结点
 DataType data; // 结点中的数据域
};

特殊的树：二叉树

就像现实中的二叉树一样：

对应于计算机中的二叉树：

我们可以发现：从根节点开始：只有左右之分（不存在第三个孩子）。而左右树也被称作左子树与右子树（意味着每一个节点的度不超过2）。

二叉树可以是空树，也可以是由左右子树构成的树（度也可以为一，这就意味着这个节点只有一个子树，可以是右子树也可以是左子树）。

• 递归性：二叉树的定义天然是递归的——一棵二叉树由根节点、左子树和右子树组成，而左右子树本身也是二叉树。

• 有序性：二叉树中左右子树是有顺序的，即使只有一个子节点，也要区分它是左孩子还是右孩子，这一点与一般树不同。

• 深度性质：在非空二叉树中，第i层最多有 2^(i-1) 个节点（i≥1）；深度为k的二叉树最多有 2^k - 1 个节点（k≥1），这就是满二叉树的情况。

• 存储方式：可以用链式存储（节点包含数据、左指针、右指针）或顺序存储（用数组，适合完全二叉树）。

特殊二叉树类型剖析

二叉树的衍生就非常多：堆，二叉搜索树、AVL树、红黑树、B系列树等。

满二叉树

特征：一棵深度为 k ，且含有 2^k - 1 个节点的二叉树。也就是说，除了叶子节点外，每个节点都有左右两个孩子，并且所有叶子都在同一层。
应用场景：满二叉树是一种理想形态，常用于理论分析，例如堆排序中的堆实际上是一棵完全二叉树，而满二叉树是完全二叉树的特例。

完全二叉树

特征：深度为k、有n个节点的二叉树，当且仅当每个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树。简单说，除了最后一层，上面各层都是满的，最后一层的节点都靠左排列。
应用场景：完全二叉树可以用数组高效存储（父子节点下标关系：父节点i的左孩子为2i，右孩子为2i+1），因此常用于实现堆（优先队列）、线段树等。

二叉搜索树（BST，Binary Search Tree）

特征：对于树中的每个节点，其左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。且左右子树本身也分别是二叉搜索树。
应用场景：二叉搜索树支持高效的动态数据集合操作（查找、插入、删除），平均时间复杂度为O(log n)。但若插入数据有序，可能退化成链表（O(n)），因此需要平衡优化。

后续C++中STL库里，我们就要学习有关二叉搜索树的应用：set与map

平衡二叉树（如AVL树、红黑树）

特征：是一种自平衡的二叉搜索树，它保证任何节点的左右子树高度差的绝对值不超过1（或满足某种平衡条件），从而避免退化为链表，确保查找效率始终在O(log n)。
应用场景：广泛用于需要频繁增删查改的场景，例如数据库索引、Java中的TreeMap、C++ STL中的map等。

---

好了，本篇博客只做对数这个数据结构的简要说明，有关树的其他知识可以关注彩妙其他文章哦，我们下篇再见~