【数据结构】二叉树_一个具有m个结点的二叉树,其二叉链表结点(左、右孩子指针分别用left和right表示)

一. 树的概念及结构

1. 概念

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

现实生活中的树

数据结构中的树

2. 树的特征

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

PS：

• 子树是不相交的
  

• 除了根节点外，每个节点有且仅有一个父节点

3. 树的表示法

实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子兄弟表示法等等。简单介绍一下孩子兄弟表示法（左孩子右兄弟） 和双亲表示法。

孩子兄弟表示法（常用）

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

即节点中除了存该节点的数据外，还存了这个节点的第一个孩子的指针，和它下一个（右边）兄弟的指针。如果没有孩子或者下一个兄弟的话就指向空。

双亲表示法
把节点按照顺序存储在数组中，节点内除了自身的数据外还存储父亲的下标。

---

二. 二叉树概念及性质

1. 概念

每个节点的度<=2的树称为二叉树。

• 每个结点最多有两棵子树，即二叉树不存在度大于2的结点
• 二叉树的子树有左右之分，其子树的次序不能颠倒

2. 特殊的二叉树

2.1 完全二叉树

从根节点开始遍历，中间不出现间断的二叉树称为完全二叉树。

2.1 满二叉树

每一个层的结点数都达到最大值的二叉树就是满二叉树。

PS：满二叉树是一种特殊的完全二叉树

• 若规定根节点的层数为1，则一棵满二叉树的第i层上有2^(i-1) 个结点
• 若规定根节点的层数为1，则深度为h的满二叉树的结点总数是2^h- 1
• 若规定根节点的层数为1，具有n个结点的满二叉树的深度h=Log2(n+1). (Log2(n+1)是log以2为底，n+1为对数)

3. 性质

• 若规定根节点的层数为1，二叉树的第i层上最多有2^(i-1) 个结点
• 若规定根节点的层数为1，则高度为h的二叉树的最大结点数（满二叉树的情况）是2^h- 1
• 若规定根节点的层数为0，具有n个结点的满二叉树的深度，h=Log(n+1). (ps：Log(n+1)是log以2为底，n+1为的对数)
• 对一个完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则父子节点之间有如下关系
  

---

三. 二叉树的顺序存储结构 — 堆

1. 概念

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。堆在逻辑结构上是一棵完全二叉树（物理结构上是数组），其父节点总是大于等于或者小于等于它的孩子，物理上是一个数组。

PS：这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2. 堆的结构

分为大堆和小堆

---

四. 堆的创建

1. 堆的向下调整算法和向上调整算法

1.1 向下调整算法

因为根的原因，整棵树不是堆，但根的两颗子树是堆，那么我们通过向下调整算法可以把该树变成一个堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

向下调整算法时间复杂度分析
最坏的情况就是从根节点（树的最高层）开始调，直到调到树的最低层结束，调整次数就是树的高度也就是它的时间复杂度O（logN）

代码实现

void swap(int* num1, int* num2)
{
	int tmp = *num1;
	*num1 = *num2;
	*num2 = tmp;
}

// 向下调整算法(拿孩子和父母比)
// 下面实现是调大堆，调小堆的话判断条件改一下就可
void AdjustDown(int* a, int n, int parent)
{
	// 最外面先计算左孩子
	int child = parent * 2 + 1;
	while (child < n)// 既然是拿孩子和父母比，那就得有孩子
	{
		// 如果有右孩子的话比较右孩子和左孩子的大小
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
		// 比较孩子和父母的大小
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[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
27
28
29
30
31
32
33
34

1.2 向上调整算法

如果一个数组已经是堆了，我们在给数组最后再加一个元素，可能就不是堆了，此时通过向上调整算法可以再次调整为堆。


向上调整算法时间复杂度
和向下调整算法一样最多调整次数为树的高度，时间复杂度也为O (logN)

代码实现

void swap(int* num1, int* num2)
{
	int tmp = *num1;
	*num1 = *num2;
	*num2 = tmp;
}

// 向上调整算法（拿孩子和父母比）
// 下面实现是调大堆，调小堆的话判断条件改一下就可
static void AdjustUp(int* a, int child)
{
	// 最坏的情况孩子到根节点了，没有父母与之比较
	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (a[parent] < a[child])
		{
			swap(&a[parent], &a[child]);
			child = parent;
		}
		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

2. 建堆

如果数组的结构完全混乱，就不能只通过一次向上（下）调整算法来建成堆了，此时要通过多次调整才可建成堆。

2.1 向下调整算法建堆

从倒数第一个非叶子节点开始进行向下调整算法，然后第倒数二个非叶子节点调，直到头结点，最后就可以建成堆了。

代码实现

for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
	AdjustDown(a, n, i);
}
1
2
3
4

2.2 向上调整算法建堆

向上调整算法也同样可以建堆，从第一个节点（根节点）开始向上调整，直到最后一个节点。其思路与向下调整算法建堆相反。


代码实现

for (int i = 0; i < n; ++i)
	{
		AdjustUp(a, i);
	}
1
2
3
4

2.3 向上和向下调整法时间复杂度分析

分析时间复杂度，考虑最坏的情况，就是满二叉树和每个节点都要调到最上面或者最下面。

下面以分析向下调整算法，向上调整算法结果也一样时间复杂度都是O(N)

3. 堆排序

3.1 堆排序过程

每个大堆的根节点是最大的数，小堆根节点是最小的数，我们可以通过建堆和调堆来达到排序的效果。

如果要排顺序，那应该建大堆还是小堆？

排顺序，建大堆就可以避免上图多次建堆造成的效率低问题

按照上图这个思路，其实我们建小堆也可以，不过最后要把数组逆置一下，才能得到顺序结果。

3.2 堆排序时间复杂度

给你一个乱序数组，首先我们要建堆，时间复杂度为O(N)，最坏的情况，每一个节点都要调整那时间复杂的就是O（ N*log(N) ）。

那么加起来就是 N + N*log(N)，推导大 O 阶渐进表示法时间复杂度为：O（ N * log(N) ）

3.3 堆排序代码实现

void HeapSort(int* a, int n)
{
	// 1.建堆
	// 向下调整法建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	// 2.排序
	// 排顺序还是逆序取决于向下调整法建大堆还是小堆
	int end = n - 1;
	while (end > 0)
	{
		// 把根节点移到最后一个位置（它的子树依然是堆）
		swap(&a[0], &a[end]);
		// 最后一个位置不计，用向下调整算法调整根节点数据
		AdjustDown(a, end, 0);
		--end;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4. 堆的实现

创建一个堆，可以实现给堆插入一个数据，删除堆顶数据等功能

堆的结构
堆物理结构上是一个数组，还可以记录数组当前元素个数和堆的容量。

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;
1
2
3
4
5
6
7
8

下面说明较复杂的堆的创建，堆的插入和删除接口

堆的创建

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	// 为数组开辟对应数组大小的空间
	hp->_a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	// 拷贝数据
	// 也可以memcpy(hp, a, sizeof(HPDataType)*n)
	for (int i = 0; i < n; ++i)
	{
		hp->_a[i] = a[i];
	}
	hp->_size = hp->_capacity = n;
	// 建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(hp->_a, n, i);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

堆的插入
在数组末尾插入一个数，然后从这个位置进行向上调整算法（时间复杂度O（logN）），没必要重新建堆（时间复杂度O（N））

void HeapPush(Heap* hp, HPDataType x)
{
	// 空间满了的话就要扩容
	if (hp->_size == hp->_capacity)
	{
		int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType)*newcapacity);
		if (!tmp)
		{
			printf("Realloc fail!");
			exit(-1);
		}
		hp->_a = tmp;
		hp->_capacity = newcapacity;
	}
	hp->_a[hp->_size] = x;
	AdjustUp(hp->_a, hp->_size++);// 不要忘了插入数据后size要++
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

堆的删除
堆的删除就是删除堆顶数据，没必要重新建堆。交换堆顶和数组最后一个位置数据，size减一，然后从堆顶开始向下调整。

void HeapPop(Heap* hp)
{
	swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	--hp->_size;
	AdjustDown(hp->_a, hp->_size, 0);
}
1
2
3
4
5
6

---

五. 二叉树的链式存储结构

1. 概念

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

2. 结构

链式结构分为二叉链和三叉链

二叉链
处理自身数据外，还存有指向左右孩子的指针

struct BinaryTreeNode
{
	struct BinTreeNode* left; // 指向当前节点左孩子
	struct BinTreeNode* right; // 指向当前节点右孩子
	BTDataType val; // 当前节点值域
};
1
2
3
4
5
6

三叉链

struct BinaryTreeNode
{
	struct BinTreeNode* parent; // 指向当前节点的双亲
	struct BinTreeNode* left; // 指向当前节点左孩子
	struct BinTreeNode* right; // 指向当前节点右孩子
	BTDataType val; // 当前节点值域
};
1
2
3
4
5
6
7

3.二叉树链式结构的实现(二叉链表)

3.1 节点的创建与树的销毁

节点的结构
就是二叉链的节点

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data; //节点的数据
	struct BinaryTreeNode* left;// 指向左孩子
	struct BinaryTreeNode* right;// 指向右孩子
}BTNode;
1
2
3
4
5
6
7

创建二叉树的节点

BTNode* BinaryTreeCreate(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	// 把节点的成员初始化
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;
	// 最后返回节点的地址
	return newnode;
}
1
2
3
4
5
6
7
8
9
10

销毁二叉树

void BinaryTreeDestory(BTNode* root)
{
	// 空树的话没必要销毁了
	if (!root)
	{
		return;
	}
	// 后续遍历，从下往上依次销毁每个节点
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}
1
2
3
4
5
6
7
8
9
10
11
12

3.2 二叉树遍历

先序遍历
根节点 -> 左子树 ->右子树

// 前序：根->左子树->右子树
void BinaryTreePrevOrder(BTNode* root)
{
	// 空树的话直接结束函数
	if (!root)
	{
		return;
	}
	// 打印节点
	printf("%c ", root->data);
	// 递归遍历左子树
	BinaryTreePrevOrder(root->left);
	// 递归遍历右子树
	BinaryTreePrevOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

中序遍历
左子树 -> 根 -> 右子树

void BinaryTreeInOrder(BTNode* root)
{
	// 空树的话直接结束函数
	if (!root)
	{
		return;
	}
	// 递归遍历左子树
	BinaryTreeInOrder(root->left);
	// 打印节点
	printf("%c ", root->data);
	// 递归遍历右子树
	BinaryTreeInOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

后序遍历
左子树->右子树->根

void BinaryTreePostOrder(BTNode* root)
{
	// 空树的话直接结束函数
	if (!root)
	{
		return;
	}
	// 递归遍历左子树
	BinaryTreePostOrder(root->left);
	// 递归遍历右子树
	BinaryTreePostOrder(root->right);
	// 打印节点
	printf("%c ", root->data);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

层序遍历
从上往下，从左往右，依次遍历每个节点。需要借助队列完成

void BinaryTreeLevelOrder(BTNode* root)
{
	// 创建一个队类，用于存放节点的指针
	std::queue<BTNode*> p;
	// 把根节点入队列
	if (root)
	{
		p.push(root);
	}
	while (!p.empty())
	{
		// 先拿到队头节点
		BTNode* front = p.front();
		// 队头节点处队列
		p.pop();
		// 打印节点的值
		printf("%c ", front->data);
		// 出队列后把该节点的左右孩子也放入队列中
		if (front->left)
		{
			p.push(front->left);
		}
		if (front->right)
		{
			p.push(front->right);
		}
	}
}
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
27
28

3.3 二叉树节点个数

思路
从根节点开始，树的节点个数等于根自身的1加上左子树和右子树的节点的个数。

代码实现

int BinaryTreeSize(BTNode* root)
{
	// 空树的话就是0个节点
	// 不空的话，节点个数就是自身节点个数1加上左子树节点个数加上有子树节点个数
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
1
2
3
4
5
6

3.4 叶子节点个数

思路
前序遍历二叉树，统计叶子节点的个数

代码实现

int BinaryTreeLeafSize(BTNode* root)
{
	// 空树的话叶子节点个数就是0
	if (!root)
	{
		return 0;
	}
	// 不空的情况
	// 当前节点是叶子节点就返回1
	if (!root->left && !root->right)
	{
		return 1;
	}
    // 当前不是叶子节点就继续递归左右孩子节点
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.5 第k层的节点个数

思路

代码实现

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	// 空树的话返回0
	if (!root)
	{
		return 0;
	}
	// k为1算第k层的节点
	if (k == 1)
	{
		return 1;
	}
	// k不为1，继续往下一层走
	else
	{
		return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.6 查找节点

思路
先看看当前的根节点是否是要查找的那个，如果不是就到左右子树中去找

代码实现

// 注意最后要返回节点的地址
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	// 空树的话找不到，返回空
	if (!root)
	{
		return NULL;
	}
	// 根节点就是要找的，就返回根节点
	if (root->data == x)
	{
		return root;
	}
	else
	{
		// 左子树中找到了，就返回那个节点
		BTNode* lret = BinaryTreeFind(root->left, x);
		if (lret)
			return lret;
		// 右子树若找到了，也返回那个节点
		BTNode* rret = BinaryTreeFind(root->right, x);
		if (rret)
			return rret;
	}
	// 找不到，返回null
	return NULL;
}
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
27

3.7 判断是否是完全二叉树

思路

代码实现

bool BinaryTreeComplete(BTNode* root)
{
	std::queue<BTNode*> p;
	// 最开始的根节点，不是空的话就入队列（只执行一次）
	if (root)
	{
		p.push(root);
	}
	while (!p.empty())
	{
		// 拿到队头数据
		BTNode* front = p.front();
		// 出队头数据
		p.pop();
		// 拿出来的那个队头节点不空的话，把他的左右孩子节点都入队列
		// 空的话退出循环
		if (!front)
		{
			break;
		}
		p.push(front->left);
		p.push(front->right);
	}
	// 如果队列中还有非空节点，就不是完全二叉树
	while (!p.empty())
	{
		if (p.front())
		{
			return false;
		}
		p.pop();
	}
	return true;
}
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
27
28
29
30
31
32
33
34