%%
# 纲要
> 主干纲要、Hint/线索/路标
# Q&A
#### 已明确
#### 待明确
> 当下仍存有的疑惑
**❓<font color="#c0504d"> 有什么问题？</font>**
# Buffer
## 闪念
> sudden idea
## 候选资料
> Read it later
%%
# 二叉树
二叉树（Binary Tree）：**每个节点的出度至多为 2 的树**，即每个节点至多有两个子节点。
> [!NOTE] 含有 $n$ 个节点、高度为 $h$ 的二叉树，其高度 $h$ 与 $n$ 之间关系为：
>
> - $n = h + 1$ 时，二叉树退化为**一条单链**。
> - $n = 2^{h+1}-1$ 时，为**满二叉树**。
>
> 高度 $h$ 的范围为： $\log_2{(n+1)}-1\;\le h \le n-1$ ，满二叉树时**左侧取等**，单链时**右侧取等**。
> 
>
<br>
## 二叉树的构造
- 对于任意二叉树，根据 "**\[前序|后序\] + ==中序==**" 遍历序列可还原二叉树的结构。 **==中序序列是必需的==**。
- 如果只给定 "**前序 + 后序**" 遍历序列：
- 对于一般二叉树，根据 "**前序** + **后序**" 序列 **不能唯一地确定一棵二叉树**。
- 对于 **==真二叉树==**，根据 "**前序** + **后序**" 可还原真二叉树的结构。
#### 根据前序 + 中序遍历序列构造二叉树
```cpp
TreeNode* buildBinaryTreeByPreorderAndInorder(vector<int>& preorder, vector<int>& inorder) {
// 哈希表建立val->中序下标映射, 便于查找.
int n = inorder.size();
unordered_map<int, int> val2idx;
for (int i = 0; i < n; ++i) {
val2idx[inorder[i]] = i;
}
// build根据前序数组中root下标, 中序数组区间进行构建.
auto build = [&](auto& self, int pre_l, int in_l, int in_r) -> TreeNode* {
if (in_l > in_r) return nullptr;
int in_root = val2idx[preorder[pre_l]]; // 中序数组中root下标
int left_cnt = in_root - in_l; // 左子树大小
auto root = new TreeNode(preorder[pre_l]);
root->left = self(self, pre_l + 1, in_l, in_root - 1);
root->right = self(self, pre_l + left_cnt + 1, in_root + 1, in_r);
return root;
};
return build(build, 0, 0, n - 1);
}
```
<br>
## 二叉树的遍历
前中后序遍历：
> [!NOTE] "迭代" 写法进行前中后序遍历的思路
>
> - 前序遍历的思路：
> - 沿着左侧链不断向下展开直至为空，**处理链上各个节点**，**并将已处理过的节点入栈**
> - 为空时，将栈中节点弹出，并**直接进入节点的右子树**。
>
> - 中序遍历的思路：
> - 沿着左侧链不断向下展开直至为空，**不访问链上节点，而将节点先入栈**
> - 为空时，**弹出栈中节点，处理该节点并转而进入到右子树**。
>
> - 后序遍历的思路：
> - 沿着左侧链不断向下展开直至为空，**不访问链上节点，而将节点先入栈**
> - 为空中，**弹出栈中节点**，**若该节点的右子树还未被访问，则将当前节点再入栈，而先访问其右子树**。
> - 若该节点的右子树已被访问，则处理该节点，而后转为空（下一步继续从栈中取出节点）。
#### 四种遍历的迭代实现
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
// 前序遍历
vector<int> preorderTravel(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
TreeNode* p = root;
while (p || !stk.empty()) {
while (p) {
res.push_back(p->val);
stk.push(p);
p = p->left;
}
p = stk.top();
stk.pop();
p = p->right;
}
return res;
}
// 中序遍历
vector<int> inorderTravel(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
TreeNode* p = root;
while (p || !stk.empty()) {
while (p) {
stk.push(p);
p = p->left;
}
p = stk.top();
stk.pop();
res.push_back(p->val);
p = p->right;
}
return res;
}
// 后序遍历
vector<int> postorderTravel(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
TreeNode* p = root, *prev = nullptr;
while (p || !stk.empty()) {
while (p) {
stk.push(p);
p = p->left;
}
p = stk.top();
stk.pop();
if (p->right && p->right != prev) {
stk.push(p);
p = p->right;
} else {
res.push_back(p->val);
prev = p;
p = nullptr;
}
}
return res;
}
// 层序遍历
vector<int> layerTravel(TreeNode* root) {
if (!root) return {};
vector<int> res;
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
int size = que.size();
while (size--) {
auto node = que.front(); que.pop();
res.push_back(node->val);
if (node->left) {
que.push(node->left);
}
if (node->right) {
que.push(node->right);
}
}
}
return res;
}
```
<br>
<br>
<br>
# 特殊二叉树
特殊二叉树包括：
- **满二叉树**（完美二叉树）
- **完全二叉树**
- 真二叉树（完整二叉树）
- 最优二叉树
- **二叉搜索树/二叉查找树**
- **平衡二叉树**
- **平衡二叉搜索树**
<br>
# 真二叉树
> 也称 "完整二叉树"。
所有节点的出度要么为 0，要么为 2。
![[_attachment/00-数据结构与算法笔记/数据结构/二叉树.assets/IMG-二叉树-F75933ABA24337DCAE32CEB6FDAA50EF.png|293]]
<br>
# 最优二叉树（Huffman 树）
给定 $n$ 个权值 $w_1$，$w_2$，…，$w_n$ **作为 $n$ 个叶子节点**，
在由此构成的所有二叉树中，**树的==带权路径长度最小== (即代价最小) 的二叉树**称为 **最优二叉树** 或 **==霍夫曼树==** [^1]。
> [!NOTE] "带权路径长度" 定义
>
> - **叶节点的带权路径长度**：叶节点到根节点之间的 **路径长度** 与 **该叶节点上权值** 的乘积。
> - **树的带权路径长度** (Weighted Path Length of Tree，WPL)：为树中所有 **==叶结点==** 的**带权路径长度之和**。
设 $w_{i}$ 为第 $i$ 个叶节点的权值，$l_{i}$ 为从根节点到第 $i$ 个叶节点的 "**路径长度**"，则 WPL 计算公式为：
$
W P L=\sum_{i=1}^n w_i l_i
$
<br>
## 霍夫曼树构造
![[_attachment/00-数据结构与算法笔记/数据结构/二叉树.assets/IMG-二叉树-56C0519F3EEB0D6513B11DD23E54127A.png|696]]
## 霍夫曼编码
霍夫曼树可用于 "**对一组字符进行二进制编码**"，构造得到 "**最短前缀编码**"（不等长编码），称之为 "**==霍夫曼编码==**"。
方法步骤：
- （1）统计**各个字符出现==频次==**，作为**字符的权值**。
- （2）以各**字符权值** 作为叶节点，构造一棵**霍夫曼树**。
- （3）规定霍夫曼树中，**左分支代表 0，右分支代表 1**，则从**根节点到叶节点所==经过的路径构成的 "01" 序列==** 即为**叶节点对应的 "==字符编码=="**。
> [!example] 霍夫曼编码
> ![[_attachment/00-数据结构与算法笔记/数据结构/二叉树.assets/IMG-二叉树-1DF81BB298037759032A206960EE1759.png|590]]
<br><br>
# 满二叉树
> **满二叉树**（full binary tree）
定义：**除叶节点外，==所有节点都有两个子节点==的二叉树，且叶节点只存在于最后一层**。 => 即每一层都全被填满
> [!NOTE] 二叉树高度：`[0, h]`
> 
#### 满二叉树的基本性质
- **节点总数**为 $n=2^{h+1}-1$；其中 $h$ 是树的高度（从 0 起，根节点高度为 0）
- **第 $i$ 层的节点数为 $2^{i}$**，最后一层节点数为 $2^h$。
#### 满二叉树的 "节点编号" 性质
对满二叉树中的节点按 "**前序遍历**" 顺序进行编号：
- 若记**根节点从 0 起**，则对 **==编号为 $i$ 的节点==**，其**左子节点编号为 $2^i+1$，右子节点编号为 $2^i+2$**。
- 若记**根节点从 1 起**，则对 **==第 $i$ 个节点==**，其**左子节点编号为 $2^i$，右子节点编号为 $2^i+1$**。
- 对于第 $k$ 个节点：
- 若其**位于第 h 层的节点**，其**有效二进制位共 h+1 位**。
- $k$ 值的二进制最高位为 1 ，其余各位**从高到低**依次表明 **==从根节点到该节点的路径==**，0 代表进入左子节点，1 代表进入右子节点。
![[Excalidraw-Solution/二叉树.excalidraw.svg|494]]
%%[[Excalidraw-Solution/二叉树.excalidraw.md|🖋 Edit in Excalidraw]]%%
> [!example] 例题： [[99-题解/leetcode/lc-222 完全二叉树的节点个数|lc-222 完全二叉树的节点个数]]
##### 满二叉树构造
```cpp
// 构造指定层数的完全二叉树. 根节点值从1起
TreeNode* buildFullBinaryTree(int layers) {
if (layers == 0) return nullptr;
queue<TreeNode*> que;
TreeNode* root = new TreeNode(1);
que.push(root);
int i = 2;
--layers;
while (layers--) {
int size = que.size();
while (size--) {
auto node = que.front();
que.pop();
node->left = new TreeNode(i++);
node->right = new TreeNode(i++);
que.push(node->left);
que.push(node->right);
}
}
return root;
}
```
<br><br>
# 完全二叉树
> **完全二叉树**（complete binary tree）
定义：叶节点只出现在**最底层**和**次底层**，且**最底层**的叶子节点**集中在树的左部**。
> [!NOTE] 即除最后一层外，其余每层全被填满，且**最后一层的所有节点均集中靠左**的二叉树。
完全二叉树性质：
- 除去最**后一个内部节点**，其余**每个内部节点均有两个子节点**。
- 完全二叉树中，**==任一节点==的左右两个子树**，**至少有一棵是满二叉树，另一棵是满二叉树或完全二叉树**。
- 高度为 $h$ 的完全二叉树，其**节点总数在 $[2^h, 2^{h+1}-1]$ 范围内**。
##### 完全二叉树构造
```cpp
// 构造n个顶点的完全二叉树(队列方式)
TreeNode* buildCompleteBinaryTree(int n) {
if (n == 0) return nullptr;
queue<TreeNode*> que;
int idx = 1;
TreeNode* root = new TreeNode(idx++);
que.push(root);
--n;
while (n) {
auto node = que.front();
que.pop();
node->left = new TreeNode(idx++);
if (--n == 0) break;
node->right = new TreeNode(idx++);
if (--n == 0) break;
que.push(node->left);
que.push(node->right);
}
return root;
};
// 构造n个顶点的完全二叉树(辅助数组的方式)
TreeNode* buildCompleteBinaryTree(int n) {
if (n == 0) return nullptr;
vector<TreeNode*> nodes(n, nullptr);
for (int i = 0; i < n; ++i) {
nodes[i] = new TreeNode(i + 1); // 顶点值从1起
}
for (int i = 0; i < n; ++i) {
int left = 2*i + 1;
int right = 2*i + 2;
if (left >= n) break; // 已是叶节点
nodes[i]->left = nodes[left];
if (right < n) {
nodes[i]->right = nodes[right];
}
};
return nodes[0];
};
```
<br><br>
# 二叉搜索树
> **二叉搜索树/二叉查找树**（Binary Search Tree）
**定义**：对于树中的任一节点，其**左子树上的所有节点==小于==根节点**，**右子树上的节点==大于==根节点**。
> [!caution] 一般情况下，二叉搜索树中**不允许存在重复的节点 key**，否则查找操作返回结果可能不确定。
### BST 建树
- 给定序列中，**首项元素为根节点**。
- 确定根节点后，**插入新节点时，小的往左子树，大的往右子树**
> [!NOTE] **根节点始终不变**
### BST 中进行查找
- 时间复杂度：$O(\log n) = O(h)$， $h$ 为树高。
- 从**根节点出发**，若**目标值大于当前子树根节点值**则进入右子树，否则进入左子树。当**进入空树时代表查找失败**。
### BST 的性质
- **==单调性==**：
- 中序遍历得到**节点值的 "==升序序列=="**；
- 中序遍历，但对每个节点，**都先访问右子树**，则得到 "**降序序列**"。
- **数量与平均高度**
- 含有 $n$ 个元素的序列的**所有排列**所可能构成的**不同二叉搜索树数量**（无重复值）恰为**卡特兰数** $\large \frac{(2n!)}{n!(n+1)!}$，**所有 BST 的平均高度为 $\sqrt{n}$。**
- 不是 $n!$，因为某些不同排列可能得到一样的 BST，例如序列`{2, 1, 3}` 和 `{2, 3, 1}`
#### 等价 BST
**拓扑结构不同的两棵 BST 可能得到完全相同的==中序遍历序列==**，称之为 "**==等价 BST==**"。
两棵等价 BST 满足如下性质
- **上下可变**：两棵树中某两个节点间的**祖先后代关系可能颠倒**；
- **左右不乱**：对任何节点而言，位居其左侧、右侧的节点间不会混淆，**保证中序遍历结果不变**。
> [!example] 如下图，两棵等价 BST 中，16 和 19 两节点的祖先关系颠倒。
>
> 
>
<br><br>
# 平衡二叉树
平衡二叉树定义：树中**所有节点的 "==左右子树==" 的高度差不超过 1**。
<br><br>
# 参考资料
- [树基础 - OI Wiki](https://oi-wiki.org/graph/tree-basic/#%E7%89%B9%E6%AE%8A%E7%9A%84%E6%A0%91)
# Footnotes