二叉树【树的基本概念】

全文目录

• 树
• • 树的概念
  • 树的相关概念
  • 树的表示
  • 树的实际应用
• 二叉树
• • 二叉树的概念
  • 二叉树的特殊类型
  • 二叉树的性质
  • 二叉树的存储结构
  • • 顺序存储
    • 链式存储
• 堆
• • 堆的概念
  • 向下调整算法
  • 向上调整算法
  • 堆的插入
  • 堆的删除
  • 堆的构建
  • • 时间复杂度计算
  • 堆排序
  • TOP-K问题

树

树的概念

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

它具有以下的特点：

• 有一个特殊的结点，称为根结点，根节点没有前驱结点
• 除根节点外，其余结点被分成$M(M>0)$个互不相交的集合$T_1、T_2、\dots \dots 、T_m$，其中每一个集合$T_i(1<=i<=m)$又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

注意：

成环的树是图，是另一种数据结构

树的相关概念

• 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
• 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
• 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点
• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
• 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
• 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
  节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
• 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
• 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
• 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
• 森林：由m（m>0）棵互不相交的树的集合称为森林；

树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

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

树的实际应用

文件系统的目录等就是树的一种应用：

二叉树

二叉树的概念

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。

二叉树是递归定义的，其节点有左右子树之分，逻辑上二叉树有五种基本形态：

1. 空二叉树——如图1（a）
2. 只有一个根节点的二叉树——如图1（b）
3. 只有左子树——如图1（c）
4. 只有右子树——如图1（d）
5. 完全二叉树——如图1（e）

二叉树的特殊类型

1. 满二叉树：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树 。
2. 完全二叉树：深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树 。

完全二叉树的节点数量：

高度为h的完全二叉树的节点个数在 $[2^{h-1},2^h-1]$

完全二叉树的特点是叶子节点只可能出现在层序最大的两层上，并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1 。

二叉树的性质

性质1： 二叉树的第 $i$ 层上至多有$2^i-1（i\ge 1）$个节点 。

性质2： 深度为 $h$ 的二叉树中至多含有 $2^h-1$ 个节点 。

性质3： 若在任意一棵二叉树中，有 $n_0$个叶子节点，有 $n_2$ 个度为$2$的节点，则必有 $n_0=n_2+1$ 。

性质4： 具有 $n$ 个节点的满二叉树深为 $lo{g}_2^{(n+1)}$ 。

性质5： 若对一棵有 $n$ 个节点的完全二叉树进行顺序编号 $（1\le i\le n）$ ，那么，对于编号为$i（i\ge 1）$的节点：

1. 若 $i>0$ ， $i$ 位置节点的双亲序号： $(i-1)/2；i=0，i$ 为根节点编号，无双亲节点
2. 若 $2i+1<n$ ，左孩子序号：$2i+1，2i+1>=n$ 否则无左孩子
3. 若 $2i+2<n$，右孩子序号： $2i+2，2i+2>=n$ 否则无右孩子

二叉树的存储结构

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

顺序存储

顺序结构存储就是利用性质五使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。后面会用到的堆就是使用这种形式存储的。

链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。

二叉链： 链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该节点左孩子和右孩子所在的链节点的存储地址

// 二叉链
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
	struct BinTreeNode* _pLeft; // 指向当前节点左孩子
	struct BinTreeNode* _pRight; // 指向当前节点右孩子
	BTDataType _data; // 当前节点值域
}
1
2
3
4
5
6
7
8
9

三叉链： 在二叉链的基础上增加父节点的存储地址

// 三叉链
struct BinaryTreeNode
{
	struct BinTreeNode* _pParent; // 指向当前节点的双亲
	struct BinTreeNode* _pLeft; // 指向当前节点左孩子
	struct BinTreeNode* _pRight; // 指向当前节点右孩子
	BTDataType _data; // 当前节点值域
}；
1
2
3
4
5
6
7
8

堆

堆的概念

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值；
• 堆总是一棵完全二叉树。

通常我们使用顺序结构的数组来存储。

将根结点最大的堆叫做最大堆或大根堆：

根结点最小的堆叫做最小堆或小根堆：

向下调整算法

向下调整算法是在堆的前提下维护堆的特性

算法思想：

选取子节点中较大或者较小的一个（大跟堆选较大，小跟堆选较小），如果大于或者小于当前节点即交换父子节点的值（大跟堆取大于，小跟堆取小于），依次迭代，直到子节点超过了堆的大小。

// 向下调整算法
void AdjustDown(HeapDataType* data, size_t parent, size_t size)
{
	assert(data);

	size_t child = parent * 2 + 1;
	
	while (child < size)
	{
		//if (child + 1 < size && data[child + 1] < data[child]) // 小堆
		if (child + 1 < size && data[child + 1] > data[child]) // 大堆
			child++;

		//if (data[child] < data[parent])		// 小堆
		if (data[child] > data[parent])		// 大堆
		{
			Swap(&data[child], &data[parent]); 
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

向上调整算法

在堆的基础上维护堆，向堆尾插入节点时，需要向上维护堆。

算法思想：

如果当前节点是否大于或小于父节点（大跟堆取大于，小跟堆取小于），交换父子节点，依次迭代，直到子节点成为根节点

// 向上调整算法
void AdjustUp(HeapDataType* data, size_t child)
{
	assert(data);

	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (data[child] > data[parent])	// 大堆
		//if (data[child] < data[parent])		// 小堆
		{
			Swap(&data[child], &data[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

堆的插入

在堆的基础上进行插入，插入后使用向上调整算法维护堆。

// 堆的插入
void HeapPush(Heap* heap, HeapDataType x)
{
	assert(heap);
	
	// 扩容检查
	CheckCapacity(heap);
	
	heap->data[heap->size] = x;
	AdjustUp(heap->data, heap->size);
	heap->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12

堆的删除

将堆顶堆底元素进行交换，删除最后一个元素，并对堆顶进行向下调整，维护堆的性质：

// 堆的删除
void HeapPop(Heap* heap)
{
	assert(heap);
	assert(heap->size);

	heap->size--;
	Swap(&heap->data[heap->size], &heap->data[0]);
	AdjustDown(heap->data, 0, heap->size);
}
1
2
3
4
5
6
7
8
9
10

堆的构建

当然可以从零开始构建一个堆，这样就是正常的HeapPush 和 HeapPop，没什么好说的。要说的是在原数组的基础上进行构建。

当给出一个数组，，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

// 构建堆
for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	AdjustDown(data, i, size - 1);
1
2
3

时间复杂度计算

建堆的时间复杂度需要计算每个细节，看似是 $O(nlo{g}^n)$ 但其实是 $O(N)$

需要操作多少个节点，每个节点需要进行多少次操作：

堆排序

堆排序就是堆的基础上实现的，分为一下几个步骤：

1. 建堆
2. 排序

堆排序使用的是 HeapPop 操作，选取一个最大或者最小的数与尾部，操作 $n$ 次。

 // 堆排序
void HeapSort(HeapDataType* data, int size)
{
	assert(data);
	
	// 建堆
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
		AdjustDown(data, i, size - 1);
	
	// 排序
	while (size > 0)
	{
		Swap(&data[0], &data[size - 1]);
		size--;
		AdjustDown(data, 0, size);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

需要注意的是：升序建大堆，降序建小堆

TOP-K问题

TOP-K问题： 即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

一般想到的是排序，排序的时间复杂度是：$O(nlo{g}^n)$

如果数据量是100亿个整数：

1GB = 1024MB
1024MB = 1024 * 1024KB
1024 * 1024KB = 1024 * 1024 * 1024byte ≈ 10亿
100亿个整数 = 400亿字节 = 40GB内存
1
2
3
4

很显然不可能有这么大的内存，那么最佳的方式就是用堆来解决，堆的优势就展现出来了，我们只需要在内存中存放前$K$ 个数即可：

1. 用数据集合中前 $K$ 个元素来建堆
   • 前 $K$ 个最大的元素，则建小堆
   • 前 $K$ 个最小的元素，则建大堆
2. 用剩余的 $N-K$ 个元素依次与堆顶元素来比较，不满足则替换堆顶元素

时间复杂度： $O(K+(N-k)lo{g}^K)$

// TopK问题
void TopK(HeapDataType* data, int n, int k)
{
	assert(data);

	HeapDataType* a = (HeapDataType*)malloc(sizeof(HeapDataType) * k);
	assert(a);

	// 建堆
	for (int i = 0; i < k; i++) a[i] = data[i];
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
		AdjustDown(a, i, k);

	// TopK
	for (int i = k; i < n; i++)
	{
		if (data[i] >= a[0])
		{
			a[0] = data[i];
			AdjustDown(a, 0, k);
		}
	}

	for (int i = 0; i < k; i++) printf("%d ", a[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25