【数据结构】——树和二叉树相关概念（全网超级详解）

 

 创作不易，家人们来一波三连吧？！

前言

世界上最大的树--雪曼将军树，这棵参天大树不是最长也不是最宽，是不是很奇怪，大只是他的体积是最大的，看图片肯定是感触不深，大家可以自己去看看

 扯远了，这次我们介绍的是一种新的数据结构--树

树的定义

之前的栈和队列，都是一对一的线性结构，而现在是一对多的数据结构--" 树 "。

树是由n个结点的有限集。当n=0的时候，也称之为空树，当n>1的时候，其余结点又可以分为m棵子树，同时这些子树是互不相交的。在任意一颗非空树中：有且仅有一个称为根的结点，也就是最上面的结点。

从图中可以看出，B,C是A的子树，D又是B的子树，其中，A为根结点

 

上面两张图就是对于定义里面的子树是互不相交的，，所以这两棵树是错误的画法。

结点的分类 

树的结点包含一个数据元素和指向若干子树的分支

1.结点拥有的子树树称为结点的度

2.度为0的称之为叶结点也是终端结点

3.树的度是树内各结点的度的最大值

结点间的关系

 结点的子树称为该结点的孩子，反正该结点称为孩子的双亲，同一个双亲的孩子称为兄弟或者姐妹，结点的祖先是从根到该结点上所有路径的结点（可千万别以为只有根结点是祖先），反之以某结点为根的子树任意一结点都称为该结点的子孙。

树的其他概念

结点的层次是从根开始的，根为第一层，根的孩子为第二层。双亲在同一层的结点互为堂兄弟，树中结点的最大层次称为树的深度或高度

那么这颗树的深度或者高度就是4

  森林是n课互不相交的树的集合，也就是很多课树在一起，但是他们不相交，上面是子树不能相交，这里分清。

对比线性表与树，他们的结构其实相差很大

1.线性结构

1.第一个数据元素：无前驱

2.最后一个元素：无后继

3.中间元素一个前驱，一个后继

2.树结构 

1.根节点：无双亲，唯一

2.叶节点：无孩子，可以多个

3.中间结点：一个双亲多个孩子

树的存储结构 

1.双亲表示法

 除了根结点外，其余结点可以没有孩子，但肯定有双亲，那么我们可以用一片连续的空间存储树的结点，在结点中附设一个指示器指明双亲结点在数组的位置。

那根结点的双亲位置我们可以设置为-1，这样就很好解决问题了

/*树的双亲表示法结点结构定义*/
#define MAXSize 100
typedef int TEDataType; 	/* 树结点的数据类型，目前暂定为整型*/
typedef struct PTNode	/*结点结构*/
{
    TEDataType data;	/*结点数据*/
	int parent;	/*双亲位置*/
} PTNode ;
 
typedef	struct	/*树结构*/
{
	PTNode nodes[MAXSize]; /*结点数组*/
	int r,n;	/*根的位置和结点数*/
} PTree;

 这样的存储结构我们可以很快可以通过parent这个指示器去找到它的双亲结点的位置，但是如果要找孩子我们就需要遍历了，比较麻烦，那我们增加一个孩子的指示器呢，也就是再增加一个孩子的域

如果没有孩子，那我们就 设置为-1，如果有那么就表示第一个孩子，如果有两个孩子，知道第一个，那么第二个也就很清楚了

但是这种结构如果要知道兄弟又要增加，所以到最后可能会有些复杂，这也就意味着系统的空间开销很大

2.孩子表示法

我们可以设置一个一个结点有多个指针域，这些指针用来指向孩子结点，同时用一个位置来存储指针的个数，这样可以避免多余的空间开销

 

 这样所以可以，但是你看这个结构也是非常复杂的，每个结点的结构都有所不同，所以运行起来可能会对时间有所损耗

通过观察结构，我们可以把每个结点都存储到一个顺序结构的数组中，然后再把他们的孩子建立一个单链表，这些个孩子结点的指针又指向结点的另外一个孩子，这样就可串起来

这就是我们的孩子表示法，需要找这个结点或者是兄弟结点直接遍历就行了，但是如果需要找到双亲那么又可能很麻烦

3.左孩子又兄弟表示法

有了上面的认识我们可以用结点的第一个孩子指向它的兄弟结点，这样我们也可以很轻松找出某个结点的位置，但是如果要找双亲那么也会很麻烦，哈哈，但是如果增加一个指针指向双亲那么就可以解决这个问题了

 

它的结构表示就是

typedef int TEDataType;
typedef struct TreeNode
{
	TEDataType data;
	struct TreeNode* Leftchild, * Rightchild;//左孩子和右孩子
}TreeNode;

 由于这种结构的特性可以很快找到该节点的位置，所以在文件目录中通常用这种表示法

比如随便打开一个文件，里面有很多子文件那么这些子文件也就是兄弟关系，他们逐个遍历，最终把把整个目录表示出来

二叉树的概念

二叉树的定义

二叉树是n个结点的有限集合，n=0,称为空树，n>0的时候由一个根节点和两个互不相交的树组成，分别称为根结点的左子树和右子树

左图就不是二叉树，因为D有三棵子树

二叉树的特点

二叉树的有顺序规定的，所以二叉树又有下面几种形态

空二叉树

只有根结点

根节点只有左子树

根结点只有右子树

根结点既有左子树又有右子树

 

如果是三个结点的树，那么只会有树1和后面4棵树中的任意一个，因为不分顺序，而二叉树是分顺序的，所以上图代表了不同的二叉树 

 特殊二叉树

1.斜树

所有结点都只有左子树的二叉树称为左斜树。所有结点都只有右子树的称为右斜树。两者都叫斜树

2.满二叉树

所有分支结点都有左子树和右子树，并且所有的叶子都在一层上面，这样的树叫满二叉树

3.完全二叉树

在编号为i的结点与同样深度的满二叉树中编号为i的结点位置完全相同，称为完全二叉树，

所有满二叉树也是一种特殊的完全二叉树

 

二叉树的性质 

1.在二叉树中第i层至多有2^（i-1）个结点,所有结点也就是每一层的加起来所以是一个等比求和可以得所以结点至多有2^i-1个结点

2.对于任何一颗二叉树，如果叶结点数为n0,度为2的结点数为n2，则n0=n2+1;

  对于这个性质其实很好理解，就是当我们增加一个度为1的结点的时候，会减少一个度为0的结点，同时也会增加一个度为0的结点，所以总体来说度为0的结点是不变的

  如果我们增加的是度为2的结点那么就会减少一个度为1的结点，同时也会增加一个度为0的结点，所以度为0的结点总是比度为2的结点大1的，这是恒成立的

3.具有n个结点的完全二叉树的深度为[log2n]+1

4.对于一颗二叉树，如果按照从上至下从左至右的数组顺序存储对所有结点从0开始编号，对于序号为i来说

如果i=0,无双亲，根节点，如果i>0;则双亲为（i-1)/2;

如果2*i+1<n,则左孩子序列为2*i+1;如果2*i+1>=n则无左孩子

 如果2*i+2<n,则右孩子序列为2*i+2;如果2*i+2>=n则无右孩子

二叉树的存储结构 

 1.顺序存储

顺序存储就是把二叉树存储在数组中，用数组的下表表示孩子和双亲的位置，所有这种表示法一般只是用在了完全二叉树，其他的用起来太浪费空间了，比如斜树就会浪费大量空间

它在物理上是一个数组，但是逻辑上又是一个二叉树，这里不要弄混

2.链式存储

二叉树每个结点最多有两个孩子，所以设置一个数据域和两个指针域，这样的链表也叫二叉链表，这样做比上面的顺序存储更加容易去理解

 

如果需要还可以增加一个双亲指针，这样就变成了三叉链了。

对于树和二叉树的介绍就先到这里，后续的使用和算法会在下篇文章介绍