数据结构（四）—— 堆和二叉树（上）

制作不易，三连支持一下呗！！！

---

前言

这篇博客我们将进行更加复杂的一种数据结构的学习——树形结构。

---

一、树的概念及结构

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合，把它叫做树，因为它的形状看起来像一颗倒挂的数，也就是说它是根朝上，而叶子朝下的。

• 有一个特殊的结点，称为根节点，根节点没有前驱节点。
• 除根节点外，其余节点被分为M（M>0）个互不相交的集合T1，T2，……Tn。其中每一个集合Ti（1<=i<=n）又是一颗结构与树类似的子树。
• 因此，树是递归定义的

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

      

     树中的基本概念：

1. 节点的度：一个节点含有的子树的个数称为该节点的度。如上图 根节点的度为3
2. 叶结点或终端结点：度为0的节点称为叶结点，如上图5节点为叶结点。（没有孩子的节点）
3. 非终端结点或分支节点：度不为0的结点，如上图2,3,4节点。
4. 双亲节点或父节点：若一个节点含有子节点，那么这个节点称为其子节点的父节点，如上图2是5的父节点
5. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点，如上图中5是2的子节点
6. 兄弟节点：具有相同父节点的节点互称为兄弟节点，如上图2,3,4互为兄弟节点
7. 树的度：一棵树中，最大的节点的度称为节点的度，如上图，树的度为3
8. 节点的层次：从根开始定义起，根为第一层，根的子节点为第二层，依此类推
9. 树的高度或深度：树中节点的最大层次，如上图，树的高度为3
10.  堂兄弟节点：双亲在同一层的节点互为堂兄弟节点
11. 节点的祖先：从根到该节点所经分支上的所有节点，如上图1是所有节点的祖先
12. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙，如上图所有节点都是1的子孙
13. 森林：由m（m>0）棵互不相交的树组成的集合叫做森林

树型结构的表示：

1.顺序表表示法

假设已知一棵树的度为N，则每个节点中可以定义一个N个元素的指针数组，数组中的每一个指针都指向这个节点的孩子。但是只是这样的结构会导致很大的空间浪费，有很多节点的孩子是没有N个的，可能都没有孩子节点。所以我们类似顺序表定义一个size和ccapacity来记录当前节点的孩子节点的个数不够的话就要扩容。

struct TreeNode
{
	int val;
	//顺序表
	struct TreeNode** a;
	int size;
	int capacity;
};

但是这种表示方法并不常用。 

2.左孩子右兄弟表示法

树的结构如下：

//左孩子右兄弟
struct TreeNode
{
	int val;
	struct TreeNodde* leftChild;
	struct TreeNodde* nextBrother;
 
};

不管有多少兄弟节点，都只记录它的第一个孩子节点。没有孩子或兄弟就指向NULL。

这样就可以讲这棵树的所有节点都遍历一遍。

这种表示方法，避免了空间的浪费，不管有多少孩子 ，都只需要记录两个指针即可。

3.双亲表示法（只适用于完全二叉树）

这种表示方法是将树存放在一个数组中，每个节点保存一份数据和它的双亲节点在数组中的下标。

如上图那棵树以双亲表示法表示的图例：

这也体现了逻辑结构和物理结构不一定是一致的。 当然，根节点也不一定存在下标为0处。

二、二叉树的概念及结构

1.概念

二叉树：每个节点最多有两个孩子节点的树。

注：空树也是二叉树！！！

1.二叉树不存在度大于2的节点。

2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

特殊的二叉树：

满二叉树：一个二叉树，如果每一个节点的度都达到最大值，那么它就是满二叉树，也就是说，假设一颗满二叉树的层数为K，那么它的总节点数为2^k-1.

完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树的概念是由满二叉树引出的，对于深度为K的，有n个节点的二叉树，当且仅当其每一个节点都与深度为K的满二叉树中编号为1~n的节点一一对应时称之为完全二叉树，特别的，满二叉树是一种特殊的完全二叉树。

以上是两组经典的对比，可以帮助我们更好的理解它们的区别！ 

2.二叉树的存储结构

1.顺序存储（数组）（建议适用于完全二叉树）

一层一层挨个按顺序存储到数组中，物理结构上是数组，逻辑结构上是完全二叉树。

这样存储之后父节点和子节点之间的下标之间是建立了一种关系的：

leftchild=2*parent+1

rightchild=2*parent+2

parent=（child-1）/2

如果不是完全二叉树，则要把空位置在数组中空出来，这样才满足上述规律！！！

2.链式存储

结构：一个节点中存储两个节点（左右孩子）

struct TreeNode
{
	int val;
	struct TreeNodde* leftChild;
	struct TreeNodde* rightChild;
 
};

---

总结

二叉树（上）介绍了树形结构中的一些概念和结构，下篇博客我们将来利用这些结构来实现二叉树