数据结构第六章树与二叉树（二）

在这里插入图片描述

🚀 【考纲要求】二叉树的定义及其主要特征；二叉树的顺序存储和链式存储

二、二叉树的概念

1）什么是二叉树？

对于二叉树来说，它是一个特殊的树形结构，其每个节点都最多有两个孩子（即节点的度最大为2），同时二叉树是一个有序树，不可以随意颠倒位置。

2）二叉树的特此：

根据二叉树的定义就能得到二叉树的特性：

是一个有序树。
每一个节点的最大度为2。
二叉树可以为空，即没有节点的二叉树称为空二叉树。

3）二叉树和度为2的有序树的区别：

度为2的与有序树表示的是该树至少有一个度为2的最大节点，也就表明其实对于度为2的有序树来说至少都有3个节点，从而来满足度为2；而对于二叉树来说，其并不需要满足其度为2，二叉树的度可以为2也可以为1，甚至为0，即变为空二叉树。即二叉树的五种形态如下：空二叉树——如图a；只有一个根节点的二叉树——如图b；只有左子树——如图c；只有右子树——如图d；左右子树都有——如图e。

在这里插入图片描述

2.1几种特殊的二叉树及其定义和主要特性

①：满二叉树

就是除去二叉树最后一层的所有节点都有两个孩子，即节点的度都为2。按着定义说就是对于高度为h的二叉树，若其节点数为 $2^h-1$ 个节点的二叉树称为满二叉树。

就如下图所示，其就为满二叉树；其特性如下：

叶子节点只出现在最后一层
不存在度为1的节点
按层序从1开始编号，节点i的左孩子的序号是2i，右孩子是2i+1；节点i的父节点是向下取整的 $\lfloor i/2 \rfloor$ 。

②：完全二叉树

高度为h的二叉树，有n个节点的二叉树，当且仅当每个节点都和高度为h的满二叉树一一对应，就称为完全二叉树。

如下图所示就是一个完全二叉树，它的每一个节点都和高度为h的满二叉树一一对应；其基本特性如下：

叶子节点可能出现在树的最后一层和倒数第二层。
只可能有一个度为1的节点。
按层序编号，序号为i的节点，若其 $i\leq\lfloor n/2 \rfloor$ ，n为节点的个数，则表示该节点是分支节点，否则为叶子节点。
若n为偶数，则有度为1的节点，若n为奇数，则没有度为1的节点，则其节点都有左孩子节点和右孩子节点。

在这里插入图片描述
③：平衡二叉树

任意一个节点的左子树和右子树的高度差只能最多相差一。为了得到更高的搜索效率。

④：二叉排序树

左子树上的任意一个节点都小于根节点的数值，右子树上的任意一个节点都大于根节点的数值。（用于排序和搜索）

2.2二叉树的性质

非空二叉树的叶子节点的个数 $n_0=n_2+1$ ，因为对于二叉树来说其总节点个数应该为 $n=n_0+n_1+n_2$ ①式，同时其总节点个数还可以表述为 $n=n_1+2n_2+1$ ②式。所以不难得到叶子节点的个数 $n_0=n_2+1$ 。
非空二叉树的第k层最多有 $2^{k-1}$ 个节点
高度为h的二叉树最多有 $2^h-1$ 个节点（等比数列的求和）
具有n个节点的完全二叉树的高度为 $\lceil log_2(n+1) \rceil$ 因为假设高度为h，其完全二叉树最多的节点个数为 $2^h-1$ ，最少为 $2^{h-1}-1$ 但取不到这个最少的；所以可以得到n的取值范围为 $2^{h-1}-1< n \leq2^h-1$ 所以 $log_2(n+1) \leq h$

2.3二叉树的存储结构

①顺序存储
对于顺序存储的二叉树是使用求组来实现的，按着树的节点从上到下从左到右依次来存储，其每个节点的关键字对应数组的下标存储；

#include<stdio.htypedef int Elementtype;
define maxisize 100struct TreNode {Elementtype data;bool isempty;
};TreNode t[maxsize];     //声明了一个树，节点个数为maxsize

不难发现对于完全二叉树来说其存储是很好进行的，要实现该数据结构的基本操作也是比较简单的

查询当前i节点的父节点，将 $i /2$ 然后向下取整数就可以查询到父节点。
查询当前i节点的左孩子节点，直接用 $2 * i$ 查询，同时要判断该节点是否有左孩子节点。
查询当前i节点的右孩子节点，直接用 $2 * i + 1$ 查询，同时要判断该节点是否有右孩子节点。
查询当前节点是分支节点还是叶子结点，使用i和 $n /2$ 向下取整的结果比较，若i小于等于该值则表示为分支节点，若大于该值则表示为叶子结点。
查询现在节点所在的层次直接使用公式 $\lceil log_2(i+1) \rceil$

但是一旦这个二叉树是一个非完全二叉树的话，若还是按着像完全二叉树一样的方式存储的话会导致很难实现该数据结构的基本操作，所以在存储非完全二叉树的时候依然要保持节点存储在其对应的完全二叉树对应的节点处，这样才能方便查询当前节点的左字树节点和右字树节点。
在这里插入图片描述

②链式存储

使用指针链表的方式来实现，其一个节点的结构如下，右左指针指向左孩子节点，由右指针指向右孩子节点。
在这里插入图片描述
代码定义

#include<stdio.h>typedef int Elementtype;typedef struct TreNode {Elementtype data;struct TreNode *lchild *rchild;
}TreNode,*BiTree;//声明一个空树
BiTree tree = NULL;
//声明根节点
tree = (TreNode*)malloc(sizeof(TreNode));