小赵的学习笔记
0%

二叉树与堆的概念以及实现

发表于 更新于 分类于
本文字数： 7.4k 阅读时长 ≈ 7 分钟

树的概念

  1. 根没有父节点
  2. 子树互不相交
  3. 节点数 = 边数 + 1
  4. 节点的度 = 子树的个数
  5. 树的度：最大节点个数
  6. 树的高度：最大层次

树的表示：双亲表示法，孩子表示法，孩子兄弟表示法

  • 满二叉树：除过叶子，其他节点度都为二，并且每层都是满的
  • 完全二叉树：除过最后一层，剩余结构是一个满二叉树，并且最后一层的节点从左向右中间无间隔

满二叉树一定是完全二叉树

完全二叉树不一定是满二叉树

二叉树

二叉树的节点总数

n0 + n1 + n2 = 二叉树的节点总数

n1 + 2 * n2 = 二叉树边的总数

节点总数 - 1 = 边的个数

n0 + n1 + n2 - 1 = n1 + 2 * n2

n0 = n2 + 1

满二叉树高度：
log⁡2(N+1) \\log_2(N+1) log2​(N+1)

∵2h−1\=N∴h\=log2(N+1) \\because2\^h - 1 =N \\quad \\therefore h = log_2(N+1) ∵2h−1\=N∴h\=log2​(N+1)

_满二叉树的节点一定为奇数_

二叉树的存储形式

  1. 顺序结构：适合存放完全二叉树，没有空间浪费

规则：从第一层开始存放，直到最后一层，每层从左向右依次存放，如果中间有空节点，保留空节点的位置

完全二叉树

父子节点的位置：

parent： left_child = 2 x parent + 1

right_child = 2 x parent +2

child : parent = (child - 1) / 2

  1. 链式结构：_适合存放一般二叉树_

二叉链：数据，指向左右孩子的指针

三叉链：数据，指向左右孩子的指针 + 指向父亲的指针

完全二叉树：总数 2n

度为1的节点出现在倒数第二层

度为一的节点个数：

节点个数为偶数：n1 = 1

节点个数为奇数：n1 = 0

堆

大小堆：

大堆：每个父节点都比子节点大

小堆：每个父节点都比子节点小

堆的向下调整：

隐含的前提：当前需要调整的位置以下的子结构已经是一个堆。

1. 小堆

从当前需要调整的位置开始，（parent）

a. 从左右孩子中选一个最小的（child）

b. 如果最小的child仍然小于parent：

交换child和parent

更新：parent = child，child = 2 * parent + 1

如果child没有越界，跳到a，继续执行

如果最小的child仍然大于parent：结束调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void shiftDown(HPDataType* a, int size, int parent)
{
	int child = 2 * parent + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] < a[child])
			child++;
		if (a[child] < a[parent])
		{
			Swap(a, child, parent);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}

2. 大堆

从当前需要调整的位置开始，（parent）

a. 从左右孩子中选一个最大的（child）

b. 如果最大的child仍然大于parent：

交换child和parent

更新：parent = child，child = 2 * parent + 1

如果child没有越界，跳到a，继续执行

如果最大的child仍然小于parent：结束调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void shiftDown(HPDataType* a, int size, int parent)
{
	int child = 2 * parent + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] > a[child])
			child++;
		if (a[child] > a[parent])
		{
			Swap(a, child, parent);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

堆的向上调整

从当前位置开始（child），与父节点进行比较，如果是大堆，则若孩子大于父亲，交换二者，如果是小堆，则若孩子小于父亲，交换二者，直到不能交换为止。

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
void shiftUp(HPDataType* a, int child)
{
	//小堆
	/*int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(a, child, parent);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}*/
	//大堆
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(a, child, parent);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

堆的实现

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

堆的实现使用了线性表来存储数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Swap(HPDataType* a, int left, int right)
{
	int tmp = a[left];
	a[left] = a[right];
	a[right] = tmp;
}

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int size)
{
	hp->_a = (HPDataType*)malloc(sizeof(HPDataType)* size);
	memcpy(hp->_a, a, sizeof(HPDataType)* size);
	hp->_size = size;
	hp->_capacity = size;

	for (int parent = (size - 2) / 2; parent >= 0; parent--)
	{
		shiftDown(hp->_a, size, parent);
	}
}

堆得插入与删除，堆得插入则直接在线性表末尾插入，然后进行向上调整，堆得删除则需先交换堆顶与最后一个叶子结点，接着线性表进行尾删，然后进行向下调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	if (hp->_size >= hp->_capacity)
	{
		hp->_capacity *= 2;
		hp->_a = (HPDataType*)realloc(hp->_a, sizeof(HPDataType)* hp->_capacity);
	}
	hp->_a[hp->_size++] = x;
	shiftUp(hp->_a, hp->_size - 1);

}
// 堆的删除
void HeapPop(Heap* hp)
{
	if (hp->_size > 0)
	{
		Swap(hp->_a, 0, hp->_size - 1);
		hp->_size--;
		shiftDown(hp->_a, hp->_size, 0);
	}
}

二叉树的实现

二叉树的遍历

  1. 前序（先序）遍历，先访问父节点，在访问左孩子，最后访问右孩子。
1
2
3
4
5
6
7
8
9
void BinaryTreePrevOrder(BTNode* root)
{
	if (root)
	{
		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
16
17
18
19
20
21
void BinaryTreePrevOrderNoR(BTNode* root)
{
	Stack st;
	StackInit(&st);
	BTNode* cur = root;
	BTNode* top = NULL;
	while (cur || !StackEmpty(&st))
	{
		while (cur)
		{
			printf("%c ", cur->_data);
			StackPush(&st, cur);
			cur = cur->_left;
		}
		top = StackTop(&st);
		StackPop(&st);
		cur = top->_right;

	}
	printf("\n");
}

非递归方式，使用到了栈

  1. 中序遍历，先访问左孩子，在访问父节点，最后访问右孩子。
1
2
3
4
5
6
7
8
9
void BinaryTreeInOrder(BTNode* root)
{
	if (root)
	{
		BinaryTreeInOrder(root->_left);
		printf("%c ", root->_data);
		BinaryTreeInOrder(root->_right);
	}
}

递归方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void BinaryTreeInOrderNoR(BTNode* root)
{
	Stack st;
	StackInit(&st);
	BTNode* cur = root;
	BTNode* top = NULL;
	while (cur || !StackEmpty(&st))
	{
		while (cur)
		{
			StackPush(&st, cur);
			cur = cur->_left;
		}
		top = StackTop(&st);
		StackPop(&st);
		printf("%c ", top->_data);
		cur = top->_right;
	}
	printf("\n");
}

非递归，使用到了栈

  1. 后序遍历，先访问左孩子，后访问右孩子，最后访问父节点。
1
2
3
4
5
6
7
8
9
10
void BinaryTreePostOrder(BTNode* root)
{
	if (root)
	{
		BinaryTreePostOrder(root->_left);
		BinaryTreePostOrder(root->_right);
		printf("%c ", root->_data);
	}
}

递归方式

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 BinaryTreePostOrderNoR(BTNode* root)
{
	Stack st;
	StackInit(&st);
	BTNode* cur = root;
	BTNode* top = NULL;
	BTNode* prev = NULL;
	while (cur || !StackEmpty(&st))
	{
		while (cur)
		{
			StackPush(&st, cur);
			cur = cur->_left;
		}
		top = StackTop(&st);
		if (!top->_right || top->_right == prev)
		{
			printf("%c ", top->_data);
			StackPop(&st);
			prev = top;
		}
		else
			cur = top->_right;
	}
	printf("\n");
}

非递归方式，使用到了栈

  1. 层序遍历，从第一层开始，每层向后遍历。

使用队列实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->_data);
		if (front->_left)
			QueuePush(&q, front->_left);
		if (front->_right)
			QueuePush(&q, front->_right);
	}
	printf("\n");
}

二叉树的构建

此处使用先序遍历的方式建树，‘ # ’代表数中的空节点NULL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
BTNode* BinaryTreeCreate(BTDataType* a,int n, int* pi)
{
	if (a[*pi] != '#' && *pi < n)
	{
		BTNode* root = (BTNode*)malloc(sizeof(BTNode));
		root->_data = a[*pi];
		(*pi)++;
		root->_left = BinaryTreeCreate(a, n, pi);
		(*pi)++;
		root->_right = BinaryTreeCreate(a, n, pi);
		return root;
	}
	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
28
29
30
31
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (!root)
		return 0;
	return BinaryTreeSize(root->_left)
		+ BinaryTreeSize(root->_right)
		+ 1;
}

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (!root)
		return 0;
	if (!root->_left && !root->_right)
		return 1;
	return BinaryTreeLeafSize(root->_left)
		+ BinaryTreeLeafSize(root->_right);
}

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (!root)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->_left, k - 1)
		+ BinaryTreeLevelKSize(root->_right, k - 1);
}
-------------本文结束感谢您的阅读-------------