树算法的整理总结

本篇是树算法的整理总结，树的一些算法以及函数的写法是总体固定的，因此需要记牢，故做此总结。在树的相关知识特别是二叉树的相关知识点中，特别要注意递归方法的使用，因为树或者二叉树本身就是递归定义的，特别适合使用递归的算法去解决相关问题。

建树

1. 根据遍历的序列建树

很经典的build函数写法，实际上就是通过主函数中对build的调用递归建树，前序中序或中序后序的建树都可以直接进行递归调用进行建树，而给出前序后序序列的建树需要枚举暴力搜索加上剪枝。
以下为典型的build写法:

int build(int il, int ir, int pl, int pr){
    int root = postorder[pr];
    //在数据量大时候需要使用哈希表，避免超时
    int k = pos[root];
    if(il < k){//向下递归的合法性检查
        l[root] = build(il, k - 1, pl, pl + (k - 1 - il));
    }
    //在递归的合适位置插入语句，可以得到相关的遍历序列
    if(k < ir){
        r[root] = build(k + 1, ir, pl + (k - 1 - il) + 1 ,pr - 1);
    }
    return root;
}

在使用上面写法的时候需要注意：不要忘记if判断条件

2.对多叉树建树

对多叉树的建树需要用到邻接表的存储，因为树本质上也是一种图，使用数组（静态链表）的方法模拟邻接表，能够提升算法的时间效率，此代码模板需要掌握的是邻接表的建立和dfs。
建树与dfs的代码如下：

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int root, int depth){
    if(终止条件){
        // ... 
    }
    for(int i = h[root]; ~i; i = ne[i]){
        dfs(e[i], depth + 1);
    }
    return;
}

3. 直接根据二叉树的值进行建树

这种方式的建树较为简单，题目会给出每个二叉树的儿子结点的值，直接定义l、r数组存储值即可。

4. 值与位置分离的方式建树

即定义自增的idx作为节点的编号，设置value数组再根据idx访问结点的值，这种方式的好处在于：
1. 即使给出的结点值再大，结点数组h等的长度仍然能够固定在N
2. 语义更加清晰，更加适用于算法，如二叉搜索树、二叉平衡树的算法

root = ++idx, v[root] = value ...

特殊二叉树算法

1. 连通分量算法

计算连通分量的算法可以考虑并查集，以下只是一个简单的并查集算法，待补充更加高效的并查集算法。

int find(int x){
    if(per[x] == x){
        return x;
    }
    return per[x] = find(per[x]);
}

2. 二叉搜索树（二叉排序树）

重要特征在于二叉搜索树的中序遍历顺序是有序的，因此给出二叉搜索树的前序遍历或者后序遍历就能够直接建立二叉搜索树，通过遍历的序列建树的方法同上。
另外就是通过直接插入数值建立二叉搜索树的算法，这个算法同二叉搜索树查找的算法非常像。插入的方式仍然是递归的。

void insert(int& root, int w){// 传入的是引用，递归向下更新
    if(root == 0){//类似于到达空节点
        root = ++idx;
        v[root] = w;
    }else if(w < v[root]){
        insert(l[root], w);
    }else{
        insert(r[root], w);
    }
    update(root);
}

3. 完全二叉树

完全二叉树的判断也是采用值与位置分离的方式建树，再利用深度优先搜索与完全二叉树的特性对树进行编号，通过编号数与总结点数n的比对得出是否是完全二叉树，编号的方式适合采用深度优先遍历的方式。

void dfs(int root, int u){
    if(u > maxid){
        maxid = u;
    }
    if(l.count(root)) dfs(l[root], 2 * u);
    if(r.count(root)) dfs(r[root], 2 * u + 1);
}

对于题目要求的完全二叉树判断，都应该利用完全二叉树的这种特性进行判断。

4. 二叉平衡树

二叉树的建立直接根据代码解释，其中很重要的部分是引用的传递以及递归的使用。左旋右旋的代码都应该凭借记忆完成。

const int N = 30;

int l[N], r[N], v[N], h[N], idx;
int n;

void update(int u){
    h[u] = max(h[l[u]], h[r[u]]) + 1;
}

void R(int& root){                  //对于R L的代码都能画图进行理解，这样更加直观
    int child = l[root];
    l[root] = r[child];
    r[child] = root;
    update(root), update(child);
    root = child;
}

void L(int& root){
    int child = r[root];
    r[root] = l[child];
    l[child] = root;
    update(root), update(child);    //此时root已经变成了孩子结点，因此先更新root后更新child
    root = child;
}

int get_balance(int root){
    return h[l[root]] - h[r[root]];
}

void insert(int& root, int w){
    if(root == 0){
        root = ++idx;
        v[root] = w;
    }else if(w < v[root]){
        insert(l[root], w);
        if(get_balance(root) == 2){
            if(get_balance(l[root]) == 1){
                R(root);                //RR
            }else{
                L(l[root]), R(root);    //LR
            }
        }
    }else{
        insert(r[root], w);
        if(get_balance(root) == -2){
            if(get_balance(r[root]) == -1){
                L(root);                //LL
            }else{
                R(r[root]), L(root);    //RL
            }
        }
    }
    update(root);   //更新根节点的高度
}

5. 哈夫曼树

哈夫曼树是使用贪心算法建立的树，在实现中，使用对进行哈夫曼树最小消耗的计算。

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

int main(void){
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> heap;
    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        heap.push(a);
    }
    int res = 0;
    while(--n){
        int x = heap.top();
        heap.pop();
        int y = heap.top();
        heap.pop();
        res += x + y;
        heap.push(x + y);
    }
    cout << res;
    return 0;
}