系列文章目录：

树

树就是一种特殊的图，是一个无向图，是一种连通且无环的无向图。

含有以下内容：

树与二叉树的定义
二叉树的实现与遍历
树与森林
哈夫曼树与哈夫曼编码

树的定义：树是一个或者多个结点的有限集合，存在一个称为根的特定结点，其余结点分为若干个互不相交的集合，每个集合本身又是一棵树，这些树称为根的子树。如下图：

             F
           /   \
         D       J
       /   \    / \
     B     E  G   K
    / \             \
   A   C             L
     /  \  \     /  /  \
    I    H   M  N  O    P

一些重要名词

结点： 树中的每一个独立单元。
结点的度： 结点拥有的子树个数。
树的度： 树中所有结点度的最大值。
叶子： 度为0的结点或者终端结点。
分支结点： 度不为0的结点。
非终端结点： 除了根结点以外的所有结点。
双亲与孩子： 结点的子树的根称为该结点的还在，相应地，该结点称为孩子的双亲。（有的书上把其根也叫儿子，同时其结点叫父亲）。
层次： 结点的层次从根开始定义起，根为第一层，根的孩子为第二层，以此类推。
高度： 树中结点的最大层次。（也可以叫深度）
中心： 使得最大距离最小的结点，中心的个数为1或2。
重心： 使得所有子树结点数都不超过总结点数一半的结点。
森林： 若干棵独立的树组成的集合，不限制每棵树的高度。

树的基本性质

一棵有n个结点的树有且仅有n-1条边。
树中所有结点的度数之和等于边数加1，即 $\sum_{v \in V} deg(v) = e+1$ （其中 $n_i$ 表示度数为 $i$ 的结点个数，$e$ 是边数）。

证明如下：

设该树为无向图 $G=(V,E)$ ，其中 $V$ 为结点集个数为 $n$ ( $ |V|=n $ )，$E$ 为边集边数为 $e$ ( $ |E|=e $ )。

我们知道对于任意无向图，有如下恒等式：

$\sum_{v \in V} deg(v) = 2|E|$

对于树，满足 $e=n-1$

带入得：

$\sum_{v \in V} deg(v) = 2(n-1)= 2e$

对于度为 $m$ 的树，第 $i$ 层最多有 $m^{i-1}$ 个结点。
（严谨的说法为：对于任意满m叉树，第i层的结点严格满足： $|L_i|=m^{i-1}且|L_i| \le |L_{i+1}|$ ）
对于高度为 $h$ 度为 $m$ 的树，最多有 $\frac{m^h-1}{m-1}$ 个结点。

证明如下：

我们先举几个例子，然后用数学归纳法：

第一层：最多有 $m^0=1$ 个结点
第二层：最多有 $m^1$ 个结点
第三层：最多有 $m^2$ 个结点
第四层：最多有 $m^3$ 个结点 $\vdots$ 显然地，第 $i$ 层最多有 $m^{i-1}$ 个结点。（严格的数学归纳读者不难自证）

那么对于一共高度为 $h$ 的树，最多有：

$N_{max}=\sum_{i=0}^{h-1}m^i=\frac{m^h-1}{m-1} （等比数列求和）$

从树上不断删除叶子，能得到树的中心或者重心。（树的剪枝）
树中任意两点之间有且仅有一条简单路径。

二叉树

二叉树(Binary Tree) 是n个结点所构成的集合，它或为空树(n=0)，或为非空树，对于非空树T；

有且仅有一个根结点。
除根结点以外的其余结点分为两个互不相交的子集 $T_i$ 和 $T_2$ ，分别称为T的左子树和右子树，且 $T_i$ 和 $T_2$ 本身也是二叉树。

二叉树每个结点至多只有两颗子树，二叉树中结点的子树有左右之分，次序不能颠倒。

          F
        /   \
      D       J
    /   \    / \
  B     E  G   K
 / \             \
A   C             L

二叉树的性质

在二叉树的第 $i$ 层上至多有 $2^{i-1}$ 个结点。
深度为 $k$ 的二叉树至多有 $2^k-1$ 个结点。
对于满二叉树中，叶子数为度为2的结点数+1。
对于任何非空的二叉树，如果叶子的个数为 $n_0$ ，度为2的结点个数为 $n_2$ ，则 $n_0=n_2+1$ 。

特殊的二叉树

满二叉树（Full Binary Tree）： 满二叉树是指每一个非叶子结点都有两个孩子结点，并且所有叶子结点都在同一层的二叉树。
- 第 $i$ 层最多有 $2^{i-1}$ 个结点。（根为第1层）
- 总共有 $2^h-1$ 个结点。
完全二叉树（Complete Binary Tree）： 除了最后一层外，每一层的结点数都达到最大值，且最后一层的结点都集中在左部连续位置上。没有左子树，不能有右子树，上一层没铺满，不能有下一层
- 可以以用数组从索引1开始存储。
- 任意结点的编号为 $i$
  - 左儿子结点的编号为 $2i$ ，右儿子结点的编号为 $2i+1$
  - 父亲结点的编号为 $\left \lfloor i/2 \right \rfloor $
- 具有 $n$ 个结点的完全二叉树，深度为 $\left \lfloor \log_2 n \right \rfloor +1$ 。
二叉搜索树（Binary Search Tree, BST）： 满足左子树的所有结点值均<根结点值，右子树的所有结点值均>根结点值，且左右子树也是二叉搜索树。也叫二叉排序树(Bianry Sort Tree)。
- 中序遍历可以得到一个严格递增序列。
- 可支持动态查找、插入、删除操作，平均时间复杂度 $O(\log n)$。
平衡二叉树（AVL Tree）： 又称为AVL树，它是一棵特殊的二叉搜索树，且每个结点的左右子树的高度差不超过1。
- 高度平衡性保证了最坏时间复杂度为 $O(\log n)$
- 插入与删除后可能需要旋转操作 (LL,RR,LR,RR)
斜树： 所有结点都只有左子树或者只有右子树的二叉树，极端情况下，二叉树退化成一条链表。

二叉树的存储结构

根据我们之前学的知识，存储结构有：顺序存储和链式存储。那么对于二叉树同理。

顺序存储

二叉树的顺序存储结构就是用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树按层序遍历的顺序存储到一维数组中。

注意：除了满二叉树和完全二叉树外，一般的二叉树不推荐使用顺序存储——结点数不足的部分会空出位置或标记符号，造成存储空间的浪费

对于一般的二叉树，我们构造一个结构体，如下：

1 2	struct P{int val,L,R;}; //L和R存储的是结点的索引 vector<P> BTree;

由于其存储的便捷性，我们常常在竞赛中使用。并且在竞赛中，我们一般构造二叉树是用类似邻链表的方式构造。例如知道某个节点的左右儿子和值，那么就将其push_back进向量数组。

值得注意的是，对于满二叉树，我们可以直接用数组存储：

计层数为i，那么该层的下标（0开始）从左到右依次为：$2^i-1$ ~ $2^{i+1}-2$。
对于下标为i的节点，其左儿子下标为 $2i+1$ ，右儿子下标为 $2i+2$ 。

链式存储

二叉树由于是一种递归定义的数据结构，因此比较自然的存储方式就是链式存储。

struct TreeNode
{
    ElemType _data;    // 结点数据
    TreeNode *_left;   // 左儿子指针
    TreeNode *_right;  // 右儿子指针
    TreeNode(int x) : _data(x), _left(nullptr), _right(nullptr) {}  // 构造函数
};

遍历方式

前序遍历

前序遍历的顺序为：根结点->左子树->右子树

void preOrder(TreeNode* root)
{
    if(root==nullptr)
        return;
    cout<<root->_data<<" ";
    preOrder(root->_left);
    preOrder(root->_right);
    return;
}

同样地，对于直接用向量数组存储的二叉树，前序遍历为：

void preOrder(int x)
{
    cout<< BTree[x].val <<" ";
    if(BTree[x].L)preOrder(BTree[x].L);
    if(BTree[x].R)preOrder(BTree[x].R);
    return;
}

我们用这个例子来演示：

每个结点上的数字也是这个结点的值，对于这个二叉树，我们用数组存储，如下：

Index	Value	Left	Right
1	1	2	3
2	2	4	5
3	3	6	0
4	4	7	8
$\vdots$	$\vdots$	$\vdots$	$\vdots$
10	10	0	0

那么对于这个二叉树，我们进行前序遍历，结果为：1 2 4 7 10 8 11 12 5 3 6 9

不用函数嵌套的方法

void preOrder(TreeNode* root)
{
    if (!root) return;

    stack<TreeNode*> stk;
    stk.push(root);

    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        cout << node->_data << " ";
        if (node->_right) stk.push(node->_right);
        if (node->_left) stk.push(node->_left);
    }
}

可见，这个不用嵌套的方法，类似 bfs 而使用嵌套的方法类似 dfs

中序遍历

中序遍历的顺序为：左子树->根结点->右子树

void inOrder(TreeNode* root)
{
    if(root==nullptr)
        return;
    inOrder(root->_left);
    cout<<root->_data<<" ";
    inOrder(root->_right);
    return;
}

同样地，对于直接用向量数组存储的二叉树，中序遍历为：

void inOrder(int x)
{
    if(BTree[x].L)inOrder(BTree[x].L);
    cout<< BTree[x].val <<" ";
    if(BTree[x].R)inOrder(BTree[x].R);
    return;
}

对于刚刚二叉树，我们进行中序遍历，结果为：10 7 4 11 8 12 2 5 1 9 6 3

后序遍历

后序遍历的顺序为：左子树->右子树->根结点

void postOrder(TreeNode* root)
{
    if(root==nullptr)
        return;
    postOrder(root->_left);
    postOrder(root->_right);
    cout<<root->_data<<" ";
    return;
}

同样地，对于直接用向量数组存储的二叉树，后序遍历为：

void postOrder(int x)
{
    if(BTree[x].L)postOrder(BTree[x].L);
    if(BTree[x].R)postOrder(BTree[x].R);
    cout<< BTree[x].val <<" ";
    return;
}

对于刚刚二叉树，我们进行后序遍历，结果为：10 7 11 12 8 4 5 2 9 6 3 1

层序遍历

层序遍历的顺序为：从根结点开始，依次访问每一层的结点

void levelOrder(TreeNode* root)
{
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())
    {
        TreeNode* front = q.front();
        q.pop();
        cout<<front->_data<<" ";
        if(front->_left)
            q.push(front->_left);
        if(front->_right)
            q.push(front->_right);
    }
    return;
}

同样地，对于直接用向量数组存储的二叉树，层序遍历为：

void levelOrder(int x)
{
    queue<int> q;
    q.push(x);
    while(!q.empty())
    {
        int front = q.front();
        q.pop();
        cout<< BTree[front].val <<" ";
        if(BTree[front].L)q.push(BTree[front].L);
        if(BTree[front].R)q.push(BTree[front].R);
    }
    return;
}

对于刚刚二叉树，我们进行层序遍历，结果为：1 2 3 4 5 6 7 8 9 10 11 12

反过来造树

以下是我自己的思考，用来锻炼自己的思维能力。

前序

输入前序遍历的结果（这里修改下输出的函数，如果该结点的值为空输出#，并且值为非正整数），输出二叉树。

那么对于这个二叉树的前序遍历结果为：1 2 4 7 10 # # # 8 11 # # 12 # # 5 # # 3 6 9 # # # #

那么我们如何构造这棵树呢？我们注意到当树的某一分支遍历到底时，输出#，那么我们可以利用这个特性，

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define ld long double


struct P { int val, L, R; };
vector<P> BTree;
int p=0;

int build(const vector<string> &a)
{
	if(p>=(int)a.size() || a[p]=="#"){p++;return -1;};
	int val=stoi(a[p++]);
	int l=build(a);
	int r=build(a);
	BTree.push_back({val, l ,r});
	return BTree.size()-1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string x;
    vector<string> a;
    while(cin>>x) a.push_back(x);
    int root=build(a); //这里注意保留根节点的索引，该索引不一定是0开始。
}

这里用一个简单的例子说明下，为什么这个 build 函数可以成功构造一个树。

我们以上树为例，其前序遍历含空 # 的结果为：1 2 4 # # # 3 # #

那么从左到右依次读取有：

读取 1 ，有val=a[0]=1, p=1 进入左右子树：
- 左子树：读取 2 ，有 val=2, p=2 进入左右子树：
  - 左子树：读取4 ，有 val=4, p=3 进入左右子树：
    - 左子树：读取 # ，有 p=4 ，直接返回-1
    - 右子树：读取 # ，有 p=5 ，直接返回-1
    - 插入 {4, -1, -1} ，返回 BTree.size()-1=0
    - 右子树：读取 # ，有 p=6 ，返回-1
    - 插入 {2, 0, -1} ，返回 BTree.size()-1=1
- 右子树：读取 3 ，有 val=3, p=7 进入左右子树：
  - 左子树：读取 # ，有 p=8 ，返回-1
  - 右子树：读取 # ，有 p=9 ，返回-1
  - 插入 {3, -1, -1} ，返回 BTree.size()-1=2
- 插入 {1, 1, 2} ，返回 BTree.size()-1=3

这样我们就成功构造了这棵树。

如果我们用指针的链式结构，那么可以写成：

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int p=0;
TreeNode* build(const vector<string> &a)
{
    if(p>=(int)a.size() || a[p]=="#"){p++;return nullptr;}
    TreeNode* node = new TreeNode(stoi(a[p++]));
    node->left = build(a);
    node->right = build(a);
    return node;
}
//在调用的时候记得保存根节点的指针 TreeNode* root = build(a);

后序

后序遍历的方式为：左子树->右子树->根结点

显然那么我们应该先找到根结点，然后递归找到右节点和左节点，这样输入构建应该是倒着读取 a.reverse() ，那么 build 函数应为：

int build(const vector<string> &a)
{
	if(p>=(int)a.size() || a[p]=="#"){p++;return -1;};
	int val=stoi(a[p++]);
  int r=build(a);
	int l=build(a);
	BTree.push_back({val, l ,r});
	return BTree.size()-1;
}

中序

中序遍历的方式为：左子树->根结点->右子树

经过前面两个例子，我们发现只有确定根节点的位置才能构造树，显然对于中序遍历，把根节点放到中间，是不能直接用中序遍历输出，举个例子：

其中序遍历结果是：# 2 # 3 # 1 # ，但是对于这个树：

其中序遍历结果也是： # 2 # 3 # 1 # ，显然我们无法只通过中序遍历确定根节点。

那么是否能够通过前序+中序或者后序+中序构造树呢？

以下的输出结果不含有空占位符 # ！！！

前序+中序

对于构造一个二叉树，关键点在于如何确定根节点，那么对于前序+中序，我们可以通过前序遍历的首个元素确定整棵树的根节点，然后在中序遍历中找到该根节点，其左边部分是左子树，右边部分是右子树，对左右子树递归构造即可。

      1
    /   \
  2      5
/   \      \

3 4 6

例如这个二叉树的前序遍历结果为： 1 2 3 4 5 6 ；中序遍历结果为： 3 2 4 1 5 6

首先我们可以确定根节点的值为1，那么由中序遍历得，左子树为3 2 4 ，右子树为 5 6
接下来对于左子树 3 2 4，由前序遍历中的 2 3 4 可知，根节点值为 2 ，左子树为 3 ，右子树为 4
同理对于右子树 5 6，由前序遍历中的 5 6 可知，根节点值为 5 ，左子树为空，右子树为 6

以此我们可以递归构造这棵树。

int build(const vector<int>& a, const vector<int>& b, int al, int ar, int bl, int br)
{
  if(al>=ar || bl>=br) return -1;
  int val=a[al];
  int idx=tree.size();
  tree.push_back({val, -1, -1});
  int k=bl;
  while(b[k]!=val)k++;
  int ls=k-bl;  // 这里也可以写成 int ls = find(b.begin() + bl, b.begin() + br + 1, val) - b.begin() - bl;
  tree[idx].L=build(a, b, al+1, al+1+ls, bl, k); //构造左子树，前序[al+1,al+1+ls) 中序[bl,k)
  tree[idx].R=build(a, b, al+1+ls, ar, k+1, br); //构造右子树，前序[al+1+ls,ar) 中序[k+1,br)
  return idx;
}

如果我们用指针的链式结构，那么可以写成：

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int p=0;
TreeNode* build(const vector<int>& a, const vector<int>& b, int al, int ar, int bl, int br)
{
    if(al>=ar || bl>=br)return nullptr;
    int val=a[al];
    TreeNode* root = new TreeNode(val);
    int k=bl;
    while(b[k]!=val)k++;
    int ls=k-bl;
    root->left = build(a, b, al+1, al+1+ls, bl, k);
    root->right = build(a, b, al+1+ls, ar, k+1, br);
    return root;
}

后序+中序

对于后序+中序，我们可以通过后序遍历的最后一个元素确定整棵树的根节点，然后在中序遍历中找到该根节点，其左边部分是左子树，右边部分是右子树，对左右子树递归构造即可。注意：这里还是要 a.reverse() 。

int build(const vector<int>& a, const vector<int>& b, int al, int ar, int bl, int br)
{
  if(al>ar) return -1;
  int val=a[al];
  int k=bl;
  while(b[k]!=val)k++;
  int rs=br-k;
  int idx=tree.size();
  tree.push_back({val,-1,-1});
  tree[idx].R=build(a, b, al+1, al+ls, k+1, br);
  tree[idx].L=build(a, b, al+rs+1, ar, bl, k-1);
  return idx;
}

线索二叉树

在使用遍历二叉树时，我们总可以得到一个线性的序列，但是，这个序列是通过递归实现的，我们无法直接像链表一样得到这个序列，即知道遍历结果的某一个元素，无法直接找到它的前驱和后继。

而线索二叉树正是这样的一种结构，利用叶子空余的空间，来记录前驱和后继，从而实现直接找到前驱和后继。

构造（中序）

ThreadTree1

我们先来观察一下二叉树的中序遍历结果： D B G E A C H F

然后我们让每个节点空余的空间指向它的前驱和后继：

ThreadTree2

接下来，让我们来分析一下如何构造这样的二叉树：

我们需要找到节点的空指针，然后让这个空指针指向它的前驱（左）或者后继（右），并且为了区分孩子指针，我们再加入 bool pred=false, succ=false 作为左右指针是否为其前驱或者后继。

那么此时线索二叉树的节点结构为：

struct ThreadNode
{
    ElemType _data;
    ThreadNode *_left, *_right;
    bool _pred, _succ;
    ThreadNode(ElemType x) : _data(x), _left(nullptr), _right(nullptr), _pred(false), _succ(false) {}
}

值得注意的是，这样构造的二叉树是永远存在的，即节点的空指针总干好够用。

因为对于一个含有 $n$ 个节点的二叉树，有 $2n$ 个指针域、$n-1$ 个非空指针域，那么空指针域就有 $n+1$ 个。

对于中序遍历，有 $n-1$ 个节点的连接关系，即需要 $2(n-1)$ 个指针来存储前驱/后继关系。

当需要前驱/后继指针小于等于空指针数量时，即 $2(n-1)\le n+1 \Longrightarrow n \ge 3$

所以对于于含有 $n\ge 3$ 个节点的二叉树，都可以构造出中序线索二叉树。

但是，这样构造的二叉树，在遍历到最后一个节点或者第一个节点是时，必须要判断是否为空指针，否则会空指针异常。我们为了统一操作，以及为了方便遍历，我们在二叉树前加入一个头节点，这个头节点满足以下：

头节点的 *_left 指向树的根节点
头节点的 *_right 指向中序遍历的最后一个节点
中序遍历的第一个节点的 _left 指向头节点
中序遍历的最后一个节点的 _right 指向头节点

ThreadTree3

具体实现

下面，我们来写这个构造中序线索二叉树的函数，我们先进行中序遍历，如果这个节点的左指针为空，那么让它指向它的前驱，右指针为空，那么让它指向它的后继。显然地，我们在中序遍历的时候，还必须要要记录前驱节点，那么我们可以用 &*pre 来记录前驱节点。

void inThread(ThreadNode *node, ThreadNode *&pre)
{
    if(node==nullptr) return;
    inThread(node->_left, pre);  // 递归左子树
    // 进入当前节点
    // 如果当前节点没有左孩子，那么将其左孩子指向前驱节点
    if(!node->_left)
    {
        node->_left = pre;
        node->_pred = true;
    }
    // 如果前驱节点没有右孩子，那么将其右孩子指向当前节点
    else if(pre && !pre->_right)
    {
        pre->_right = node;
        pre->_succ = true;
    }
    pre=node; // 更新前驱节点
    inThread(node->_right, pre);  // 递归右子树
}


// 中序线索化二叉树，并加入head节点
ThreadNode *buildThreadTree(ThreadNode *root)
{
    ThreadNode *head = new ThreadNode(-1);
    // 特判： 如果根节点为空，那么直接返回head
    if(!root)
    {
        head->_left = head;
        head->_right = head;
        return head;
    }
    head->_left = root;  // 头节点的左指向根节点
    ThreadNode* pre = head;  // 设置前驱节点
    inThread(root, pre);  // 中序线索化二叉树
    // 此时中序遍历后，pre指向的是最后一个节点
    pre->_right = head;  // 最后一个节点的右指向头节点
    pre->_succ = true;
    head->_succ=true;  
    head->_right = pre;  // 头节点的右指向最后一个节点
    // 找到中序遍历的第一个节点
    ThreadNode *p=root;
    while(p && !p->_pred) p=p->_left;
    p->_left = head;  // 第一个节点的左指向头节点
    p->_pred = true;
    return head;
}

那么其中序遍历的方式就是直接用头节点：

void inOrder(ThreadNode *head)
{
    ThreadNode *p = head->_right;
    // 首先找到中序遍历的第一个节点
    while(p && !p->_pred) p=p->_left;
    // 然后按照线索遍历
    while(p!=head)
    {
        cout<<p->_data<<" ";
        // 如果当前节点没有右孩子，那么直接跳到下一个节点（后继）
        if(p->_succ) p=p->_right;
        else 
        {
            // 否则进入右子树，找右子树的最左下节点（中序下一个）
            p=p->_right;
            while(p && !p->_pred) p=p->_left;
        }
    }
}

竞赛中的方法

struct P
{
    int val,L,R;
    bool pred=false, succ=false;
};
vector<P> BTree; 
int pre = -1; // 前驱索引

void buildThread(int cur)
{
    if(cur == -1) return;

    // 左子树
    if(!BTree[cur].pred) buildThread(BTree[cur].L);

    // 当前结点处理
    if(BTree[cur].L == -1)
    {
        BTree[cur].L = pre;
        BTree[cur].pred = true;
    }
    if(pre != -1 && BTree[pre].R == -1)
    {
        BTree[pre].R = cur;
        BTree[pre].succ = true;
    }
    pre = cur;

    // 右子树
    if (!BTree[cur].succ) buildThread(BTree[cur].R);
}
// 使用时把根节点的索引传入cur即可: buildThread(root);

这个不使用指针的方法直戳构造的逻辑，写起来较为便捷。

构造（前序）

类似地，对于前序线索二叉树，我们只需要在构造使用前序遍历即可。

void preThread(ThreadNode *node, ThreadNode *&pre)
{
    if(node==nullptr) return;
    if(!node->_left)
    {
        node->_left = pre;
        node->_pred = true;
    }
    else if(pre && !pre->_right)
    {
        pre->_right = node;
        pre->_succ = true;
    }
    pre=node;
    // 注意：左右子树递归前需要判断是否是线索
    if(!node->_pred)preThread(node->_left, pre); 
    if(!node->_succ)preThread(node->_right, pre);  
}

ThreadNode *buildThreadTree(ThreadNode *root)
{
    ThreadNode *head = new ThreadNode(-1);
    if(!root)
    {
        head->_left = head;
        head->_right = head;
        return head;
    }
    head->_left = root;
    ThreadNode* pre = head;
    preThread(root, pre);
    pre->_right = head;
    pre->_succ = true;
    head->_succ=true;  
    head->_right = pre;
    // 前序第一个节点就是根节点
    root->_left = head;
    root->_pred = true;    
    return head;
}

在前序遍历中，这个判断 if(!node->_pred) 和 if(!node->_succ) 是必须要写的！！！

因为前序遍历的构造方式，会在“构造当前节点的线索”之后，马上访问它的左、右孩子。
而这些孩子可能——已经被线索占用了！

构造（后序）

后序遍历的线索二叉树的构造就很复杂了，因为在前节点处理时，左右子树已经线索化，递归处理复杂

void postThread(ThreadNode *node, ThreadNode *&pre)
{
    if(node==nullptr) return;
    if(!node->_pred)postThread(node->_left, pre);
    if(!node->_succ)postThread(node->_right, pre);
    if(!node->_left)
    {
        node->_left = pre;
        node->_pred = true;
    }
    else if(pre && !pre->_right)
    {
        pre->_right = node;
        pre->_succ = true;
    }
    pre=node;
}

ThreadNode *buildThreadTree(ThreadNode *root)
{
    ThreadNode *head = new ThreadNode(-1);
    if(!root)
    {
        head->_left = head;
        head->_right = head;
        return head;
    }
    // 头
    head->_left = root;
    head->_succ = true;

    ThreadNode* pre = head;
    postThread(root, pre);

    // 尾
    pre->_right = head;
    pre->_succ = true;
    head->_right = pre;

     // 找到最后一个后序节点（即最先访问的节点）
    ThreadNode* p = root;
    while (true) {
        if (!p->_pred) p = p->_left;
        else if (!p->_succ) p = p->_right;
        else break;
    }
    p->_left = head;
    p->_pred = true;

    return head;   
}

应用

虽然线索二叉树有这三种，但常用的也就一种，即中序线索二叉树。

这里举例一个详细的竞赛例子——二叉查找树（BST）：

struct P
{
    int val;
    int L=-1, R=-1;
    bool pred=false, succ=false;
};
vector<P> BSTree;
int root=-1; 
int pre=-1;

int insert(int root, int val)
{
    if(root == -1)
    {
        BSTree.push_back({val, -1, -1, false, false});
        return (int)BSTree.size() - 1;
    }
    if(val<BSTree[root].val) 
        BSTree[root].L=insert(BSTree[root].L, val);
    else BSTree[root].R = insert(BSTree[root].R, val);
    return root;
}

void buildThread(int cur)
{
    if(cur==-1) return;
    if(!BSTree[cur].pred) buildThread(BSTree[cur].L);
    if(BSTree[cur].L==-1)
    {
        BSTree[cur].L=pre;
        BSTree[cur].pred=true;
    }
    if(pre!=-1 && BSTree[pre].R==-1)
    {
        BSTree[pre].R=cur;
        BSTree[pre].succ=true;
    }
    pre=cur;
    if (!BSTree[cur].succ) buildThread(BSTree[cur].R);
}

// 使用时记得root=insert(root, val)来更新根节点

这个例子的打印函数：

void inorder_threaded(int root)
{
    int cur=root;
    while (!BSTree[cur].pred)cur=BSTree[cur].L;  // 找最左
    while (cur != -1)
    {
        cout << BSTree[cur].val << " ";
        if(BSTree[cur].succ) cur=BSTree[cur].R;
        else
        {
            // 找到最右，中序下一个节点
            cur=BSTree[cur].R;
            while(cur!=-1 && !BSTree[cur].pred)
                cur=BSTree[cur].L;
        }
    }
}

中序线索二叉树的其他应用，包括但不限于：

编译器构建抽象语法树（AST）后需要遍历树来生成代码或优化
- 树大且深，递归开销大，且遍历顺序很重要
- 使用中序线索二叉树可节省递归栈空间，且方便快速定位前驱后继节点，方便代码生成和优化
数据库索引的区间查询优化
- 频繁递归或栈访问影响性能，据库使用二叉排序树或B树做索引，快速区间查询需要有序访问节点
实时系统与嵌入式系统的资源受限环境
动态维护一棵二叉树，频繁插入和删除节点
- 插入删除时需要更新前驱和后继指针，普通树结构操作复杂，使用线索二叉树的前驱后继指针明确，便于快速定位插入位置和删除影响范围，提高动态更新效率

哈夫曼树

补充几个概念：

路径：一个节点到另一个节点的通路，一般有很多条。
路径长度：路径上经过的边的数量。
权：叶子上存储的数据，一般是一个数值。
带权路径长度：从根节点到叶子的路径长度（一般是层数）与该叶子上的权值乘积。
树的带权路径长度（Weighted Path Length of Tree， WPL）：树中所有叶子节点的带权路径长度之和。

例如下面这棵树：

          R
        /   \
      A     B
      / \     \
    C    D     4
   / \    \
  2   3    5

$WPL=\sum_{i=1}^{4}w_i l_i=2 \times 3+3 \times 3 + 5 \times 3 + 4 \times 2=34$

基本概念

对于一棵带权的二叉树，如果它的带权路径长度最小，那么这棵树就叫做哈夫曼树（Huffman Tree）。

对于于哈夫曼树来说，距离根节点越远的叶子节点权值越大，反之越小。

构造

我们考虑叶子的权值集合为 $\mathbf W={w_1, w_2, \cdots, w_n}$，在经过某种构造方法后：

$WPL=\sum_{i=0}^{n}w_i l_i$

我们以叶子所在层数划分，对于第 $i$ 层有 $ci$ 个叶子，其中 $i,c_i \in \mathbf N$ ，有叶子的权集合 $\mathbf W_i ={w{i1}, w{i2}, \cdots, w{ic_i}} \subseteq \mathbf W$，我们按照层开始求，那么有：

$\begin{aligned} WPL &= \sum_{i=0}^{n}w_i l_i \\ &=\sum_{i=0}^{c_1}w_{i1}+2\sum_{i=0}^{c_2}w_{i2}+\cdots+n\sum_{i=0}^{c_n}w_{in} \\ &=\sum_{j=1}^{n}\sum_{i=0}^{c_j}w_{ij}j \end{aligned}$

我们不难发现，欲WPL越小，那么要使得每层的带权路径长度最小，则尽量把大的权值放到低层，小的权值放到高层。

考虑到有 $n$ 个叶子的二叉树树，至少有 $2n-1$ 个节点（当且仅当满二叉树时），除去根节点即至少有 $2(n-1)$ 个节点，并且此时二叉树的层数也最小。

不难发现当每次取出权值最小的两个节点，构造一个新节点，然后依次递归，最后得到的必定是满二叉树，且权值大的节点在底层，权值小的节点在高层。

这里给出为什么$n$ 个叶子的二叉树树，至少有 $2n-1$ 个节点的证明：

我们知道对于一颗二叉树，节点下的孩子节点的数量可能为 ${0,1,2}$ 我们令：

叶子数 $L=n$
恰好有 1 个子节点的内部节点数 $c_1$
恰好有 2 个子节点的内部节点数 $c_2$

那么内部总节点数 $I=c_1+c_2$ ，总节点数（+叶子） $N=L+I$ ，有：

$c_1+2c_2=N-1=c_1+c_2+L-1 \Longrightarrow c_2=L-1$

因此总节点数 $N$ :

$N=L+I=L+c_1+c_2=L+c_1+(L-1)=2L-1+c_1$

当 $N$ 最小时，$c_1=0$ 也最小，因此 $N$ 最小为 $2L-1$ ，即 $2n-1$ 。

故当且仅当 $n$ 个叶子构成满二叉树 $c_1=0$ 时，$N$ 最小。

代码实现

于是我们可以按照上述思路，构造哈夫曼树：

先将叶子节点存入一个小根堆中（c++中是优先队列）
每次取出两个权值最小的节点，构造一个新节点，权值为两个节点的权值之和，然后将其插入堆中
重复上述过程，直到堆中只剩下一个节点，即为哈夫曼树的根节点

struct TreeNode
{
    int _weight=0;
    TreeNode* _left,*_right;
    TreeNode(int weight=0) :  _weight(weight), _left(nullptr), _right(nullptr) {};
};


// 小根堆比较器，用于优先队列
struct Compare
{
    bool operator()(TreeNode* a, TreeNode* b)
    {
        return a->_weight > b->_weight;
    }
};

priority_queue<TreeNode*, vector<TreeNode*>, Compare> pq;

void FindLeaves(TreeNode* root)
{
    if(!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())
    {
        TreeNode* cur = q.front(); q.pop();
        if(!cur->_left && !cur->_right)
        {   // 叶子
            if(cur->_weight != 0)
                pq.push(cur);
        } 
        else
        {
            if(cur->_left) q.push(cur->_left);
            if(cur->_right) q.push(cur->_right);
        }
    }
    return;
}

TreeNode* BuildHuffman()
{
    while(pq.size() > 1)
    {
        //选两个最小的
        TreeNode* left = pq.top(); pq.pop();
        TreeNode* right = pq.top(); pq.pop();
        // 构造父节点，权值为左右子树权值之和
        TreeNode* parent = new TreeNode(left->_weight + right->_weight);
        parent->_left = left;
        parent->_right = right;
        pq.push(parent);
    }
    return pq.empty() ? nullptr : pq.top();
}

用个例子测试一下：

int WPL(TreeNode* root)
{
    int res = 0;
    if(!root) return 0;
    queue<pair<TreeNode*,int>> q;
    q.push({root,0});
    while(!q.empty())
    {
        auto [cur, depth] = q.front(); q.pop();
        if(!cur->_left && !cur->_right && cur->_weight != 0) res += cur->_weight*depth;
        else
        {
            if(cur->_left) q.push({cur->_left, depth+1});
            if(cur->_right) q.push({cur->_right, depth+1});
        }
    }
    return res;
}

int main()
{
    TreeNode* root = new TreeNode();
    root->_right = new TreeNode();
    root->_left = new TreeNode();
    root->_right->_left = new TreeNode(2);
    root->_right->_right = new TreeNode(3);
    root->_left->_left = new TreeNode(12);
    root->_left->_right = new TreeNode();
    root->_left->_right->_left = new TreeNode(1);
    root->_left->_right->_right = new TreeNode(8);
    /**
     *          R
     *         / \
     *        R   R
     *      /  \  /  \
     *    12   R  2   3
     *        / \
     *       1   8
     **/
    FindLeaves(root);
    cout << WPL(BuildHuffman()) << endl;  // 49
    system("pause");

}

竞赛中的写法

#define pii pair<int,int>
struct node
{
    int W=0;
    int L=-1,R=-1;
};

// 这个是在原数组上再构建一颗树
// return Huffman Tree Root Index
int buildHuffman(vector<node> &tree)
{
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for(int i=0;i<tree.size();i++)
        if(tree[i].W!=0)pq.push({tree[i].W,i});
    queue<pii> q;
    while(pq.size()>1)
    {
        auto [lw,ldx]=pq.top(); pq.pop();
        auto [rw,rdx]=pq.top(); pq.pop();
        node pt;
        pt.W=lw+rw;
        pt.L=ldx;
        pt.R=rdx;
        int idx=tree.size();
        tree.push_back(pt);
        pq.push({pt.W,idx});
    }
    return pq.top().second;
}

哈夫曼编码

Huffman编码是一种无损压缩算法，用来根据字符出现频率生成最优前缀码（Prefix Code）

出现频率高的字符用更短的编码表示
出现频率低的字符用更长的编码表示
保证任何一个符号的编码都不是其他符号编码的前缀（前缀码性质），这样解码时不会产生歧义

编码步骤

统计每个字符出现的频率
每次取出权重最小的两个节点，构造一个新节点，权值为两个节点的权值之和，然后将其插入堆中
重复上述过程，直到堆中只剩下一个节点，即为哈夫曼树的根节点
从根开始：
- 向左走，编码加 0
- 向右走，编码加 1
- 直到走到叶子节点，该路径上的编码即为该字符的编码
按照编码表对原字符进行编码，得到编码后的编码串

代码实现

这里直接按照上述思路实现即可：

using pii=pair<string,int>;
using tpe=tuple<int,char,int>;

struct Node{char C;int W, L=-1, R=-1;};

map<char,int> freqm(string s)
{
    map<char,int> res;
    for(char c: s)res[c]++;
    return res;
}

map<char,string> HuffmanCodeList(map<char, int> &freq)
{
    priority_queue<tpe, vector<tpe>, greater<tpe>> pq;
    vector<Node> Htree;
    for(auto [ch,f]: freq)
    {
        Htree.push_back({ch,f});
        pq.push({f,ch,Htree.size()-1});
    }
    while(pq.size()>1)
    {
        auto [f1, ch1, i1] = pq.top();pq.pop();
        auto [f2, ch2, i2] = pq.top();pq.pop();
        Htree.push_back({'\0',f1+f2,i1,i2});
        pq.push({f1+f2,'\0',Htree.size()-1});
    }
    int root = get<2>(pq.top());
    map<char,string> res;
    queue<pii> q;
    q.push({"",root});
    while(!q.empty())
    {
        auto [code, i] = q.front();q.pop();
        if(Htree[i].C!='\0')
            res[Htree[i].C] = code;
        else
        {
            q.push({code+'0',Htree[i].L});
            q.push({code+'1',Htree[i].R});
        }
    }
    return res;
}

string HuffmanCode(string s)
{
    string res;
    auto freq = freqm(s);
    auto code = HuffmanCodeList(freq);
    for(char c: s) res+=code[c];
    return res;
}

测试代码：

int main()
{
    string s="Hello World!";
    auto freq = freqm(s);
    auto code = HuffmanCodeList(freq);
    for(auto [c,w]: freq) cout<<c<<" : "<<w<<endl;
    cout <<endl;
    for(auto [c,cde]: code) cout<<c<<" : "<<cde<<endl;
    cout <<endl;
    cout<<HuffmanCode(s)<<endl;
    system("pause");
    return 0;
}

哈夫曼解码

如果我们知道一个编码串和对应的哈夫曼编码表，那么我们应该如何快速地解码呢？

一个很自然的想法就是直接遍历编码字符串，维护一个 cur 字符串，把编码字符依次加入 cur 中，如果 cur 在编码表中，那么就输出对应的字符，并清空 cur，否则继续遍历。但是这样时间复杂度太高。

我们可以直接利用哈夫曼树进行解码，先用编码表构造一棵树，再遍历编码串，每次向左走或向右走，直到走到叶子节点，输出叶子节点对应的字符，然后回到根节点，继续遍历。

代码实现

struct Node {char C; int L=-1,R=-1;};

string decode(string HuffmanCode, map<char,string> HuffmanList)
{
    int root=0;
    vector<Node> HuffmanTree;
    string decodeStr;
    HuffmanTree.push_back({'\0',-1,-1});
    for(auto [c,code]: HuffmanList)
    {
        int cur=root;
        for(int i=0; i<code.size(); i++)
        {
            if(code[i]=='0')
            {
                if(HuffmanTree[cur].L==-1)
                {
                    HuffmanTree.push_back({'\0',-1,-1});
                    HuffmanTree[cur].L=HuffmanTree.size()-1;
                }
                cur=HuffmanTree[cur].L;
            }
            else
            {
                if(HuffmanTree[cur].R==-1)
                {
                    HuffmanTree.push_back({'\0',-1,-1});
                    HuffmanTree[cur].R=HuffmanTree.size()-1;
                }
                cur=HuffmanTree[cur].R;
            }
        }
        HuffmanTree[cur].C=c;
    }
    int cur=root;
    for(char c: HuffmanCode)
    {
        cur = (c=='0')? HuffmanTree[cur].L: HuffmanTree[cur].R;
        if(HuffmanTree[cur].C!='\0')
        {
            decodeStr+=HuffmanTree[cur].C;
            cur=root;
        }
    }
    return decodeStr;
}

这玩意再搞个进制转换和简单混淆，就可以实现简单密码的功能了。

树的补充

树的存储

由于树的孩子不止有两个，所以不能像二叉树那样用明确左右孩子的连接关系来存储，这里介绍几种不同的方式：

多叉树的指针存储

存储多叉树最自然的方式就是用一个数组存储节点的所有孩子指针

struct TreeNode
{
    ElmeType data;
    vector<TreeNode*> children;
}

为了方便回溯，我们还可以加入TreeNode* parent 其父节点的指针

父节点表示法

由于每个孩子都有且仅有一个父节点，于是直接使用一个数组来存储每个父节点的索引，这样就可以得到节点（该数组索引）->父节点位置（存储的值）的关系：

1 2	val: 1 -1 4 4 2 5 5 1 2 4 //-1表示为根节点 idx: 0 1 2 3 4 5 6 7 8 9

这样存储的好处是找父节点方便 $O(1)$ ，但是找子节点需要遍历整个数组 $O(n)$

子节点表示法

类似邻接表（Adjacency List）的方式来存储树的连接关系：

1 2	vector<vector<int>> children(n); children(x).push_back({...}); // 编号为x节点的孩子push进

这样存储的好处就是能够快速找到子节点，适合DFS/BFS，但是找父节点需要遍历整个数组 $O(m)$ 或者再开一个数组来记录。

如果直接使用邻接表，那么还需要把父节点的编号push进该节点的数组中，如此构造就方便使用图的算法、LCA、最短路等

邻接矩阵（Adjacency Matrix）

由于这时候的树已经很像图了，不妨直接用图的邻接矩阵来存储：

vector<vector<bool>> g(n, vector<bool>(n, false));  // or bool g[n][n];
g[1][2]=true;  // 1->2
g[2][1]=true;  // 2->1
...

这样对于两个节点的连接查询很方便，但是空间复杂度太高了，树很稀疏时很浪费，而且寻找父节点的子节点时间复杂度是 $O(n)$

兄弟表示法（Left-Child Right-Sibling, LCRS）

把一棵多叉树变成一棵二叉树，方便用二叉树的算法和结构处理。

每个节点都只保留两个指针：

leftChild 指向第一个孩子
rightSibling 指向同一父节点的下一个兄弟节点

这个在后续的树转化为二叉树会讲到。

树的遍历

树不像二叉树那样有左右子节点之分，按照搜索方式不同，树的遍历可以分为：先根遍历(dfs)、后根遍历(dfs)、层序遍历(bfs)。

这里我们都采取邻接表的存储方式进行遍历。

先根遍历

先根遍历顾名思义就是先访问根节点，再访问子节点，至于子节点的访问顺序？一般没有规定其顺序，可以直接遍历。

vector<int> data(n)={...};
vector<bool> vis(n, false);
void preOrder(int u)
{
    vis[u]=true;
    cout << data[u] << " ";
    for(int v : adj[u])if(!vis[v]) preOrder(v);
}

如果使用孩子表示法来存储树，那么这个遍历就不需要vis来避免访问到已经访问过的节点了。

这里补充一个使用邻接表避免多开一个vis数组的方法：

void preOrder(int u,int parent)
{
    cout << data[u] << " ";
    for(int v : adj[u])if(v!=parent) preOrder(v,u)
}

后根遍历

后根遍历顾名思义就是先访问子节点，再访问根节点。

vector<int> data(n)={...};
vector<bool> vis(n, false);
void postOrder(int u)
{
    vis[u]=true;
    for(int v : adj[u])if(!vis[v]) postOrder(v);
    cout << data[u] << " ";
}

同样地，后序遍历也可以避免使用vis数组，读者自己完成。

层序遍历

这个遍历方式和之前的二叉树层序遍历别无二致，使用队列即可。这里使用邻接表的方式举例，这时一定要多开一个vis数组。

vector<int> data(n)={...};
void levelOrder(int u)
{
    vector<bool> vis(n, false);
    queue<int> q;
    q.push(u);
    vis[u]=true;
    while(!q.empty())
    {
        int cur=q.front(); q.pop();
        cout << data[cur] << " ";
        for(int v : adj[cur])if(!vis[v]) 
        {
            vis[cur]=true;
            q.push(v);
        }
    }
}

树的转换

多叉树<——>二叉树

对于某个节点：

多叉树——>二叉树
- 左连孩子：将多叉树中某节点的第一个子节点作为该节点的左子节点。
- 右连兄弟：将多叉树中某节点的其他子节点依次作为其左子节点的右子节点。
二叉树——>多叉树
- 左孩子右兄弟：将二叉树中某节点的左子节点作为该节点的第一个子节点，右子节点作为该节点的下一个兄弟节点。

下面用bfs的方式展示（虽然一般用dfs更简洁直观🤫但动画都做好了🤗）：

alt text

具体的代码

多叉树——>二叉树

DFS 写法：

void treeToBtreeDFS(vector<vector<int> > &children,vector<node> &Btree,int u)
{
    Btree.assign(children.size(),{});
    if(u>=(int)children.size())return;
    int prev=-1;
    for(int i=0; i<(int)children[u].size(); i++)
    {
        int v=children[u][i];
        if(i==0)Btree[u].L=v;
        else Btree[prev].R=v;
        prev=v;
        treeToBtreeBFS(children,Btree,v);
    }
}

BFS 写法：

void treeToBtreeBFS(vector<vector<int> > &children,vector<node> &Btree,int root)
{
    Btree.assign(children.size(),{});
    queue<int> q;
    q.push(root);
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        const auto& kids=children[u];
        if(kids.empty())continue;
        Btree[u].L=kids[0];
        q.push(kids[0]);
        for(int i=1; i<(int)kids.size(); i++)
        {
            // 前一个孩子右指针指向下一个孩子
            Btree[kids[i-1]].R=kids[i];
            q.push(kids[i]);
        }
    }
}

二叉树——>多叉树

DFS 写法：

void BtreeToTreeDFS(vector<vector<int> > &children,vector<node> &Btree,int u)
{
    children.resize(Btree.size());
    int child=Btree[u].L;
    while(child!=-1)
    {
        children[u].push_back(child);
        BtreeToTreeDFS(children,Btree,child);
        child=Btree[child].R;
    }
}

BFS 写法：

void BtreeToTreeBFS(const vector<node> &Btree, vector<vector<int>> &children, int root)
{
    children.resize(Btree.size());
    queue<int> q;
    q.push(root);
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        int child=Btree[u].L;
        while(child!=-1)
        {
            children[u].push_back(child);
            q.push(child);
            child=Btree[child].R;
        }
    }
}

以上仅为示例，并不代表实际情况一定要这么写。

如果要多次使用并存到同一个容器，记得先clear() 。

二叉树<——>森林

对于某个节点：

二叉树——>森林
- 从根节点开始，如果右子节点存在，那么将该节点拆分，右子节点作为新树的根节点
- 继续向右移动，拆分，直到右子节点不存在
- 将所得的二叉树树转化为多叉树
森林——>二叉树
- 将森林中的每棵树层数对齐，最左的为根节点，向右依次连接为右子树
- 将连接所得的多叉树转化为二叉树

alt text

由于这里森林的表示方式有很多，包括但不限于：

邻接表 + 根节点数组

1 2	vector<int> children[N]; vector<int> roots;

左孩子–右兄弟（LCRS）二叉树表示
1
2
struct node{int L=-1,R=-1;};
vector<node> tree;
由于森林可以转化为二叉树，而LCRS表示方法可以直接表示二叉树、多叉树、森林，这样只用以上结构就可以表示不同的树，但就是不直观
虚拟根法

创建一个新的虚拟根 VR，所有森林的根挂到它下面，之后森林就是一颗树，做遍历就很方便
1
2
int VR = 0;
for (auto r : roots) children[VR].push_back(r);
使用父节点数组

用 parent[u] 存父节点编号，很省空间，但是对于查找遍历不方便，除非预处理或者加个 children 数组双查找。

具体的代码

下面只给出邻接表+根节点数组的示例代码：

二叉树——>森林

struct node{int L=-1,R=-1;};
void dfs(const vector<node> &Btree, vector<vector<int>> &children, int u)
{
    for(int c=Btree[u].L; c!=-1; c=Btree[c].R)
    {
        children[u].push_back(c); 
        dfs(Btree, children, c);  // 递归进入子节点
    }
}

// 把 LCRS 二叉树转换成森林
void btreeToForest(const vector<node> &Btree,vector<vector<int>> &children,vector<int> &roots,int root)
{
    for (int cur=root; cur!=-1; cur=Btree[cur].R)
    { // 遍历森林根链
        roots.push_back(cur);
        dfs(Btree, children, cur);
    }
}

或者用BFS写：

void btreeToForestBFS(const vector<node> &Btree,vector<vector<int>> &children,vector<int> &roots,int root)
{
    // 先找森林的所有根
    for (int cur=root; cur!=-1; cur=Btree[cur].R)
    {
        roots.push_back(cur);
        queue<int> q;
        q.push(cur);
        while(!q.empty())
        {
            int u=q.front(); q.pop();
            // 遍历 u 的左孩子链
            for (int c = Btree[u].L; c != -1; c = Btree[c].R)
            {
                children[u].push_back(c); 
                q.push(c);
            }
        }
    }
}

森林——>二叉树

void forestToBtree(const vector<node> &Btree,vector<vector<int>> &children,vector<int> &roots,int root)
{
    // 先串联根节点兄弟链
    for(int i=0; i<(int)roots.size(); i++)
    {
        if(i+1<(int)roots.size())
            Btree[roots[i]].R=roots[i+1];
        else Btree[roots[i]].R=-1;
    }

    // 对每个节点处理孩子链
    int n=(int)Btree.size();
    for(int u=0; u<n; u++)
    {
        if(children[u].empty()) Btree[u].L=-1;
        else
        {
            Btree[u].L=children[u][0];
            int m=(int)children[u].size();
            for(int i=0; i<m-1; i++)
                Btree[children[u][i]].R=children[u][i+1];
            // 最后一个孩子的右兄弟是 -1
            Btree[children[u][m-1]].R=-1; 
        }
    }
}

树

一些重要名词

树的基本性质

二叉树

二叉树的性质

特殊的二叉树

二叉树的存储结构

顺序存储

链式存储

遍历方式

前序遍历

中序遍历

后序遍历

层序遍历

反过来造树

前序

后序

中序

前序+中序

后序+中序

线索二叉树

构造（中序）

具体实现

构造（前序）

构造（后序）

应用

哈夫曼树

基本概念

构造

代码实现

哈夫曼编码

编码步骤

代码实现

哈夫曼解码

代码实现

树的补充

树的存储

多叉树的指针存储

父节点表示法

子节点表示法

邻接矩阵 （Adjacency Matrix）

兄弟表示法 （Left-Child Right-Sibling, LCRS）

树的遍历

先根遍历

后根遍历

层序遍历

树的转换

多叉树<——>二叉树

具体的代码

二叉树<——>森林

具体的代码

邻接矩阵（Adjacency Matrix）

兄弟表示法（Left-Child Right-Sibling, LCRS）