树的概念及结构

树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合，之所以叫做树是因为它看起来就像一颗倒着挂的树，只不过这棵树是根朝上，叶朝下的。

• 有一个特殊的结点，称为根结点，根结点是没有前驱结点的。
• 除根结点外，其余结点被分为M（M>0）个互不相交的集合T1、T2、…Tm，其中每个集合Ti（1<=i<=m）又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或者多个后继。
• 树是递归定义的。

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

树的基本概念

接下来：以上图为例子来解释树的基本概念。

结点的度：一个结点含有的子树的个数称为该结点的度；A结点的度为3。

叶结点或终端结点：度为0的结点称为叶结点（或终端结点），简单来说就是没有孩子的结点就是叶结点；E、K、L、M结点称为叶结点。

非终端结点或分支结点：该结点指度不为0的结点；如B、F、C、D、J。注意：A结点也可以是分支结点。

双亲结点或父结点：若一个结点含有子结点，则该结点称为其子结点的父结点；如A是B、C、D结点的父结点。

孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；如B、C、D结点是A结点的子结点。

这里也要注意一点，有的地方也会把**F、J**称为是A结点的子结点，其实可以这么说但是不严谨，我们正常情况下还是会默认把F、J称为是子孙结点。

兄弟结点：具有相同父结点的结点互称为兄弟结点，注意这里是指亲兄弟，堂兄弟表兄弟都不算数；如H、I、G可以互称为D结点的兄弟结点。

树的度：一棵树中，最大的结点的度称为树的度；上图树的度为3。

结点的层次：从根开始定义起，根称为第一层，根的子结点称为第二层。

树的高度或深度：树中结点的最大层次；上图的树的高度为4。也有的地方收到数组的影响，从0开始计数，即树的高度是3，但还是建议按照第一种方式来计树的高度。假如说我们按照第二种方式，如果只有1个结点的话我们可以说树的高度是0，但是如果是空树的情况呢？空树只能是-1了，这样其实也可以，但是非常别扭。所以建议用第一种方式来计算树的高度。

堂兄弟结点：双亲在同一层的结点会称为堂兄弟；如

结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先。

子孙：以某结点为根的子树中任一结点都称为该结点的子孙。上图所有的结点都是A结点的子孙。

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

小总结：任何一棵树都是由根和子树组成的。而子树又是由根和子树组成的，子树又是由根和子树组成的，所以我们说树是递归定义的，结束的标标志就是叶结点，即没有子树就递归结束。而二叉树是一种特殊的树，只能有两棵子树。

这棵树就是由根A和三棵子树组成的。

下面是树的一些特点：

• 子树是不相交的；
• 除了根结点外，每个结点有且仅有一个父结点；
• 一棵N个结点的树由N-1条边。

树的结构

树结构非常复杂，表示起来也是复杂一些。我们既要保存值域，也要保存各个结点之间的关系。树的表示方法有很多种：双亲表示法、孩子表示法、双亲孩子表示法以及孩子兄弟表示法等。

现在，我们来看看最常用的孩子表示法。

typedef int DataType;
struct TreeNode
{
  struct TreeNode* firstChile1;//第一个孩子结点
  struct TreeNode* pNextBrother;//指向下一个兄弟结点
  DataType data;//结点种的数据域
};

这种表示方法也叫左孩子右兄弟表示法。

我们还是以下面这张图为例：

我们现在就用孩子表示法来表示该图，请看：

这种左孩子有兄弟表示法能够很好的表示这个树形结构。但是在实际当中用途不大，树在实际当中的应用场景就比如文件系统；在数据结构中，最常用的还是二叉树。

二叉树概念及结构

概念

一棵二叉树是结点的一个有限集合，该集合：要么为空；要么就是由一个根结点加上两棵别称为左子树和右子树的二叉树组成的。

二叉树特点：

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

这里需要注意的是：对于任意的二叉树都是由一下几种情况复合而成的。

特殊的二叉树

特殊的二叉树总共有两种：满二叉树和完全二叉树。

满二叉树：一个二叉树中如果每一个层的结点都达到最大值，则这个数就是满二叉树。如果我们设一个二叉树的层数为k，且总结点数是2的k次方-1，那么这个树就是满二叉树。

完全二叉树：完全二叉树是由满二叉树引出来的。对于深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树种编号从1至n的结点一一对应时称为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

简单来说，满二叉树就是除了最后一层之外，其余每层的结点都只有两个子结点。

满二叉树是也是完全二叉树，但是完全二叉树不一定就是满二叉树。类似于长方形与正方形的关系。

二叉树结论

1.对于任何一棵二叉树（树为非空），如果度为0其叶结点个数为n0，度为2的分支结点个数为n2，则有n0=n2+1。简单来说就是度为0的永远比度为2的多一个。

举个例子：某二叉树共有399个结点，其中199个度为2的结点，则该二叉树种的叶子结点（就是度为0的结点）为200个。

2.二叉树中度为1的要么只有1个，要么就是没有（满二叉树中度只有度为0和度为2的，没有度为1的；而完全二叉树中度为1的要么有1个要么就是没有）。

例题：在具有2n个结点的完全二叉树中，叶子结点个数为（）？

由这个题我们就可以得出一个结论：在具有2n个结点的完全二叉树中，叶子结点个数为n。

再来看一个题：

一个具有767个结点的完全二叉树，其叶子结点个数为？

二叉树的存储结构

二叉树一般分为两种结构存储，分为顺序结构和链式结构。

顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中只有堆才会使用数组来存储。所以，二叉树顺序存储在物理上其实就是一个数组，在逻辑上就是我们想象出来的一棵树。

现在我们来看一下二叉树顺序存储的逻辑结构和物理结构。

二叉树顺序存储的逻辑结构（逻辑结构是我们自己想象出来的）就是一棵树；

物理结构就是一个数组。

如果我们知道孩子结点的下标，如何推算父结点的下标呢？

比如：下标为5和6的结点，它们的父结点是下标为2的结点。这里就直接说结论吧，知道子节点来求父结点，二者之间的关系就是parent=（chile-1）/2。

如果我们知道父结点的下边如何推算子节点的下标呢？

比如：下标为1的结点是下标为3和4结点的父结点。知道父结点想要求子节点的话，此时二者之间就是leftchild=parent*2+1；rightchild=parent*2+2。

以上就表示二叉树的值在数组位置中父子下标关系。注意，这里规定的是下标必须是从0开始的，否则关系就乱套了。

二叉树的顺序存储适合满二叉树或者完全二叉树，如果不是满二叉树或者完全二叉树的话就很有可能造成空间浪费。就比如说下面这棵树就不适合用二叉树的顺序结构来存储。

上图这棵树如果非要用二叉树的顺序结构来存储的话就会造成空间浪费。

所以，二叉树的顺序存储适合完全二叉树（满二叉树是一种特殊的完全二叉树）。

链式存储

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

下面是二叉树和三叉树的结构：

typedef int STDataType;
//二叉树
struct BinaryTreeNode
{
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
  STDataType data;
};
//三叉树
struct TreeNode
{
  struct TreeNode* parent;
  struct TreeNode* left;
  struct TreeNode* right;
  STDataType data;
};

二叉树的顺序结构

在这之前，我们之前的数据结构，无论是顺序表、链表、还是栈和队列那里，都只是单纯的的存储数据。而现在这里，我们可以通过二叉树这个数据结构来实现一些其它的价值，就比如说排序…

普通的二叉树不适合用数组来存储，因为可能会有大量的空间浪费。而完全二叉树很适合使用顺序结构来存储。现实中我们通常把堆（一种二叉树）使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

堆的概念及结构

堆的数据结构是完全二叉树或一堆数组，因为堆在逻辑上是一棵完全二叉树，在物理结构上是一个一维数组。

堆的性质

• 堆的某个结点总是不大于或者不小于其父结点的值；
• 堆总是一棵完全二叉树

小根堆：树中所有的父结点都小于或等于自己的孩子结点。

大根堆：树中所有的父结点都大于或等于自己的孩子结点。