系列文章目录：

树

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

含有以下内容：

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

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

             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)
斜树： 所有结点都只有左子树或者只有右子树的二叉树，极端情况下，二叉树退化成一条链表。

二叉树的存储结构

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

顺序存储

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

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

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

struct TreeNode
{
    ElemType _data;    // 结点数据
    TreeNode *_left;   // 左儿子指针
    TreeNode *_right;  // 右儿子指针
};

但一般算法竞赛时，我们使用数组来存储，如下：

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

这样简洁的代码就可以存储一棵二叉树了。

遍历方式

前序遍历

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

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 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 pos=0;

int preOrderRE(const vector<string> &a)
{
    if(pos>=a.size() || a[pos]=="#") return pos++, -1;
        int idx = BTree.size();
    BTree.push_back({stoi(a[pos++]), -1, -1});
    BTree[idx].L = preOrderRE(a);
    BTree[idx].R = preOrderRE(a);
    return idx;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s,x;
    getline(cin,s);
    stringstream ss(s);
    vector<string> a;
    while(ss>>x) a.push_back(x);
    preOrderRE(a);
}