数据结构：树的基本概念

树

树的概念与结构

树是一种非线性的数据结构，由N（N≥1）个有限结点构成，之所以称为树，是因为它的结构看起来像一棵倒挂的树。

根结点：根结点是没有前驱结点的结点，如上图中的根结点就是A。
除根结点外，其他结点被分为M(M≥0)个互不相交的集合，每一个集合就称为一个子树，每一个子树又是与树类似的结构。每一个结点都能找到对应的前驱结点，所以说树是递归定义的。

注：子树是不相交的。
除根结点外，其他结点有且仅有一个父结点。
有N个结点的树有N-1条边。

树的相关术语

父结点/双亲结点：若一个结点含有子结点，则这个结点称为其子结点的父结点。比如B的父结点就是A。
子结点/孩子结点：一个结点含有的子树的根节点就是该结点的子结点。比如B、C、D、E就是A的子结点，也是A的孩子。
结点的度：一个结点有几个孩子，他的度就是多少。比如A结点的孩子是B、C、D、E，结点A的度就是4
树的度：一棵树中，最大的结点的度称为树的度。这棵树中最大结点的度是4，树的度就是4。
叶子结点/终端结点：度为 0的结点称为叶结点。这棵树中的叶子就是F、G、K、I、J。
分支结点/非终端结点：度不为0的点。
兄弟结点：具有相同父结点的结点互称为兄弟结点。比如B和C互称为兄弟结点。
结点的层次：从根开始定义起，根为第一层，根的子结点为第二层，以此类推。
**树的高度或深度：**树中结点的最大层次。这棵树的深度就是4。
结点的祖先：从根到该结点所经分支上的所有结点。比如A是所有结点的祖先。
路径：一条从树中任意结点出发，沿父结点-子结点连接，达到任意结点的序列。比如A到K，路径就是1->3->8->11
子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。
森林：由m（m＞0）棵互不相交的树的集合称为森林。

树的表示

树作为一种特殊的数据结构在表示上是有一定困难的，前人发明了“双亲表示法”，“孩子兄弟表示法”等，这里举一种最常用的表示法，“孩子兄弟表示法”。

从最左边的孩子开始找起，如果有兄弟则指向右边的兄弟。

大致可以表示为这样：

箭头表示该指针指向的结点。

二叉树

在树形结构中，我们最常用的是二叉树。二叉树表示有限个结点的集合，它是由左右两个子树组成或者为空。

二叉树的左右子树是有先后次序之分的，不能颠倒，所以二叉树也是有序树。
任意二叉树都是由以下几种情况复合而来的：

特殊的二叉树

满二叉树

满二叉树是一种特殊的二叉树，它的每一层结点个数都是满的。

第一层有2⁰个结点，第二层有2¹个结点，依此类推，一个k层的满二叉树，第k层的结点个数为2^k-1。满二叉树的总结点个数为2^k-1.

也就是说，一个k层的二叉树，如果它的总结点个数为2^k-1，那么它就是满二叉树。

完全二叉树

完全二叉树是一种效率很高的数据结构，完全二叉树是由满二叉树引来的，对于一个二叉树，如果它的每个结点都与其每个编号对应的话，那么它就是完全二叉树。

完全二叉树的每个结点都是和编号对应的，对于完全二叉树的任意一个结点，先有左孩子才能有右孩子。

二叉树的性质

二叉树的存储结构

二叉树一般可以使用两种存储结构：顺序存储和链式存储。

顺序结构

顺序结构底层就是数组，一般更适合用来存储完全二叉树，因为不是完全二叉树的话会造成空间浪费。


现实中我们通常把堆（一种二叉树）使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链。后面学到红黑树等会用到三叉链。

三叉链比二叉链多了一个指向父结点的指针。