目录

一、树的概念及结构

1.树的概念

2.树的相关概念

3.树的表示

二、二叉树的概念及结构

1.概念

2.特殊的二叉树

3.二叉树的性质

三、二叉树的存储结构

一、树的概念及结构

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.链式存储

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

本期内容就到这里了

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