数据结构：二叉树（一）·（重点）

前言

什么树？what？

树的概念与结构

概念：

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

结构：

有⼀个特殊的结点，称为根结点，根结点没有前驱结点。 除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1 、 T2 、 …… 、 Tm ，其中每⼀个集合 Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以 有 0 个或多个后继。因此，树是递归定义的。在树形结构中，⼦树之间不能有交集，否则就不是树形结构。（这里只讲树形结构）

如图：

 

树的相关术语

树的相关术语理解就行，没必要硬记。

⽗结点/双亲结点：

若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点。

如上图：1是2的⽗结点

⼦结点/孩⼦结点：

⼀个结点含有的⼦树的根结点称为该结点的⼦结点。

如上图：2是1的孩⼦结点

结点的度：

⼀个结点有⼏个孩⼦，他的度就是多少。

⽐如1的度为2，5的度为2，9的度为0

树的度：

⼀棵树中，最⼤的结点的度称为树的度。

如上图：树的度为 2（上述图中每个节点的度都为2）

叶⼦结点/终端结点：

度为 0 的结点称为叶结点。

如上图： 9、10、11... 等结点为叶结点

分⽀结点/⾮终端结点：

度不为 0 的结点。

如上图： 2、、4、5、6... 等结点为分⽀结点

兄弟结点：

具有相同⽗结点的结点互称为兄弟结点(亲兄弟)。

如上图：4、5是兄弟结点

结点的层次：

从根开始定义起，根为第 1 层，根的⼦结点为第 2 层，以此类推。

树的⾼度或深度：

树中结点的最⼤层次。

如上图：树的⾼度为 4

结点的祖先：

从根到该结点所经分⽀上的所有结点。

如上图： 1 是所有结点的祖先

路径：

⼀条从树中任意节点出发，沿⽗节点-⼦节点连接，达到任意节点的序列。

⽐如1到11的路径为： 1-2-5-11

⼦孙：

以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。

如上图：所有结点都是1的⼦孙

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

树的表示（数据结构）

常见表示方式：：双亲表⽰法，孩⼦表⽰法、孩⼦双亲表⽰法以及孩⼦ 兄弟表⽰法等。

如孩子兄弟表示法：

struct TreeNode {struct Node* child;struct Node* brother;int data;
};

如图：

这篇文章目前只讲简单的基础部分，后续会继续更新！！！

 作者希望在未来你们可以将自己的命运牢牢的握在自己手中，而不用满眼都是遗憾了！！！