常用数据结构

工作中，最常用的数据结构有：数组，链表，栈，队列，哈希表和二叉搜索树。数组我们已经很熟悉了，因此不再赘述。接下来我们分别讨论下链表、栈、队列、哈希表和二叉搜索树。

网站推荐：数据结构与算法可视化Data Structure Visualization (usfca.edu)

链表

链表：是用”链”将结点串联起来的数据结构。

结点：是一个对象(在C语言中就是一个结构体)。该对象中有数据域和指针域，数据域顾名思义存放的就是数据，指针域存放的是结点(可以是另一个结点，也可以是自身)的地址

链表的分类：

单向链表

单向循环链表

双向链表

双向循环链表

循环链表我们用的一般比较少，但是当处理的数据具有环形结构时，就特别适合用循环链表，比如约瑟夫环问题。接下来我们讨论下最常用单向链表和双向链表。

单链表

基本操作

  1. 添加 (在某个结点后面添加) O(1)

    1
    2
    newNode->next = curr->next;
    curr->next = newNode;

  2. 删除 (在某个结点后面删除) O(1)

    1
    2
    3
    Node* removed = curr->next;
    curr->next = curr->next->next;
    free(removed);

  3. 查找

    a. 根据索引查找结点 O(n)

    b. 查找链表中与特定值相等的结点

    1)大小有序 O(n)

    2)大小无序 O(n)

实现

List.h

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
//List.h
// 定义结点类型
typedef struct node {
	char val;
	struct node* next;
} Node;

//存放整条链表的信息
typedef struct {
	Node* head;
	Node* tail;
	int size;
}List;

// API
List* create_list();
void destroy_list(List* list);

void add_before_head(List* list, char val);
void add_behind_tail(List* list, char val);
void add_node(List* list, int idx, char val);

void delete_node(List* list, int val);

Node* find_by_index(List* list, int idx);

List.c

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include "List.h"
#include<stdio.h>
#include<stdlib.h>

// API
//不带dummy node的链表
List* create_list() {
	/*List* list = malloc(sizeof(List));
	if (!list) {
		return NULL;
	}
	list->head = NULL;
	list->tail = NULL;
	list->size = 0;*/
	//创建空链表
	return calloc(1, sizeof(List));
}

void destroy_list(List* list) {
	//释放节点
	Node* curr = list->head;
	while (curr)
	{
		Node* nodeNext = curr->next;
		free(curr);
		curr = nodeNext;
	}
	//释放List结构体
	free(list);
}
//头插法
void add_before_head(List* list, char val) {
	//创建结点
	Node* newNode = malloc(sizeof(Node));
	if (!newNode) {
		printf("malloc failed in add_before_head\n");
		exit(1);
	}
	//初始化节点
	newNode->val = val;
	//插入节点
	newNode->next = list->head;
	//更改List结构体的信息
	list->head = newNode;
	if (list->size == 0)
		list->tail = newNode;

	list->size++;
}
//尾插法
void add_behind_tail(List* list, char val) {
	//创建结点
	Node* newNode = malloc(sizeof(Node));
	if (!newNode) {
		printf("malloc failed in add_behind_tail\n");
		exit(1);
	}
	//初始化节点
	newNode->val = val;
	newNode->next = NULL;//尾插法的新节点的指针是NULL基本是固定的。可以先赋值

	//插入节点
	//空链表的时候
	if (list->tail == NULL) {
		list->tail = newNode;
		list->head = newNode;
	}
	else {
		list->tail->next = newNode;
		list->tail = newNode;
	}
	list->size++;
}
void add_node(List* list, int idx, char val) {
	//参数校验
	if (idx < 0 || idx > list->size) {
		printf("Invalid arguments: idx = %d, size = %d\n", idx, list->size);
		//exit(1);
		return;
	}

	
	//要分插入位置为第一个和最后一个吗
	//好像可以调用函数，改一下list就行了
	if (idx == 0) {
		add_before_head(list, val);
		return;
	}
	if (idx == list->size) {
		add_behind_tail(list, val);
		return;
	}
	
		//查找索引为idx - 1的节点
	//curr是要插入位置的前一个节点，为了保留地址信息
		Node* curr = list->head;
		idx--;
		while (idx--) {
			curr = curr->next;
		}
		//比较好的做法就是将curr和i对应起来
		/*for (int i = 0; i < idx - 1; i++)
			curr = curr->next;*/
		//i = idx - 1

		//创建结点
		Node* newNode = malloc(sizeof(Node));
		if (!newNode) {
			printf("malloc failed in add_node\n");
			exit(1);
		}
		//初始化节点
		newNode->val = val;

		newNode->next = curr->next;
		curr->next = newNode;
		//更新List结构体
		list->size++;
		return;

}
//删除链表中第一个与value想等的节点
void delete_node(List* list, char val) {
	//查找第一个与value想等的节点的前一个节点
	/*Node* node = list->head;
	if (node->val == val)
	{
		list->head = node->next;
		free(node);
	}
	else {
		while (node->next) {
			if (node->next->val == val)break;
			node = node->next;
		}
		if (!node->next)
		{
			printf("invalid arugment: val is not exist!\n");
		}
		else {
			Node* tmp = node->next;
			node->next = node->next->next;
			free(tmp);
		}
	}*/
	//查找第一个与value想等的节点的前一个节点
	Node* pre = NULL;
	Node* curr = list->head;
	while (curr)
	{
		if (curr->val == val) {
			if (pre == NULL) {			//curr是链表第一个结点
				list->head = curr->next;
				if (list->size == 1)  
					list->tail == NULL; 
				free(curr);
			}
			else {			//curr是链表不是第一个借点
				pre->next = curr->next;
				if (curr->next == NULL)
					list->tail = pre;
				free(curr);
			}
			list->size--;
			return;
		}
			pre = curr;
			curr = curr->next;
	}
	//curr == NULL

	printf("invalid argument: val = %c\n", val);
	return;
}

Node* find_by_index(List* list, int idx) {
	//参数校验
	if (idx < 0 || idx >= list->size) {
		printf("Invalid arguments: idx = %d, size = %d\n", idx, list->size);
		//exit(1);
		return NULL;
	}
	Node* curr = list->head;
	for (int i = 0; i < idx; i++)
			curr = curr->next;
			//i == idx
	return curr;

}
//在链表中查找第一个与value想等的节点
Node* search_for_value(List* list, int val) {
	Node* curr = list->head;
	while (curr) {
		if (curr->val == val) return curr;
		curr = curr->next;
	}
	return NULL;
}

main.c

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
35
36
37
38
39
40
41
#define _CRT_SECURE_NO_WARNINGS
#include "List.h"
#include<stdio.h>
#include<stdlib.h>
int main(void) {
	List* list = create_list();//创建空链表
	if (!list) {
		printf("Error: create_list failed!\n");
		exit(1);
	}
	for (int i = 'a'; i < 'a' + 2; i++)
		add_behind_tail(list, i);
	for (int i = 'b'; i > 'b' - 2; i--)
		add_before_head(list, i);

	/*for (int i = '1'; i < '1' + 10; i += 2)
		add_node(list, i - '1', i);*/

	/*delete_node(list, 'a');
	delete_node(list, 'a');
	delete_node(list, 'x');*/

	Node* node = list->head;
	while (node) {
		printf("%c ", node->val);
		node = node->next;
	}
	printf("\n");

	/*Node* nodeByIndex = find_by_index(list, 2);
	printf("%c ", nodeByIndex->val);*/

	Node* node1 = search_for_value(list, 'a');
	/*printf("%c ", node1->val);*/

	Node* node2 = search_for_value(list, 'c');

	printf("size = %d\n", list->size);
	destroy_list(list);
	return 0;
}

双向链表

基本操作我们很容易验证，单向链表的基本操作，双向链表也是支持的，并且时间复杂度也是一样。但是在工程实践上，我们往往更倾向于使用双向链表，而不是单链表，比如C++ 中的 list，Java 中的 LinkedList 底层的数据结构都是双向链表。

原因源自于双向链表的独特魅力——它有一条指向前驱结点的链接，使得双向链表可以高效地完成一些单链表处理起来很麻烦的问题。

  1. 添加 (在某个结点前面添加)

  2. 删除 (删除当前结点)

    1. 查找

      a. 根据索引查找结点 O(n), 平均只需遍历 n/4 各结点。

      b. 查找链表中与特定值相等的结点

      1. 大小有序， 保留上次查找结点的地址
        1. 大小无序 O(n), 与单链表一致

总结：虽然双向链表更占内存空间，但是它某些操作的性能是优于单链表的。这就是典型的空间换时间的思想。

常见面试题

假设结点定义如下，请完成下列题目。

1
2
3
4
typedef struct node {
int val;
struct node* next;
} Node;

求链表中间结点的值。

1
2
3
4
5
int middleElement(Node* list);
输入: 1 --> 2 --> 3
输出: 2
输入: 1 --> 2 --> 3 --> 4
输出: 3

思路1:

遍历链表，求出链表的长度n

找出索引为n / 2的节点

思路2：快慢指针

什么时候快指针到达了末尾？

1
fast == NULL || fast->next == NULL

千万不能写成，如下。这样写不符合短路原则，fast为NULL时候，不能写成fast->next == NULL ，对空指针进行解引用会报错。

1
fast->next == NULL || fast == NULL

判断单链表是否有环?

1
bool hasCircle(Node* list);

思路1：迷雾森林

如何做标记？ 把遍历过的的链表放进集合里面（图那一张就经常这样，遍历过的就放入集合里面）

时间：如果是数组，那就是O(n * n)

如果该集合的查找时间复杂度为O(1)（例如哈希表）,那么整体的时间复杂度就退化为O(n)

所以依赖于集合的查找性能，最好情况为O(n)

空间：O(n)

思路2：快慢指针

无环的情况：快指针肯定先到链表末尾

有环的情况：快指针和慢指针再一次相遇。相遇的点肯定不是末尾

时间复杂度：O(n)

空间复杂度：只有两个指针变量，是O(1)（如果要开n个指针变量，那才是O(n),n是链表的结点个数）

反转单链表

1
2
3
Node* reverse(Node* list);
输入: 1 --> 2 --> 3
输出: 3 --> 2 --> 1

反转链表都是不要创建额外节点的，不需要额外内存空间，直接在原来链表上进行反转

思路1：头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
Node* prev = NULL;
Node* curr = list;
while(curr){
	//保留下一个节点
		Node* currNext = curr->next;
	//反转curr借点
	curr->next = prev;
	//跟新prev，curr
	prev = curr;
	curr = currNext;
}
// curr == NULL的时候循环结束
list = prev;//prev这个时候指向第一个节点

时间复杂度：O(n)

空间复杂度：O(1)

迭代实现
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //迭代
        ListNode* prev = NULL;
        ListNode* curr = head;
        while(curr){
            ListNode* currNext = curr->next;
            curr->next = prev;
            prev = curr;
            curr = currNext;
        }
        head = prev;
        return head; 
    }
};

思路2：递归

类似于数学归纳法：假设我已经实现了反转n - 1个结点（成立），那么如果在已经实现反转n - 1个节点的基础上，反转 n 个节点

边界条件:只有一个借点或者是空链表（类似于数学归纳法的归纳奠基，k = 0成立，k = 1成立。在假设k = n - 1成立，求证明k = n也成立

1
list == NULL || list->next == NULL

递归公式：

1
2
3
4
Node* head = reverse(list->next);//相当于假设k = n - 1成立，接下来只要证明k = n也成立
list->next->next = list;
list->next = NULL;

时间复杂度：O(n)

空间复杂度：O(n)

递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //递归
        //边界条件
        if(head == NULL || head->next == NULL) return head;
        //递归公式
        ListNode* headnew = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return headnew;

    }
};

合并两条有序的单向链表，使得合并后的链表也是有序的 (要求: 不能额外申请堆内存空间)。

1
2
3
4
Node* mergeTwoLists(Node* list1, Node* list2);
输入：1 --> 3 --> 5
2 --> 4 --> 6
输出：1 --> 2 --> 3 --> 4 --> 5 --> 6

虽然不能申请额外的堆内存空间，但是可以申请额外的栈内存空间

栈

栈是一种操作受限的线性结构。操作受限体现在，栈只能在一端添加和删除元素，符合**后进先出(LIFO)**的特性，如下图所示：

和生活中的场景对应起来，如从桶里面拿网球羽毛球，洗碗拿碗放碗。

操作受限往往不是坏事，往往是为了更加的安全，可以提醒程序员这是一个栈，操作是受限的。

单独领出来栈，可以提高代码可读性，别人脑海中就会联想到栈，栈顶，栈底。而不是联想到一个vector连续存放的动态数组

基本操作

  1. 入栈
  2. 出栈
  3. 查看栈顶元素
  4. 判空

实现

(a) 用链表实现 (为了复习二级指针，这里我们使用二级指针来实现)

Stack.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdbool.h>
//Stack.h
//定义结点类型
typedef struct node {
	int val;
	struct node* next;
}Node;
//API
void stack_push(Node** pstack, int val);
int stack_pop(Node** pstack);
int stack_peek(Node* stack);
bool stack_empty(Node* stack);


Stack.c

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
35
36
37
38
39
40
#include "Stack.h"
#include<stdio.h>
#include<stdlib.h>
void stack_push(Node** pstack, int val) {
	//相当头插法
	Node* newNode = malloc(sizeof(Node));
	if (!newNode) {
		printf("Error: failed in malloc\n");
		exit(1);
	}

	newNode->val = val;
	newNode->next = *pstack;
	//改变stack的指向
	*pstack = newNode;

}
int stack_pop(Node** pstack) {
	if (stack_empty(*pstack)) {
		printf("Error: stack is empty\n");
		exit(1);
	}
	//保留要去除节点的地址和返回值，方便free和return val；
	Node* removedNode = *pstack;
		int removedVal = removedNode->val;

	*pstack = removedNode->next;
		free(removedNode);
		return removedVal;
}
int stack_peek(Node* stack) {
	if (stack_empty(stack)) {
		printf("Error: stack is empty\n");
		exit(1);
	}
	return stack->val;
}
bool stack_empty(Node* stack) {
	return stack == NULL;
}

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<stdlib.h>
#include "Stack.h"

int  main() {

	Node* stack = NULL;
	stack_push(&stack, 1);
	stack_push(&stack, 2);
	stack_push(&stack, 3);
	stack_push(&stack, 4);
	//遍历栈
	while (!stack_empty(stack)) {
		int val = stack_peek(stack);
		printf("%d ", val);
		stack_pop(&stack);
	}
	printf("\n");
	printf("%d ", stack_empty(stack));
	return 0; 
}

(b) 用数组实现 (作业)

应用场景

栈的应用场景是多种多样的：

事实上，只要有后进先出LIFO的特性，都可以联想到栈

（这里贴上leetcode对应的题目）

(1) 函数调用栈

(2) 符号匹配问题

括号匹配问题泛化一下就是符号匹配问题。例如a,A进行匹配

然后符号匹配问题一般使用括号去解决这个问题

左括号：将对应的右括号入栈

右括号：右括号直接出栈

遇到的符号不匹配那么就说明给的符号序列是不匹配 的

(3) 表达式求值

(4) 深度优先搜索(DFS)

(5) …

上面的没有做完，显然这里应该和链表一样填上很多题目d

队列

队列是另一种操作受限的线性结构。操作受限体现在，队列只能在一端添加元素，在另一端删除元素，符合**先进先出(FIFO)**的特性

基本操作

  1. 入队列 2. 出队列 3. 查看队头元素 4. 判空

实现

(a) 用链表实现 (作业)

(b) 用数组实现

一般都是用数组实现，性能更高

队列的设计1

如果是一般的数组来实现，把队头固定了，只有rear没有front 。

,这个时候，出队列就是性能的瓶颈 

1
2
3
4
5
6
7
8
9
 入队列:`elements[rear++] = val; O(1)`

**出队列:` O(n)`**

peek:O(1)

判空： `rear == 0`

判满：`rear == N

队列的设计2

有rear也有front 。但是存在浪费内存空间的问题

1
2
3
4
5
6
7
8
9
 入队列:`elements[rear++] = val; O(1)`

**出队列:` O(1)`**

peek:O(1)

判空： `rear == front`

判满：`rear == N

队列的设计2（也是最好最终的设计，循环队列）

1
2
3
4
5
6
7
8
 入队列:elements[rear] = val;
rear = (rear + 1) % N;
 O(1)
出队列:front = (front + 1) % N;
O(1)
peek:O(1)
判空： rear == front
判满：rear == front

如何区分空和满

如果人为有一个位置不存元素

1
2
判空： rear == front
判满： (rear + 1) % N == front

如果添加一个size,此时N个位置，0到N-1都能填数字

1
2
判空： size == 0
判满： size == N

实现

(a) 用链表实现 (作业)

(b) 用数组实现

Queue.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define N 10
typedef struct {
	int elements[N];
	int front;
	int rear;
	int size;
}Queue;
//API
Queue* queue_create();
void queue_destroy(Queue* q);

void queue_push(Queue* q, int val);
int queue_pop(Queue* q);
int queue_peek(Queue* q);

bool queue_empty(Queue* q);
bool queue_full(Queue* q);

Queue.c

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
35
36
37
38
39
40
41
42
43
44
45
46
#include "Queue.h"

//API
Queue* queue_create() {
	//create empty queue
	return calloc(1, sizeof(Queue));
}
void queue_destroy(Queue* q) {
	free(q);
}

void queue_push(Queue* q, int val) {
	if (queue_full(q)) {
		printf("Error: queue is full in queue_push\n");
		exit(1);
	}
	q->elements[q->rear] = val;
	q->rear = (q->rear + 1) % N;
	q->size++;
}
int queue_pop(Queue* q) {
	if (queue_empty(q)) {
		printf("Error: queue is empty in queue_pop\n");
		exit(1);
	}
	int tmp = q->elements[q->front];
	//
	q->front = (q->front + 1) % N;
	q->size--;
	return tmp;
}
int queue_peek(Queue* q) {
	if (queue_empty(q)) {
		printf("Error: queue is empty in queue_peek\n");
		exit(1);
	}
		return q->elements[q->front];
}

bool queue_empty(Queue* q) {
	return q->size == 0;
}
bool queue_full(Queue* q) {
	return q->size == N;
}

main.c

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
#include "Queue.h"
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
int main(void) {
	Queue* q = queue_create();
	if (!q) {
		printf("calloc failed in queue_create\n");
		exit(1);
	}
	//printf("front in queue is %d\n", queue_pop(q));
	//printf("front in queue is %d\n", queue_peek(q));
	for (int i = 0; i < 10; i++) {
		queue_push(q, i);
	}
	printf("front in queue is %d\n", queue_peek(q));
	printf("queue size is %d\n", q->size);
	//printf("pop front in queue is %d\n", queue_pop(q));
	printf("queue size is %d\n", q->size);


	//Traverse the queue
	int i = q->front;
	int size = q->size;
		while (!queue_empty(q)) {
			int val = queue_peek(q);
			printf("%d ", val);
			queue_pop(q);
	}

	printf("\n");
	printf("Queue is %s\n", queue_empty(q) ? "EMPTY" : "NOT EMPTY");
	return 0;
}

应用场景

(1) 缓冲

(2) 广度优先搜索(BFS)

(3)

哈希表

在现实生活中，我们经常需要存储键值对(key-value)数据，比如上面的 ‘a’:10, ‘b’:6，再比如账号:个人信息，关键字:网页等等。如果键的取值范围很小(比如上面的例子)，那么我们可以用数组存储，为每一个键绑定一个索引。

但是，如果键的取值范围很大，那么数组的方式就行不通了。哈希表就是被设计用来解决这样一个问题的

原理

哈希表的核心设计分为两个部分：

  1. 哈希函数。哈希函数将 key 转换为数组中的一个索引。理想情况下不同的 key 都能转换成不同的索引值。当然这只是理想情况，所以我们还需要处理两个或者多个key 都散列到相同索引值的情况 (哈希冲突)。

优秀的哈希函数需要满足这些特性 (拓展)：

a. 运算速度快。

b. 尽量使键平均分布

c. 逆向非常困难

d. 对数据非常敏感

e. 哈希冲突的概率非常小

哈希函数：模拟等概率随机分布事件。

对于实现哈希表而言，哈希函数只需要实现a, b的性质即可

2.处理哈希冲突。

a. 开放地址法线性探测法, 平方探测法, 再散列法…（这几个都是 理论层面，一般实现都不会用。不过考研肯定是要你手动熟悉一下过程简单计算的，背一背就好了）

b.拉链法

实现

这里，我们也采用常用的拉链法来解决哈希冲突，如下图所示：

Hashmap.h

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
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>

#define N 10
typedef char* K;
typedef char* V;

typedef struct node {
	K key;
	V val;
	struct node* next;
}Node;

typedef struct {
	Node* table[N];

}HashMap;

HashMap* hashmap_create();
void hashmap_destroy(HashMap* map);

V hashmap_put(HashMap* map, K key, V val);
V hashmap_get(HashMap* map, K key);
void hashmap_delete(HashMap* map, K key);

Hashmap.c

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include "Hashmap.h"

HashMap* hashmap_create() {
	//创建一个空的Hashmap
	return calloc(1, sizeof(HashMap));
}
void hashmap_destroy(HashMap* map);
// JS Hash Function: 由Justin Sobel发明的一种hash算法
unsigned int hash(const char* str) {
	unsigned int hash = 1315423911;
	while (*str) {
		hash ^= ((hash << 5) + (*str++) + (hash >> 2));
	}
	return (hash & 0x7FFFFFFF);
}
// 添加键值对
// 更新键关联的值
V hashmap_put(HashMap* map, K key, V val) {
	int idx = hash(key) % N;
	//遍历链表，判断键是否存在
	Node* curr = map->table[idx];
	while (curr) {
		if (strcmp(curr->key, key) == 0) {
			//更新值，此时不用创建新节点
			V oldVal = curr->val;
			curr->val = val;
			return oldVal;
		}
		curr = curr->next;
	}
	//curr  == NULL
	// 创建节点
	Node* newNode = malloc(sizeof(Node));
	if (!newNode) {
		printf("malloc failed in hashmap_put\n");
		exit(1);
	}
	newNode->key = key;
	newNode->val = val;

	//头插法插入节点
	newNode->next = map->table[idx];
	map->table[idx] = newNode;
	return NULL;

}
V hashmap_get(HashMap* map, K key) {
	int idx = hash(key) % N;
	//遍历链表，判断键是否存在
	Node* curr = map->table[idx];
	while (curr) {
		if (strcmp(curr->key, key) == 0) {
			//存在
			return curr->val;
		}
		curr = curr->next;
	}
	//curr  == NULL
	return NULL;
}
void hashmap_delete(HashMap* map, K key) {
	int idx = hash(key) % N;
	//遍历链表，判断键是否存在
	Node* curr = map->table[idx];
	Node* prev = NULL;
	while (curr) {
		if (strcmp(curr->key, key) == 0) {
			//存在
			//如果是第一个节点
			if (prev == NULL) {
				map->table[idx] = curr->next;
				free(curr);
				return ;
			}
			//如果不是第一个节点
			
			prev->next = curr->next;
			free(curr);
			return ;
		}
		prev = curr;
		curr = curr->next;
	}
	//curr  == NULL
	printf("Error: %s is not exist in map\n", key);
	return ;
}

main.c

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
#include "Hashmap.h"
int main(void) {
	HashMap* map = hashmap_create();
	if (!map) {
		printf("calloc failed in hashmap_create\n");
		exit(1);
	}

	hashmap_put(map, "xuwendong", "fool");
	hashmap_put(map, "jiujixinzhengddg", "foolboy");
	hashmap_put(map, "jindi", "king");
	hashmap_put(map, "huangjin", "kingdom");

	hashmap_put(map, "jindi", "MIT");
	hashmap_put(map, "huangjin", "QINGHUA");

	V val1 = hashmap_get(map, "jindi");
	V val2 = hashmap_get(map, "peanut");

	hashmap_delete(map, "xuwendong");
	hashmap_delete(map, "jindi");
	hashmap_delete(map, "xuwendong222");

	return 0;
}

分析

在哈希函数保证 key 平均分布的前提下，那么哈希表的性能就取决于**链表的平均长度(L)**。

put :O(L)

先对 key 进行哈希，找到对应的链表，然后遍历链表，判断是添加结点还是更新结点。

get :O(L)

先对 key 进行哈希，找到对应的链表，然后遍历链表，找到对应的结点。

delete :O(L)

先对 key 进行哈希，找到对应的链表，然后遍历链表，删除对应的结点。

但是教科书都说上面三个复杂度是O(1)。

如果我们想在常数时间复杂度内, 完成哈希表的增删查操作，那么我们就得控制链表的平均长度不超过某个值。这个值我们称之为加载因子(load factor)，也就是链表平均长度可以达到的最大值。

这个“某个值”是常数，因此教科书才说是O(1)

因此，当元素个数达到一定的数目的时候，我们就需要对数组进行扩容，然后把所有元素重新映射到哈希表

应用

哈希表的应用很广，比如 C++ 中的 unordered_map, unordered_set

和 Java 中的HashMap,HashSet底层的数据结构都是哈希表。再比如，常用的缓存中间件Redis，也大量使用了哈希表数据结构。

二叉搜索树

定义：二叉树是一棵树，并且二叉树的每个结点最多有两棵子树。二叉树的子树又分为左子树和右子树

完全二叉树和满二叉树

二叉树有两种特殊的形态：完全二叉树和满二叉树。完全二叉树：若二叉树的深度为 h，除第 h 层外，其它各层(1～h-1)的结点数目都达到最大值，第 h 层的结点都连续排列在最左边，这样的二叉树就是完全二叉树。满二叉树：每一层的结点数目都达到最大值(包括最下面一层)。

二叉搜索树

又叫二叉排序树。要求树中的结点可以按照某个规则进行比较，其定义如下：（本身又是一个递归的定义）

  1. 左子树中所有结点的 key 值都比根结点的 key 值小，并且左子树也是二叉搜索树。
  2. 右子树中所有结点的 key 值都比根结点的 key 值大，并且右子树也是二叉搜索树

基本操作

search ：若 BST 为空，则直接NULL。若 BST 非空，则和根结点比较，若和根结点相等，表明找到了。若比根结点小，则在左子树中递归查找；若比根结点大，则在右子树中递归查找。

insert ：若 BST 为空，则创建结点，将其作为根结点。若 BST 非空，则和根结点比较，若和根结点相等，则返回。若比根结点小，则在左子树中递归插入；若比根结点大，则在右子树中递归插入。

delete ：分三种情况处理。

a. 如果要删除结点没有孩子，那么直接将该结点删除就行了。

b. 如果要删除结点只有一个孩子，那么需要将父亲结点对应的指针，指向它唯一的孩子结点。

c. 如果要删除结点有两个孩子，那么我们可以找到这个结点的右子树中最小结点(或者左子树中最大结点)，把它替换到要删除的结点上，然后再删除右子树的最小结点 (或左子树的最大结点)

二叉树的建树

根据先序，中序，后序，中序的一种还原二叉树的模样

先序，中序可建树

后序，中序可建树

类似于根据正视图，侧视图，俯视图，还原立体图形的模样

实现

BST.h

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
35
36
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int K;

typedef struct tree_node {
	K key;
	struct tree_node* left;
	struct tree_node* right;

}TreeNode;

typedef struct {
	TreeNode* root;
	//把树都信息放在一个单独的结构体里面对他进行抽象
	//不过这里面只有一个指向根节点的指针，你也可以加 int size 等等，看你的需求了
}BST;
//API


BST* bst_create();
void bst_destroy(BST* tree);

void bst_insert(BST* tree, K key);
TreeNode* bst_search(BST* tree, K key);
void bst_delete(BST* treee, K key);

void bst_preorder(BST* tree);
void bst_inorder(BST* tree);
void bst_postorder(BST* tree);
void bst_levelorder1(BST* tree);
void bst_levelorder2(BST* tree);

BST* bst_bliudTree(K preorder[], K inorder[], int n);


Queue.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define N 10
typedef struct tree_node* E;
typedef struct {
	E elements[N];
	int front;
	int rear;
	int size;
}Queue;
//API
Queue* queue_create();
void queue_destroy(Queue* q);

void queue_push(Queue* q, E val);
E queue_pop(Queue* q);
E queue_peek(Queue* q);

bool queue_empty(Queue* q);
bool queue_full(Queue* q);

BST.c

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
#include "BST.h"
#include "Queue.h"
BST* bst_create() {
	return calloc(1, sizeof(BST));
}
void bst_destroyPost(TreeNode* node) {
	if (!node) return;
	bst_destroyPost(node->left);
	bst_destroyPost(node->right);
	//销毁根节点
	free(node);

}

void bst_destroy(BST* tree) {
	bst_destroyPost(tree->root);
	free(tree);

}

void bst_insert(BST* tree, K key) {
	

	//查找位置 ,先判断一下数里面有没有这个key，没有才创建节点。调用bst_search????
	//一般实现bst里面key的数值是唯一的，不允许重复
	TreeNode* parent = NULL;
	TreeNode* curr = tree->root;
	int cmp;
	while (curr) {
		cmp = key - curr->key;
		if (cmp < 0) {
			parent = curr;
			curr = curr->left;
		}
		else if (cmp > 0) {
			parent = curr;
			curr = curr->right;
		}
		else {
			
			return;
		}
	}
	//curr == NULL,，没有这个key，要分配空间开始插入了
	TreeNode* newNode = calloc(1, sizeof(TreeNode));
	if (!newNode) {
		fprintf(stderr, "malloc failed in bst_insert\n");
		//printf("malloc failed in bst_insert\n");
		exit(1);
	}
	newNode->key = key;

	//相当于链表的尾插法，链表的尾插法就是考虑两种情况 1.前面没有结点，链表为空 2. 前面有结点，链表不为空 
	//事实上，只要有跟节点，那么新的节点只能插入在根节点左子树或者右子树，不可能和链表一样插入在第一个节点前面，因此不用考虑插入的节点在根节点之前的情况
	//BST为空。。没有根节点，那么插入的节点就是跟节点

	if (parent == NULL) {
		tree->root = newNode;
	}
	//插入的位置在根节点后面
	else if (cmp < 0) parent->left = newNode;
	else  parent->right = newNode;
	return;
	// 这个不是二叉平衡数
}
// 类似链表的遍历操作
TreeNode* bst_search(BST* tree, K key) {
	TreeNode* curr = tree->root;
	if (!curr) return NULL;
	int cmp;
	while (curr) {
		cmp = key - curr->key;
		if (cmp < 0) curr = curr->left;
		else if (cmp > 0) curr = curr->right;
		else return curr;
	}
	//curr == NULL,  没有找到
	return NULL;
}
void bst_delete(BST* tree, K key) {
	//找到key对应的要删除的节点
	TreeNode* curr = tree->root;
	TreeNode* parent = NULL;
	int cmp;
	while (curr) {
		cmp = key - curr->key;
		if (cmp < 0) {
			parent = curr;
			curr = curr->left;
		}
		else if (cmp > 0) {
			parent = curr;
			curr = curr->right;
		}
		else break;
	}
	//curr == NULL或者 curr.key == keY
	if (curr == NULL) {
		printf("Error: key is not exist in tree\n");
		exit(1);
	}
	//删除该借点
	if (curr->left && curr->right) {
		//查找右子树的最大借点
		TreeNode* minOfRight = curr->right;
		TreeNode* minParent = curr;//别写成NULL

		while (minOfRight->left) {
			minParent = minOfRight;
			minOfRight = minOfRight->left;
		}
		//minOfRight->left == NULL
		//先将度为二点情况，退化为度为零 and 1的情况
		
		curr->key = minOfRight->key;

		parent = minParent;
		curr = minOfRight;
	}
	//删除curr指向的节点
	//处理度为零或者一点情况
	TreeNode* child = (curr->left ? curr->left : curr->right);
	//删除的是根节点,此时curr == tree.root, parent == NULL
	if (parent == NULL) {
		//删除根节点
		tree->root = child;
	}
	else if (curr->key < parent->key) {
		parent->left = child;
	}
	else parent->right = child;//个人感觉这里包含了curr->key = parent->key的情况也是存在的
	
	free(curr);
	return;
}
void preorder_helper(TreeNode* node) {
	if (!node) return;
	//遍历根节点
	printf("%d ", node->key);
	//遍历左子树
	preorder_helper(node->left);
	//遍历右子树
	preorder_helper(node->right);
}
void inorder_helper(TreeNode* node) {
	if (!node) return;
	//遍历左子树
	inorder_helper(node->left);
	//遍历根节点
	printf("%d ", node->key);
	//遍历右子树
	inorder_helper(node->right);
}
void postorder_helper(TreeNode* node) {
	if (!node) return;
	//遍历左子树
	postorder_helper(node->left);
	//遍历右子树
	postorder_helper(node->right);
	//遍历根节点
	printf("%d ", node->key);
}
void bst_preorder(BST* tree) {
	preorder_helper(tree->root);
	printf("preorder\n");
}
void bst_inorder(BST* tree) {
	inorder_helper(tree->root);
	printf("inorder\n");
}
void bst_postorder(BST* tree) {
	postorder_helper(tree->root);
	printf("postorder\n");
}
void bst_levelorder1(BST* tree) {
	if (tree->root == NULL) {
		return;
	}
	//将根节点入队列
	Queue* q = queue_create();
	if (!q) {
		printf("Error: calloc failed in queue_create\n");
		exit(1);
	}
	//1.根节点入队列
	queue_push(q, tree->root);
	//2.判断队列是否为空
	while (!queue_empty(q))
	{
		TreeNode* node = queue_pop(q);
		printf("%d ", node->key);
		//判断是否有左孩子
		if(node->left)
		queue_push(q, node->left);
		//判断是否有右孩子
		if(node->right)
		queue_push(q, node->right);
	}
	//队列为空，q is empty
	printf("levelorder\n");
	return;
}

TreeNode* bliud(K preorder[], K inorder[], int n) {
	// 递归边界条件
	if (n == 0) {
		return NULL;
	}
	//构建跟节点
	K key = preorder[0];
	TreeNode* node = malloc(sizeof(TreeNode));
	if (!node) {
		fprintf(stderr, "malloc failed in malloc\n");
		exit(1);
	}
	node->key = key;
	
	//找左子树小先，中序遍历序列
	int idx = 0;
	while (inorder[idx] != key) {
		idx++;
	} 
	//inorder[idx] == key
	//构建左子树
	node->left = bliud(preorder + 1, inorder, idx);
	//构建右子树
	node->right = bliud(preorder + 1 + idx, inorder + 1 + idx, n - idx - 1);
	return node;
}
BST* bst_bliudTree(K preorder[], K inorder[], int n) {
	BST* tree = bst_create();
	if (!tree) {
		return NULL;
	}
	//委托方法 
	tree->root = bliud(preorder, inorder, n);
	return tree;
}


void bst_levelorder2(BST* tree) {
	if (tree->root == NULL) {
		return;
	}
	//将根节点入队列
	Queue* q = queue_create();
	if (!q) {
		printf("Error: calloc failed in queue_create\n");
		exit(1);
	}
	//1.根节点入队列
	queue_push(q, tree->root);
	//2.判断队列是否为空
	while (!queue_empty(q))
	{
		int n = q->size; 
		for (int i = 0; i < n; i++) {
			TreeNode* node = queue_pop(q);
			printf("%d ", node->key);
			//判断是否有左孩子
			if (node->left)
				queue_push(q, node->left);
			//判断是否有右孩子
			if (node->right)
				queue_push(q, node->right);
		}
	}
	//队列为空，q is empty
	printf("levelorder\n");
	return;
}

Queue.c

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
35
36
37
38
39
40
41
42
43
44
45
46
#include "Queue.h"

//API
Queue* queue_create() {
	//create empty queue
	return calloc(1, sizeof(Queue));
}
void queue_destroy(Queue* q) {
	free(q);
}

void queue_push(Queue* q, E val) {
	if (queue_full(q)) {
		printf("Error: queue is full in queue_push\n");
		exit(1);
	}
	q->elements[q->rear] = val;
	q->rear = (q->rear + 1) % N;
	q->size++;
}
E queue_pop(Queue* q) {
	if (queue_empty(q)) {
		printf("Error: queue is empty in queue_pop\n");
		exit(1);
	}
	E tmp = q->elements[q->front];
	//
	q->front = (q->front + 1) % N;
	q->size--;
	return tmp;
}
E queue_peek(Queue* q) {
	if (queue_empty(q)) {
		printf("Error: queue is empty in queue_peek\n");
		exit(1);
	}
		return q->elements[q->front];
}

bool queue_empty(Queue* q) {
	return q->size == 0;
}
bool queue_full(Queue* q) {
	return q->size == N;
}

main.c

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
#include "BST.h"
#include "Queue.h"
int main() {
	// 创建一颗空书
	/*BST* tree = bst_create();
	if (!tree) {
		printf("calloc failed in bst_create\n");
		exit(1);
	}
	bst_insert(tree, 9);
	bst_insert(tree, 5);
	bst_insert(tree, 42);
	bst_insert(tree, 57);
	bst_insert(tree, 13);
	bst_insert(tree, 3);*/

	//TreeNode* node1 = bst_search(tree, 13);
	//TreeNode* node2 = bst_search(tree, 12);
	//bst_delete(tree, 3);
	//bst_delete(tree, 5);
	//bst_delete(tree, 9);

	/*bst_preorder(tree); 
	bst_inorder(tree); 
	bst_postorder(tree); 
	bst_levelorder(tree);*/
	int preorder[] = { 9, 5, 3, 42, 13, 57 };
	int inorder[] = { 3, 5, 9, 13, 42, 57 };
	BST* tree = bst_bliudTree(preorder, inorder, 6);
	return 0;
}

分析

BST 增加、删除和查找的效率取决于它的高度 h。

insert :O(h)

search :O(h)

delete :O(h)

有 n 个结点的二叉树，高度最低时 h = log2n (why?)，高度最高时 h = n (why?)。但是我们上面实现的 BST 并不能保证树的高度为 O(logn)，更糟糕的是，随着动态的插入和删除元素，整棵树会慢慢地向左倾斜(删除度为2的结点时，我们会在右子树中删除)。

要想保证二叉树增加，查找，删除的时间复杂度为 O(logn)，我们需要在添加结点和删除结点后，做一些调整操作，以保证二叉树的平衡。常见的平衡二叉树有：AVL树、红黑树、伸展树、树堆等。其中应用最广，名气最大的当属红黑树了

红黑树(拓展)

2 - 3 - 4 树

自己看pdf，非重点，了解会调用stl函数就行了

红黑树

自己看pdf，非重点，了解会调用stl函数就行了

我们可以用普通的 BST 来表示 2-3-4 树。可是，我们该如何表示3-结点和4-结点呢？

红黑树给出了一个很好的解决方案，我们可以用”红色”的边来表示3-结点和4-结点。如下图所示

3-结点有两种表示形式，而4-结点只有一种表示形式。可是”边”是不存在的呀，它只是逻辑上的一个结构，我们又该如何表示边的颜色呢？孩子结点到父亲结点的边是唯一的，所以我们可以用孩子结点的颜色，来表示孩子结点到父亲结点的边的颜色 

1
2
3
4
5
6
typedef struct treenode_s {
int val;
struct treenode_s* left;
struct treenode_s* right;
bool color;
}TreeNode

一棵红黑树是满足下面红黑性质的二叉搜索树：

  1. 每个结点或者是红色的，或者是黑色的
  2. 根结点是黑色的
  3. 叶子结点 (Nil) 是黑色的 (注：在算法导论中，叶子结点指得是 NULL 结点)
  4. 如果一个结点是红色的，则它的两个子结点都是黑色的 （4-node 只有一种编码方式）
  5. 对每个结点，从该结点到其所有后代叶子结点的路径上，包含相同数目的黑色结点。(黑高平衡， 2-3-4树是一个完美平衡的树)

代码随想录1二叉树理论基础

以下内容均来自https://programmercarl.com/

carl哥的（程序员Carl (opens new window)）的原创。

我仅做学习过程中的笔记总结。帮助自己理解记忆，绝不做任何商业盈利用途。如觉得侵权，请联系微信BradTorres，我一定删除。

代码随想录二叉树的视频笔记，感觉质量不足以我发到博客上面
map,set,mulipmap,mutipset底层是AVL平衡二叉树
unorderedmap,unorderedset底层是哈西表
存储方式：链式存储，数组存储（用的少，而且根节点从0开始从1开始要灵活，不能死记硬背，直接画图自己按照记忆推理一遍公式）
遍历方式：
深度优先搜索：前序，中序，后序，有递归实现也有迭代实现
但其实迭代写起来会比较麻烦
广度优先搜索：队列，FIFO

自己手写leetcode的结构体定义

二叉搜索树定义

前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树

平衡二叉搜索树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树的存储方式

二叉树可以链式存储，也可以顺序存储。

那么链式存储方式就用指针， 顺序存储的方式就是用数组。

顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。

二叉树的遍历方式

关于二叉树的遍历方式，要知道二叉树遍历的基本方式都有哪些。

一些同学用做了很多二叉树的题目了，可能知道前中后序遍历，可能知道层序遍历，但是却没有框架。

我这里把二叉树的几种遍历方式列出来，大家就可以一一串起来了。

二叉树主要有两种遍历方式：

  1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
  2. 广度优先遍历：一层一层的去遍历。

这两种遍历是图论中最基本的两种遍历方式，后面在介绍图论的时候 还会介绍到。

那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

  • 深度优先遍历
    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）
  • 广度优先遍历
    • 层次遍历（迭代法）

在深度优先遍历中：有三个顺序，前中后序遍历， 有同学总分不清这三个顺序，经常搞混，我这里教大家一个技巧。

这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。

看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式

  • 前序遍历：中左右
  • 中序遍历：左中右
  • 后序遍历：左右中

大家可以对着如下图，看看自己理解的前后中序有没有问题。

最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。

之前我们讲栈与队列的时候，就说过栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。

而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

这里其实我们又了解了栈与队列的一个应用场景了。

具体的实现我们后面都会讲的，这里大家先要清楚这些理论基础。

二叉树的定义

刚刚我们说过了二叉树有两种存储方式顺序存储，和链式存储，顺序存储就是用数组来存，这个定义没啥可说的，我们来看看链式存储的二叉树节点的定义方式。

C++代码如下：

1
2
3
4
5
6
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

2二叉树的递归遍历

思路

每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

  1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

以下以前序遍历为例：

  1. 确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入vector来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是void，代码如下：
1
void traversal(TreeNode* cur, vector<int>& vec)
  1. 确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：
1
if (cur == NULL) return;
  1. 确定单层递归的逻辑：前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：
1
2
3
vec.push_back(cur->val);    // 中
traversal(cur->left, vec);  // 左
traversal(cur->right, vec); // 右

单层递归的逻辑就是按照中左右的顺序来处理的，这样二叉树的前序遍历，基本就写完了，再看一下完整代码：

前序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

那么前序遍历写出来之后，中序和后序遍历就不难理解了，代码如下：

中序遍历：

1
2
3
4
5
6
void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中
    traversal(cur->right, vec); // 右
}

后序遍历：

1
2
3
4
5
6
void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
}

此时大家可以做一做leetcode上三道题目，分别是：

全部做完了，比较简单就补贴在这里了

可能有同学感觉前后中序遍历的递归太简单了，要打迭代法（非递归），别急，我们明天打迭代法，打个通透！

over

3二叉树的迭代遍历

为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历呢？

匹配问题都是栈道强项，递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。

前序遍历（迭代法）

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。

为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序

不难写出如下代码: （注意代码中空节点不入栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);           // 右（空节点不入栈）
            if (node->left) st.push(node->left);             // 左（空节点不入栈）
        }
        return result;
    }
};

后序遍历（迭代法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        vector<int> res;
        stack<TreeNode *> st;
        if (root == NULL)
            return res;
        st.push(root);
        while (!st.empty())
        {
            TreeNode *node = st.top();
            st.pop();
            res.push_back(node->val);
            if (node->left)
                st.push(node->left);
            if (node->right)
                st.push(node->right);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

中序遍历（迭代法）

处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素

中序遍历，可以写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

4二叉树的统一迭代法

仅作查阅参考

https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html#%E6%80%9D%E8%B7%AF

5二叉树的层序便利

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
class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        queue<TreeNode *> q;
        vector<vector<int>> result;
        if (root == NULL)
            return result;
        q.push(root);
        while (!q.empty())
        {
            int size = q.size();
            vector<int> vec;
            while (size--)
            {
                TreeNode *node = q.front();
                q.pop();
                vec.push_back(node->val);
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

递归实现明天再看，看不懂，有没有人讲

一个有思考，和我对递归类似数学归纳法的认知一样的视频讲解

【看到递归就晕？带你理解递归的本质！】 https://www.bilibili.com/video/BV1UD4y1Y769/?share_source=copy_web&vd_source=82180e49f17daecf14bb6f246fc29cd0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 递归法
class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth)
    {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

result.push_back(vector());什么意思

1
2
3
vector<vector<int>> vec;
vec.push_back(vector<int>());
vec.back().push_back();

第一句创建了一个实体为vertor的容器，可以理解为一个二维数组；

第二句话相当于分隔符了，往二维数组里插入空的vector()，可以理解为分行，即二维数组的下一行；（有些不够准确，应该说是往二维数组插入了一个一维向量，相当与初始化一行，但这一行的size为0，这一维向量没有元素。此时vec.size() 是1，因为只有一个一维向量。

result[depth].push_back(cur->val);这个就是在对应的一维向量里面插入元素。

模拟一下递归的过程，就知道，刚刚好创建了树的深度+1（根节点深度为零）也就是树的高度（假设根节点高度为一）个数的一维向量。结果完全正确。）

第三句话则是在每一行里插入数据。

转载自http://t.csdnimg.cn/DnB8H

https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html

下面是个大佬的博客

https://www.cnblogs.com/tyty-Somnuspoppy/p/9361821.html

问问群友，问了，自己也看明白了。给个感谢

6翻转二叉树

开始，别管上面了