无根树： 没有指定根节点的树，意味着它没有深度、高度、祖先、父子关系等概念
有根树： 有指定根节点的树
当有根树的有向边转化为无向边时，即为无根树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
struct NaryTreeNode {
int val;
std::vector<NaryTreeNode*> children;
NaryTreeNode(int x) : val(x) {}
};
|
树的遍历
树的遍历是指按照某种顺序访问树中的所有节点。常见的树遍历方法有以下几种：
- 前序遍历(先根遍历)（Pre-order Traversal）：先访问根节点，然后依次访问左子树和右子树
- 中序遍历（In-order Traversal）：先访问左子树，然后访问根节点，最后访问右子树
- 后序遍历(后根遍历)（Post-order Traversal）：先访问左子树，然后访问右子树，最后访问根节点
递归的实现
前序遍历
1
2
3
4
5
6
| void preOrder(TreeNode* root) {
if (root == nullptr) return;
visit(root);
preOrder(root->left);
preOrder(root->right);
}
|
中序遍历
1
2
3
4
5
6
| void inOrder(TreeNode* root) {
if (root == nullptr) return;
inOrder(root->left);
visit(root);
inOrder(root->right);
}
|
后序遍历
1
2
3
4
5
6
| void postOrder(TreeNode* root) {
if (root == nullptr) return;
postOrder(root->left);
postOrder(root->right);
visit(root);
}
|
非递归的实现
前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
| void preOrder(TreeNode* root) {
if (root == nullptr) return;
std::stack<TreeNode*> stack;
stack.push(root);
while (!stack.empty()) {
TreeNode* node = stack.top();
stack.pop();
visit(node);
if (node->right) stack.push(node->right);
if (node->left) stack.push(node->left);
}
}
|
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void inOrder(TreeNode* root) {
std::stack<TreeNode*> stack;
TreeNode* current = root;
while (current != nullptr || !stack.empty()) {
while (current != nullptr) {
stack.push(current);
current = current->left;
}
current = stack.top();
stack.pop();
visit(current);
current = current->right;
}
}
|
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void postOrder(TreeNode* root) {
if (root == nullptr) return;
std::stack<TreeNode*> stack1, stack2;
stack1.push(root);
while (!stack1.empty()) {
TreeNode* node = stack1.top();
stack1.pop();
stack2.push(node);
if (node->left) stack1.push(node->left);
if (node->right) stack1.push(node->right);
}
while (!stack2.empty()) {
visit(stack2.top());
stack2.pop();
}
}
|
前缀表达式就是前序遍历，中缀表达式就是中序遍历，后缀表达式就是后序遍历
树的存储
等长链表表示法
根据树的度为每个节点分配固定数量的指针域
优点：简单，管理容易
缺点：浪费空间，灵活性差
注意，由于分配的内存空间是固定的，所以占用空间只与节点总数有关，而与树的结构无关
1
2
3
4
5
6
7
8
9
10
| struct TreeNode {
int val;
TreeNode* children[MaxDegree];
TreeNode(int x) : val(x) {
for (int i = 0; i < MaxDegree; ++i) {
children[i] = nullptr;
}
}
};
|
变长链表表示法
采用边长链表存储每个节点的子节点
和上面类似，但是有几个指针域就有几个分叉，不会存在空指针域
优点：避免了定长链表的空间浪费
缺点：需要额外管理子女节点链表
1
2
3
4
5
6
| struct TreeNode {
int val;
std::list<TreeNode*> children;
TreeNode(int x) : val(x) {}
};
|
左儿子-右兄弟表示法
每个节点包含两个指针：一个指向其第一个子节点（左儿子），另一个指向其下一个兄弟节点（右兄弟）
这是一种将多叉树转化为二叉树的表示方法
由于二叉树的度数为则可以节省空间
优点：节省空间，适用于多叉树
缺点：访问子节点和兄弟节点需要额外的指针跳转
1
2
3
4
5
6
7
| struct TreeNode {
int val;
TreeNode* leftChild;
TreeNode* rightSibling;
TreeNode(int x) : val(x), leftChild(nullptr), rightSibling(nullptr) {}
};
|
进行多叉树到二叉树的转化后
多叉树的先根遍历为二叉树的前序遍历
多叉树的后根遍历为二叉树的中序遍历
双亲表示法
每个节点包含一个指向其父节点的指针
并查集是一种典型的双亲表示法应用
优点：便于访问父节点
缺点：不便于访问子节点，空间浪费
1
2
3
4
5
6
| struct TreeNode {
int val;
TreeNode* parent;
TreeNode(int x) : val(x), parent(nullptr) {}
};
|
数组的实现
1
2
| int data[MAX_N];
int parent[MAX_N];
|
层号表示法
按照前序写出树中全部结点，在节点前带上节点的层号
也就是层序遍历+前序遍历唯一确定一颗树
1
2
3
4
5
6
| struct TreeNode {
int val;
int level;
TreeNode(int x, int l) : val(x), level(l) {}
};
|
广义表表示法
根节点表示广义表的表头
广义表表示需要特别强调左右子树的区别
通过树构建广义表
- 深度优先遍历整棵树
- 进入节点时，添加，即将节点压入序列
- 如果有子节点
- 左括号压入序列
- 递归遍历节点的每个子节点
- 右括号压入序列
- 退出节点
广义表构建树
- 依次从保存广义表的字符串中输入字符
- 若是字母则表示结点值，建立新结点，作为左子 女或右子女链接到其父结点上
- 左括号则代表子树开始，置，右括号代表子树结束
- 遇到逗号则代表左子女为根的子树处理完毕，置
- 使用一个栈，在进入子树前将根节点指针进栈，处理完子树后出栈，继续处理根节点的其他子女
仅保留广义表表示中的括号
左括号用替代，右括号用替代
得到一个序列，称为欧拉序列
任意一对之间的元素构成以为根节点的子树的欧拉序列
霍夫曼树和霍夫曼编码
霍夫曼树(Huffman Tree)是一种带权路径长度最短的二叉树，常用于数据压缩中的霍夫曼编码
带权路径长度(WPL, Weighted Path Length)是指树中所有叶子节点的权值与其到根节点路径长度的乘积之和
霍夫曼编码(Huffman Coding)是一种无损数据压缩算法，通过构建霍夫曼树为每个符号分配可变长度的二进制编码，频率高的符号分配较短的编码，频率低的符号分配较长的编码，从而实现数据压缩
构建霍夫曼树的步骤：
- 初始化：将每个符号及其对应的权值作为一个独立的节点，放入一个优先队列（最小堆）中
- 构建树：重复以下步骤直到队列中只剩下一个节点为止：
- 从队列中取出两个权值最小的节点，作为新节点的左子节点和右子节点
- 创建一个新节点，其权值为两个子节点权值之和
- 将新节点插入队列中
- 生成编码：从根节点开始，为每个左子节点分配一个 ‘0’，为每个右子节点分配一个 ‘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
27
28
29
30
31
32
33
34
35
36
| void HuffmanCoding(const std::vector<int>& weights) {
struct Node {
int weight;
Node* left;
Node* right;
Node(int w) : weight(w), left(nullptr), right(nullptr) {}
};
auto cmp = [](Node* a, Node* b) { return a->weight > b->weight; };
std::priority_queue<Node*, std::vector<Node*>, decltype(cmp)> minHeap(cmp);
for (int w : weights) {
minHeap.push(new Node(w));
}
while (minHeap.size() > 1) {
Node* left = minHeap.top(); minHeap.pop();
Node* right = minHeap.top(); minHeap.pop();
Node* parent = new Node(left->weight + right->weight);
parent->left = left;
parent->right = right;
minHeap.push(parent);
}
Node* root = minHeap.top();
generateCodes(root, "", codes);
}
void generateCodes(Node* node, const std::string& code, std::unordered_map<char, std::string>& codes) {
if (!node) return;
if (!node->left && !node->right) {
codes[node->symbol] = code;
}
generateCodes(node->left, code + "0", codes);
generateCodes(node->right, code + "1", codes);
}
|
为什么霍夫曼编码的贪心选择过程是正确的？
可以通过交换论证法证明霍夫曼编码的贪心选择过程是正确的
假设我们有一个最优树，但它没有选择当前权值最小的两个节点进行合并
可以通过交换这两个节点与当前选择的节点来构造一个新的树，证明新树的总权值路径长度不会增加
从而说明选择当前权值最小的两个节点是正确的
霍夫曼编码是一种最优的前缀编码，但不是最优的熵编码，一般作为压缩算法的一个环节出现
算术编码是一种最优的熵编码，但也更复杂
多叉霍夫曼树
多叉霍夫曼树是霍夫曼树的一种扩展，允许每个节点有多个子节点，而不仅限于二叉树的两个子节点
构建多叉霍夫曼树的步骤类似于二叉霍夫曼树，但在每次合并节点时，可以选择多个权值最小的节点进行合并，具体步骤与二叉的有些许不同，需要补充节点使得节点数满足的倍数
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
| void buildDaryHuffmanTree(const std::vector<int>& weights, int d) {
struct Node {
int weight;
std::vector<Node*> children;
Node(int w) : weight(w) {}
};
auto cmp = [](Node* a, Node* b) { return a->weight > b->weight; };
std::priority_queue<Node*, std::vector<Node*>, decltype(cmp)> minHeap(cmp);
for (int w : weights) {
minHeap.push(new Node(w));
}
int n = weights.size();
int remainder = (d - 1 - (n - 1) % (d - 1)) % (d - 1);
for (int i = 0; i < remainder; ++i) {
minHeap.push(new Node(0));
}
while (minHeap.size() > 1) {
Node* parent = new Node(0);
for (int i = 0; i < d; ++i) {
if (minHeap.empty()) break;
Node* child = minHeap.top(); minHeap.pop();
parent->children.push_back(child);
parent->weight += child->weight;
}
minHeap.push(parent);
}
Node* root = minHeap.top();
}
|
树的直径
树的同构
无根树的同构等价于图同构
树的重心
LCA 最近公共祖先
朴素算法
倍增算法
欧拉序列
稀疏表
