【数据结构】第九站：树和二叉树

一、树的概念及结构

1.树的概念

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

1.有一个特殊的结点，称为根结点，根节点没有前驱结点

2.除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

3.因此，树是递归定义的。

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

上图中三种结构均不为树，其实是另一种数据结构——图

2.树的相关概念

3.树的表示

对于树的表示，由于它的孩子结点的个数是不确定的，所以它的定义是比较麻烦的

1.如下图所示，是一种定义结点的方式，根据树有多少度去定义多少个结点。这种方式为了简洁，也可以使用一个指针数组来简化代码

2.使用一个顺序表，显然第一种方式太浪费空间了，所以我们可以使用一个顺序表来调整每个结点的孩子个数

struct TreeNode
{
  SeqList s1;
  int data;
};

但是这种结构太过于繁琐

3.左孩子右兄弟

这种方法是只定义两个指针来控制的，一个指针永远只指向左边的孩子，另外一个指针永远只指向它的右边的兄弟结点。这样就可以将整个树给组织起来

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

二、二叉树的概念及结构

1.概念

一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

由此可以看出

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

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

注意：对于任意的二叉树都是由以下几种情况复合而成的：

2.特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 2^k-1，则它就是满二叉树。

2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

3.二叉树的性质

1.若规定根节点的层数为1，则一颗非空二叉树的第i层上最多有2^(i-1)个结点。

2.若规定根节点的层数为1，则深度为h的二叉树最大的结点数是2^h-1

3.对于任何一颗二叉树，如果度为0的叶结点个数为n0，度为2的分支结点个数为n2，则有n0=n2+1

4.若规定根结点的层数为1，具有N个结点的满二叉树的深度为logN

对于性质3，我们可以画图来理解，对于一开始只有一个结点的二叉树，它的度如下图所示

当它增加一个结点时候

继续增加一个度为1的结点的时候

由此可见，增加度为1的结点不会影响度为2和度为0的结点个数

当增加一个度为2的结点时

我们发现度为2和度为0的结点个数分别增加1，而度为1的结点个数减少1

由此我们可以观察出，二叉树的度为0的结点个数永远比度为1的结点个数多1

三、二叉树的存储结构

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

1. 顺序存储

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

其中需要注意的是：表示二叉树的值在数组位置中父子下标关系：

parent=（child-1）/2

leftchild=parent*2+1

rightchild=parent*2+2

2.链式存储

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

本期内容就到这里了

如果对你有帮助的话，不要忘记点赞加收藏哦！！！