Tree
线性表、栈和队列描述“一前一后”的关系。
树描述“一对多”的层级关系。
典型场景：
树 \(T\) 是结点的有限集合。
树可以为空。
若树非空，则存在一个特殊结点 \(r\)，称为根；其余结点被划分为若干棵互不相交的非空子树：
\[ T_1,T_2,\ldots,T_k \]
递归定义是树结构的核心。
| 维度 | 线性结构 | 树结构 |
|---|---|---|
| 关系 | 一对一前后关系 | 一对多父子关系 |
| 入口 | 通常是表头或栈顶 | 根 |
| 基本移动 | 前驱/后继 | 父、孩子、兄弟 |
| 典型遍历 | 从左到右 | 深度优先或广度优先 |
二叉树是有限结点集合。
当二叉树非空时：
左、右子树有顺序，因此只有左孩子和只有右孩子是不同结构。
| 维度 | 普通树 | 二叉树 |
|---|---|---|
| 孩子数 | 任意多个 | 最多两个 |
| 子树是否有序 | 常视为无序 | 左右有序 |
| 空子树 | 通常不显式出现 | 左空与右空要区分 |
| 存储方式 | 孩子链表、长子兄弟 | 左右孩子指针 |
该树表示：
\[ (a*b)+(c/d) \]
任何含 \(n>0\) 个结点的二叉树都有：
\[ n-1 \]
条边。
原因：除根结点外，每个结点恰好有一条来自父结点的边。
根在第 \(0\) 层时，第 \(i\) 层最多有：
\[ 2^i \]
个结点。
高度为 \(h\) 的二叉树最多有：
\[ 1+2+\cdots+2^h=2^{h+1}-1 \]
个结点。
设二叉树中：
则：
\[ n_0=n_2+1 \]
证明关键是边数：
\[ n-1=n_1+2n_2 \]
又有：
\[ n=n_0+n_1+n_2 \]
满二叉树：高度为 \(h\)，且结点数达到最大值：
\[ 2^{h+1}-1 \]
完全二叉树：按层从左到右编号时，结点编号连续，没有中间空洞。
完全二叉树是堆结构的基础。
若使用 0-based 编号：
\[ parent(i)=\left\lfloor \frac{i-1}{2}\right\rfloor \]
\[ left(i)=2i+1,\quad right(i)=2i+2 \]
若使用 1-based 编号：
\[ parent(i)=\left\lfloor \frac{i}{2}\right\rfloor \]
\[ left(i)=2i,\quad right(i)=2i+1 \]
数组表示适合完全二叉树。
若普通二叉树缺很多结点，数组表示会浪费空间。
| 结构 | 数组表示是否适合 |
|---|---|
| 完全二叉树 | 适合，公式简单 |
| 接近完全的二叉树 | 通常可接受 |
| 稀疏二叉树 | 空位过多，不适合 |
链式表示不需要保存空位，适合一般二叉树。
| index | data | left | right |
|---|---|---|---|
| 0 | A | 1 | -1 |
| 1 | B | 2 | 3 |
| 2 | C | -1 | -1 |
| 3 | D | 4 | 5 |
| 4 | E | -1 | 6 |
| 5 | F | -1 | -1 |
| 6 | G | -1 | -1 |
游标表示用数组下标模拟指针。
树的渐近复杂度常写成 \(O(h)\) 或 \(O(n)\)，但真实运行还取决于结点如何放在内存里。
操作系统管理虚拟内存时，分散节点可能带来更多页访问；数据库和文件系统中的树结构通常会把多个 key 放入一个页内，以减少 I/O 次数。
template <class T>
class BinaryTree {
public:
BinaryTree() = default;
~BinaryTree();
bool empty() const { return root_ == nullptr; }
void makeTree(const T& data, BinaryTree& left, BinaryTree& right);
void breakTree(T& data, BinaryTree& left, BinaryTree& right);
void preorder(void (*visit)(BinaryNode<T>*));
void inorder(void (*visit)(BinaryNode<T>*));
void postorder(void (*visit)(BinaryNode<T>*));
void levelOrder(void (*visit)(BinaryNode<T>*));
int height() const;
private:
BinaryNode<T>* root_ = nullptr;
};把两棵树接到新根下，原来的两棵树不再拥有这些结点。
拆分时也要明确所有权转移，避免重复释放。
顺序：根、左子树、右子树。
顺序：左子树、根、右子树。
顺序：左子树、右子树、根。
template <class T>
void levelOrder(BinaryNode<T>* root) {
if (root == nullptr) return;
std::queue<BinaryNode<T>*> q;
q.push(root);
while (!q.empty()) {
BinaryNode<T>* node = q.front();
q.pop();
visit(node);
if (node->left != nullptr) q.push(node->left);
if (node->right != nullptr) q.push(node->right);
}
}层序遍历的核心数据结构是队列。
栈保存“已经进入但尚未访问”的祖先结点。
这里约定空树高度为 \(-1\)，单结点树高度为 \(0\)。
若约定空树高度为 \(0\)，所有结果整体加一。
BinaryNode<char>* build(const std::string& preorder,
int preL, int preR,
const std::string& inorder,
int inL, int inR) {
if (preL > preR) return nullptr;
char rootValue = preorder[preL];
int rootPos = inorder.find(rootValue, inL);
int leftSize = rootPos - inL;
auto* root = new BinaryNode<char>(rootValue);
root->left = build(preorder, preL + 1, preL + leftSize,
inorder, inL, rootPos - 1);
root->right = build(preorder, preL + leftSize + 1, preR,
inorder, rootPos + 1, inR);
return root;
}先序给根，中序给左右子树边界。
| 已知序列 | 是否唯一 | 原因 |
|---|---|---|
| 先序 + 中序 | 是 | 根由先序确定，左右边界由中序确定 |
| 后序 + 中序 | 是 | 根由后序最后一个元素确定 |
| 先序 + 后序 | 通常否 | 无法区分只有左子树还是只有右子树 |
| 层序 + 中序 | 是 | 可逐层确定根并用中序切分 |
普通树可以转成二叉树形式：
firstChild 指向第一个孩子nextSibling 指向下一个兄弟这也称为孩子兄弟表示。
转换规则：
森林可以看作若干棵树的根互为兄弟。
转换规则：
森林遍历可以转化为二叉树遍历。
先根遍历：
后根遍历：
广度优先遍历使用队列。
含 \(n\) 个结点的二叉链表有 \(2n\) 个孩子指针域。
实际边数只有 \(n-1\)。
因此空指针数为：
\[ 2n-(n-1)=n+1 \]
线索二叉树用这些空指针保存遍历序列中的前驱或后继。
中序线索树中：
left == nullptr，可让 left 指向中序前驱right == nullptr，可让 right 指向中序后继中序线索树遍历不需要递归，也不需要栈。
设每个外结点权值为 \(w_i\)，从根到该外结点的路径长度为 \(l_i\)。
带权外路径长度：
\[ WPL=\sum_i w_i l_i \]
Huffman 树使 \(WPL\) 最小。
struct HuffmanNode {
int weight;
HuffmanNode* left = nullptr;
HuffmanNode* right = nullptr;
};
HuffmanNode* buildHuffman(std::vector<int> weights) {
auto cmp = [](HuffmanNode* a, HuffmanNode* b) {
return a->weight > b->weight;
};
std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, decltype(cmp)> pq(cmp);
for (int w : weights) pq.push(new HuffmanNode{w});
while (pq.size() > 1) {
HuffmanNode* a = pq.top(); pq.pop();
HuffmanNode* b = pq.top(); pq.pop();
pq.push(new HuffmanNode{a->weight + b->weight, a, b});
}
return pq.top();
}优先队列让每次取两个最小权值高效完成。
给左边标 0，右边标 1，从根到叶子的路径就是该字符编码。
Huffman 编码是前缀码：
| 问题 | 时间 | 空间 | 关键结构 |
|---|---|---|---|
| 二叉树遍历 | \(O(n)\) | 递归栈 \(O(h)\) | 栈或递归 |
| 层序遍历 | \(O(n)\) | 队列最坏 \(O(n)\) | 队列 |
| 先序+中序构造 | \(O(n)\) 或 \(O(n^2)\) | \(O(h)\) | 哈希表可优化定位 |
| 线索树遍历 | \(O(n)\) | \(O(1)\) 额外空间 | 线索指针 |
| Huffman 构造 | \(O(n\log n)\) | \(O(n)\) | 优先队列 |
题目：证明二叉树中 \(n_0=n_2+1\)。
答案：
\[ n=n_0+n_1+n_2 \]
边数既等于 \(n-1\)，也等于：
\[ n_1+2n_2 \]
因此：
\[ n_0+n_1+n_2-1=n_1+2n_2 \]
得到：
\[ n_0=n_2+1 \]
题目：完全二叉树第 6 层有 8 个叶结点，根为第 1 层，结点数最多是多少？
答案：
第 6 层最多有 \(2^5=32\) 个位置。
若第 6 层有 8 个叶结点且结点数最多，则这些叶结点应尽量靠右，前面位置尽量成为内部结点并拥有第 7 层孩子。
第 1 到 6 层满时有：
\[ 2^6-1=63 \]
第 6 层非叶最多 \(32-8=24\) 个，每个可有两个第 7 层孩子。
最大结点数：
\[ 63+48=111 \]
题目：一棵度为 4 的树中，度为 4、3、2、1 的结点数分别为 20、10、1、10，求叶结点数。
答案：
设叶结点数为 \(n_0\)。
总边数等于结点数减一：
\[ 4\cdot20+3\cdot10+2\cdot1+1\cdot10=n_0+20+10+1+10-1 \]
左侧为 \(122\)。
因此：
\[ 122=n_0+40 \]
\[ n_0=82 \]
每个结点访问一次，时间 \(O(n)\)。
该算法会把整棵二叉树变成镜像。
对于权值互不相同的字符构成的 Huffman 树：
正确结论是第二条和第三条。