二叉树详讲（一）---完全二叉树、满二叉树、堆

1.树的概念及其结构

1.1树的概念

树是一种非线性数据结构，是一种种抽象数据类型，旨在模拟具有树状结构的节点之间的层次关系。一颗树由诺干个点和诺干条边组成。每棵树只有一个根节点，根节点向下延申又有子节点和叶子节点，叶子节点是树中度数为0的节点。

 这样一种由根节点向下扩展延申至叶子节点的结构看上去像是一颗倒着的树

其实我觉得从某种角度来说，其结构更像是树的根

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

 值得注意的是，在一棵树中，子树之间不能有交集。

1.2 树的相关概念 

1.3树的表示

由于树的结构是非线性的，相比于线性表来说表示就比较复杂，除了要存储值域以外，还要存下所有子节点甚至父节点的关系。

1.3.1双亲表示法

双亲表示法是指每个节点都有一个指向其父节点的指针，根节点的指针为NULL.

typedef int DataType;
struct Node
{struct Node* parent; // 指向父节点DataType _data; // 结点中的数据域
};

1.3.2孩子兄弟表示法

孩子兄弟表示法是指每个节点都存有指向第一个左孩子的指针和其兄弟的指针

typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};

1.3.3孩子表示法

每个节点都有存放其所有孩子的指针

typedef int DataType;
struct Node
{struct Node* Child1[N]; // 指针数组，存放所有孩子节点的指针DataType _data; // 结点中的数据域
};

 1.4树在实际中的运用（表示文件系统的目录树结构）

我们可以看到，我们的根目录就是树的根节点，其下面的各个文件夹都是它的子树

2.二叉树

2.1二叉树的概念

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

 2.2二叉树的递归定义

二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

上图是一颗二叉树，有根节点，和其左右子树组成 

其实任何一棵二叉树的组成都由这样的根节点、左右子树组成，左右子树可能为空。

任何一棵二叉树都由一下几种情况复合而成

2.3特殊的二叉树

2.3.1满二叉树

满二叉树除了最后一层的节点度数为0，其余节点的度数都为2，外观上看像一个三角形

给出一棵满二叉树： 

求满二叉树的节点数目

由于其特殊性质，我们很容易得出满二叉树的节点总数为2^k-1（假设k是满二叉树的高度）

求满二叉树的深度

假设有N个节点，其深度就为log2(N+1)

国外的满二叉树定义

 值得注意的是，美国及其国际上关于满二叉树的定义与国内是不一样的。

美国NIST定义满二叉树是满二叉树的节点度数要么为0，要么为2.

国际上认为上图也是满二叉树，但是不符合国内定义的满二叉树。 

2.3.2完全二叉树

 完全二叉树除了最后一层的节点度数可以不为2，其余节点的度数都为2，且度数不为2的节点数目最多只有一个。满二叉树是一种特殊的完全二叉树。

给出一颗完全二叉树： 

求完全二叉树的节点数目

 假设一颗完全二叉树的深度为k,那么这棵树的节点数量就是[2^(k-1),2^k-1）

满二叉树与完全二叉树的关系：

完全二叉树包含满二叉树，满二叉树是一种特殊的完全二叉树

2.4二叉树的性质（公式）（重要）

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

二叉树每一层的节点容量是一个公比为2的等比数列，2^0 、2^1 、2^2.....2^(i-1)

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

根据等比求和公式，S=a（1-q^n）/(1-q),将q=2,a=1，n=i 带入可得S(i)=2^i-1

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为n2 ,则有 n0＝n2 ＋1

假设有一棵二叉树n个顶点，那么可得一定有n-1条边。

n0表示节点度数为0的数目，n1表示度数为1的节点数目，n2表示度数为2的节点的数目

每一个度数为2的节点的出边都有两条，度数为1的节点出边有一条，省略度数为0的节点。所以总共的边数就是度数为2的节点与度数为1的节点的出边的总和，即为2*n2+n1

于是我们可根据边数关系列出等式  n-1=2*n2+n1...(1)

又根据n=n1+n2+n0...(2),联立等式（1）（2）消掉n，可得n2=n0-1。即n0=n2+1得证。

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= .log(2)(n+1)  (ps：log(2)(n+1) 是log以2 为底，n+1为对数)

根据性质2，深度为h的满二叉树的节点数目n=S(h)=2^h-1,可得h=log2(n+1).

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对 于序号为i的结点有：

1. 若i>0，i位置节点的双亲（父亲节点）序号：(i-1)/2,i=0，i为根节点编号，无双亲节点

2. 若2i+1<n,存在左孩子序号：2i+1；若2i+1>=n（数组下标[0,n-1]）,无左孩子

3. 若2i+2<n,存在右孩子序号：2i+2；若2i+1>=n,无右孩子

图上的节点数n=7.

节点编号6的父节点编号为（6-1）/2=2

节点编号3的父节点编号为（3-1）/2=1

节点编号2的左孩子节点编号为2*2+1=5(5<n)

节点编号3没有左孩子，因为2*3+1=7，7=n

 2.5题目训练

注：以下题目中n0表示节点度数为0的数目，n1表示度数为1的节点数目，n2表示度数为2的节点的数目。h代表高度（深度），n代表节点总数目

题目1

某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）

A 不存在这样的二叉树

B 200

C 198

D 199

解析 ：

根据上述二叉树的性质，n0=n2+1,所以得到n0等于199+1=200，所以答案选B

题目2

在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）

A n

B n+1

C n-1

D n/2

解析：

首先容易想到n0+n1+n2=2n..... (1)

然后根据性质，n0=n2+1 ......(2)

联立（1）（2）得：n0=（2n-n1+1）/2

因为n1只能为1或者0，且n0是个整数，所以（2n-n1+1）一定得是个偶数才能整除2，所以n1一定为1。即得n0=2n/2=n.所以选A

 题目3

一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）

A 11

B 10

C 8

D 12

解析：

因为完全二叉树的节点数目跟高度的关系为n=[2^(h-1),2^h-1），所以易得

h>=log2(n+1)<==>  h<=10

h<log2(n+1) <==> h>9

由此可得h=10,所以答案选B

 2.6 二叉树的存储结构

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

2.6.1顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树或者满二叉树，因为容易有空间的浪费。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

 可以看到，顺序存储非完全二叉树会造成空间的浪费。

2.6.2链式存储

二叉树树的链式存储结构指的是用链表来表示一棵二叉树，用链来表示节点之间的关系。

链表中每个结点通常由三个域组成，一个是存放数据的值域，另外两个则是分别存放左右孩子地址的指针域。

代码： 

typedef int DataType;
struct Node
{struct Node* _leftChild; // 指向左孩子结点struct Node* _rightChild; // 指向右孩子结点DataType _data; // 结点中的数据域
};

 3.堆

3.1堆的概念

如果有一个关键码的集合K = { k0，k1 ，k2 ，…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：ki<=k(2i+1)  且ki >=k(2i+2) ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆

3.2堆的性质

1.堆中某个节点的值一定是不大于或者不小于其孩子节点的值（不大于其孩子节点是小根堆，不小于则是大根堆）

2.堆总是一颗完全二叉树

3.3判断是否为堆

给出以下关键字序列，判断是否为堆

1. 100,60,70,50,32,65 

100的下标为0，是根节点，因为100>60&&100>70,可以判断，如果该关键字序列是堆的话，也一定是大根堆。继续往后看，关键字60和70的左右孩子都不大于其父亲的值，所以该序列是堆，且为大根堆。

2. 60,70,65,50,32,100

 由前3个序列可以判断，如果该关键字序列是堆的话，也一定是小根堆。继续往后看，关键字70的左右孩子的值50，32都小于它，不符合小根堆性质。所以，这个序列不是堆。

 3.4堆的实现（c语言）

给出结构体定义：

typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;//顺序表int _size;//当前堆的节点数量int _capacity;//当前顺序表的容量
}Heap;

3.4.1向下调整法

我们用顺序表存储一颗完全二叉树，并且将这个完全二叉树维护成一个小根堆（大根堆同理），每当要插入节点，我们首先将其插在顺序表尾部，再从后往前，从子节点到父节点依次调整，如果子节点的值大于父节点的值，那么就进行交换，始终维护父节点不大于子节点的这一性质。

部分代码：

//向上调整
static void AdjustUp(HPDataType* a, int pos) {//pos为插入数据的下标assert(a);int child = pos;//从pos开始向上调整int parent = (pos - 1) / 2;//找到其父节点while (child > 0) {//递归向上找父节点，并判断是否要交换if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);child = parent;//更新其父节点与子节点parent = (child - 1) / 2;}else {//一遇到不需要交换时，就立即停下来break;}}
}

 3.4.2向下调整法

当需要删除堆顶元素时，我们先交换堆顶元素和顺序表的最后一个元素，再把最后一个元素的值删除，这样变相的删除了堆顶元素。但是由于不知道此时堆顶元素是否符合小根堆的性质，则需要向下调整。从堆顶元素开始，判断是否不大于其孩子元素，如果否，为了保持小根堆的性质，需要与值最小的孩子交换，从上往下，从父节点到孩子节点，观察是否还需要交换，不需要则退出，或者是孩子节点>=size(没有孩子了)时退出。

代码：

//向下调整
static void AdjustDown(HPDataType* a, int Size) {//Size为当前顺序表的大小assert(a);int parent = 0;int child = parent * 2 + 1;while (child < Size) {//调整方式与向上调整一致if (child+1<Size&&a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}

 3.4.3建立堆的时间复杂度

O(n)（n为节点的数量）

3.4.4堆的代码实现

3.4.4.1Heap.h头文件

定义结构体类型，声明各种函数

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;
//堆的初始化
void InitHeap(Heap* hp);
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

 3.4.4.2Heap.c源文件

具体实现各种函数功能，包括向上调整与向下调整函数

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"void Swap(HPDataType* a, HPDataType* b) {HPDataType t = *a;*a = *b;*b = t;
}//向上调整
static void AdjustUp(HPDataType* a, int pos) {//pos为插入数据的下标assert(a);int child = pos;//从pos开始向上调整int parent = (pos - 1) / 2;//找到其父节点while (child > 0) {//递归向上找父节点，并判断是否要交换if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);child = parent;//更新其父节点与子节点parent = (child - 1) / 2;}else {//一遇到不需要交换时，就立即停下来break;}}
}
//向下调整
static void AdjustDown(HPDataType* a, int Size) {//Size为当前顺序表的大小assert(a);int parent = 0;int child = parent * 2 + 1;while (child < Size) {//调整方式与向上调整一致if (child+1<Size&&a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}//堆的初始化
void InitHeap(Heap* hp) {assert(hp);hp->_capacity = hp->_size = 0;hp->_a = NULL;
}
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n) {assert(hp && a);for (int i = 0; i < n; i++) {HeapPush(hp, a[i]);}//hp->_a = a;//hp->_capacity = hp->_size = n;
}
// 堆的销毁
void HeapDestory(Heap* hp) {assert(hp);free(hp->_a);hp->_a = NULL;hp->_capacity = hp->_size = 0;
}// 堆的插入
void HeapPush(Heap*hp, HPDataType x) {assert(hp);if (hp->_capacity == hp->_size) {//printf("hp->_capacity==%d", hp->_capacity);int newcap = hp->_capacity ==0?4:hp->_capacity*2;//printf("hp->_capacity==%d", newcap);HPDataType* temp = realloc(hp->_a,sizeof(HPDataType)* newcap);if (temp == NULL) {perror("realloc:fail");}hp->_a = temp;hp->_capacity = newcap;}hp->_a[hp->_size] = x;hp->_size++;AdjustUp(hp->_a, hp->_size - 1);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp) {assert(hp);return hp->_a[0];
}// 堆的删除
void HeapPop(Heap* hp) {assert(hp);Swap(&hp->_a[0], &(hp->_a[hp->_size - 1]));hp->_size--;AdjustDown(hp->_a, hp->_size);
}
//获取数据个数
int HeapSize(Heap* hp){return hp->_size;
}// 堆的判空
int HeapEmpty(Heap* hp) {return hp->_size == 0;
}

3.4.4.3test.c源文件

测试文件，测试各种函数功能是否正常

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
Heap hp;int main() {InitHeap(&hp);int arr[10] = { 2,1,0,3,4,7,5,1,2,10 };HeapCreate(&hp, arr, 10);//printf("%d", HeapTop(&hp));/*for (int i = 0; i < 10; i++) {HeapPush(&hp, arr[i]);}*/while (!HeapEmpty(&hp)) {printf("%d ", HeapTop(&hp));HeapPop(&hp);}HeapDestory(&hp);return 0;
}

运行结果