目录

一、树的定义

二、树的基本术语

1. 结点的度、树的度

2. 叶子结点、分支结点

3. 孩子结点，双亲结点、兄弟结点、堂兄弟结点

4. 路径、路径长度

5. 祖先、子孙

6. 结点的层数、树的深度（高度）、树的宽度

7. 森林

三、树的表示

---

一、树的定义

现实中的树：

        树（tree）是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。

        把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的，树的基本结构如图所示：

在树中，通常将数据元素称为结点（node）

当n=0时，称为空树。

任意一个非空树都满足以下条件：

1. 有且仅有一个特定的称为根（root）的结点。根节点没有前驱结点
2. 当n>1时，除根节点之外的其余结点被分成m（m>0）个互不相交的有限集合T1，T2，......，Tm，其中每个集合又是一棵树，并称为这个根结点的子树（subtree）。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。

        需要强调的是，树中根结点的子树之间是互不相交的；树形结构中，子树之间不能有交集，否则就不是树形结构。

---

二、树的基本术语

1. 结点的度、树的度

一个节点含有的子树的个数称为该结点的度（degree）。

一棵树中，最大的结点的度称为树的度。

如图示，结点A的度是2，结点B的度是3，由于在这棵树中结点B的度最大，所以该树的度是3。

2. 叶子结点、分支结点

度为0的结点称为叶子结点（leaf node），也称终端结点。
度不为0的结点称为分支结点（branch node），也称为非终端结点。

如图中的D、I、F、G、H是叶子结点，其余的A、B、C、E都是分支结点。

3. 孩子结点，双亲结点、兄弟结点、堂兄弟结点

一个结点含有的子树的根结点称为该结点的孩子结点（children node），也叫子结点。如图结点B是结点A的孩子。

若一个结点含有孩子节点，则这个结点称为其孩子节点的双亲结点（parent node），也叫父结点。如图结点A是结点B的双亲。

具有相同双亲结点的结点互称为兄弟结点（brother node）。如图B、C是兄弟结点。

双亲在同一层的结点互为堂兄弟结点。如图中的D和G是堂兄弟结点。

4. 路径、路径长度

如果树的结点序列n_1，n_2，n_3，...，n_k  满足如下关系：结点n_i是结点n_i+k的双亲（1 ≤ i ≤ k），则n_1，n_2，n_3，...，n_k  称为一条由n_1至n_k的路径（path）；路径上经过的边数称为路径长度（path length）。显然，在树中路径是唯一的。

如图，从结点A到结点I的路径是ABEI，路径长度是3。

5. 祖先、子孙

如果从结点x到结点y之间有一条路径，那么x就称为y的祖先（ancestor），y称为x的子孙（descendant）。显然，以某个结点为根的子树中的任意一个结点都是该结点的子孙。

如图中，结点A、B、E均为结点I的祖先，结点B的子孙有D、E、F、I。

6. 结点的层数、树的深度（高度）、树的宽度

从根开始定义，规定根结点的层数（level）为1，根的子节点为第2层，以此类推；

树中所有结点的最大层次称为树的深度（depth），也称为树的高度。

树中每一层结点个数的最大值称为树的宽度（breadth）。

如图所示，结点D的层数是3，树的深度是4，树的宽度是5.

7. 森林

由m（m>0）棵互不相交的树的集合称为森林（forest）

如图所示为由三棵树构成的森林：

---

三、树的表示

        树是一种非线性的数据结构，比较复杂。想要表示它，不仅需要表示各个结点的数据值，还需要表示结点与结点之间的关系。

        实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。其中最常用的是孩子兄弟表示法。
孩子兄弟表示法（children brother express）：又称为二叉链表表示法，其方法是链表中的每个结点除数据域外，还设置了两个指针分别指向该结点的第一个孩子节点，和它的右兄弟，如图所示：

下面是孩子兄弟表示法的结点存储结构定义：

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

感谢观看，支持！