判断前/后+中 是否能建树

pat1043

    bool build（）
    {
    if(inl>inr) return true;
    找k
    if(k==inr+1) return false;

    bool res=true;左右子树有一个找不到k就失败
左     if(!build()) res=false;
右     if(!build() res=false;

根    post【cnt++】=root
    return res;
    }

前+中 :
build（pl+1,pl+**k-inl**,inl,k-1）
build(pl+k-inl+1,pr,k+1,inr)

非完全二叉树建树（树的结构,l[],r[]）

算法：
pos[in[i]]=i; pos保存在中序的下标（不用while（k）找）
建树思想：找根

 unordered_map<int, int> l, r, pos;
    建树

    int build(int il, int ir, int pl, int pr)
    {
       int root = post[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;
    }

建树后输出层序

1. 输出层序（1.数组版 2队列版）
   2.需要知道每层的首尾——数组（Z字遍历，每层个数（待写））

1.1 数组版

void bfs(int root)
{
    int hh=0,tt=0;
    q[0]=root;
    while(hh<=tt)
        {
            int t=q[hh++];
            if(l.count(t)) q[++tt]=l[t];
            if(r.count(t)) q[++tt]=r[t];
        }

}

1.2 队列版
void bfs(int root)
{
    q.push(root);
    while(q.size())
    {
        int t=q.front();
        cout<<t<<" ";
        q.pop();
        if(l.count(t)) q.push(l[t]);
        if(r.count(t)) q.push(r[t]);
    }   
}

2
Z字层序 奇数层翻转
void bfs(int root)
{
    int hh = 0, tt = 0;
    q[0] = root;

    int step = 0;
    while (hh <= tt)
    {
        int head = hh, tail = tt;
        while (hh <= tail)
        {
            int t = q[hh ++ ];
            if (l.count(t)) q[ ++ tt] = l[t];
            if (r.count(t)) q[ ++ tt] = r[t];
        }

        if ( ++ step % 2) reverse(q + head, q + tail + 1);
    }
}

堆的建立、排序。

1.

插入一个数 heap[++size]=x;
2.
求集合中的最小值 heap[1]
3.
删除最小值 heap[1]=heap[size–];down(1); 最底下的换到根，再向下调整
4.
.删除任意一个元素：

heap【k】=heap【size–】；down（k）；up（k）
1.
修改任意一个元素

heap【k】=x；down（k）；up（k）；

h输入序列
int h[N], cnt;存当前heap有多少元素

down就是找三个点里的最小值，放到根
void down(int u)
{
t表示最小值 ，下标
int t = u;
左儿子存在且值小于
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
swap(h[u], h[t]);
down(t);
}
}
建小根堆
for (int i = n / 2; i; i – ) down(i);
输出前m小的数
while(m–)
{
cout<<h[1]<<” “;
h[1]=h[n–];
down(1);
}