二叉树求第三种遍历序列 Trie

二叉搜索树

二叉搜索树（Binary Search Tree）它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。
二叉搜索树能高效进行如下操作

• 插入一个数值
• 查询是否包含某个数值
• 删除某个数值

比较繁琐的地方是删除结点时, 对于 "需要删除的结点" 而言分3种情况
(所谓提上去是指提到现在需要删除的结点的位置)
1. 没有左儿子,那么就把右儿子提上去
2. 左儿子没有右儿子,把左儿子提上去
3. 以上2种情况都不满足,把左儿子的子孙中最大的结点提上去

struct nd {
    int val;
    nd *lch, *rch;
};

// 插入数值x
nd *insert(nd *p, int x) {
    if (p == NULL) {
        nd *q = new nd;
        q->val = x;
        q->lch = q->rch = NULL;
        return q;
    } else {
        if (x < p->val)
            p->lch = insert(p->lch, x);
        else
            p->rch = insert(p->rch, x);
        return p;
    }
}

// 是否存在数值x
bool find(nd *p, int x) {
    if (p == NULL) return 0;
    else if (x == p->val) return 1;
    else if (x < p->val) return find(p->lch, x);
    else return find(p->rch, x);
}

// 删除数值x, 返回删后链表的头指针
nd *remove(nd *p, int x) {
    if (p == NULL) return NULL;
    else if (x < p->val) p->lch = remove(p->lch, x);
    else if (x > p->val) p->rch = remove(p->rch, x);
    else if (p->lch == NULL){
        nd *q = p->rch;
        delete p;
        return q;
    }
    else if (p->lch->rch == NULL) {
        nd *q = p->lch;
        q->rch = p->rch;
        delete p;
        return q;
    } else {
        nd *q;
        for (q = p->lch; q->rch->rch != NULL; q = q->rch);
        nd *r = q->rch;
        q->rch = r->lch;
        r->lch = p->lch;
        r->rch = p->rch;
        delete p;
        return r;
    }
    return p;
}

Trie树，原理十分简单，看这道题就完事儿了。
这里权当备份个模板：

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define maxN 1000005
char a[maxN];

struct Trie {
  int nxt[26], cnt;
  void init() {
    cnt = 0, memset(nxt, -1, sizeof nxt);
  }
} T[maxN];
int L;

void insert(string s) {
  int p = 0;
  FOR(i, 0, (int)s.size() - 1) {
    int r = s[i] - 'a';
    if (T[p].nxt[r] == -1) {
      T[L].init();
      T[p].nxt[r] = L++;
    }
    p = T[p].nxt[r];
    T[p].cnt++;
  }
}

void query(string s) {
  int p = 0;
  FOR(i, 0, (int)s.size() - 1) {
    int r = s[i] - 'a';
    if (T[p].nxt[r] == -1) {
      cout << 0 << endl;
      return;
    }
    p = T[p].nxt[r];
  }
  cout << T[p].cnt << endl;
}

int main () {
  // freopen("data.in", "r", stdin);
  int n, m;
  cin >> n;
  T[0].init();
  L = 1;
  string s;
  FOR(i, 0, n - 1) cin >> s, insert(s);
  cin >> m;
  while (m--) {
    cin >> s;
    query(s);
  }
  return 0;
}

样例树

        4
     /     \
    1       6
     \     /   \
      3   5     7
     /
   2

前中求后序

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<(b);++i)

const int maxN = 35;
int N, M;
struct node { int v; node *lc, *rc; };
int mid[maxN], pre[maxN];

node* build(int *p, int *m, int len) {
    if (len == 0)
        return nullptr;
    node* prt = new node();
    prt->v = p[0];
    int idx;
    for (idx = 0; idx < len; ++idx)
        if (m[idx] == p[0])
            break;
    int lsz = idx, rsz = len - idx - 1;
    prt->lc = build(p + 1, m, lsz);
    prt->rc = build(p + 1 + lsz, m + idx + 1, rsz);
    return prt;
}
void print_path(node *prt) {
    if (prt == nullptr)
        return;
    print_path(prt->lc);
    print_path(prt->rc);
    printf("%d ", prt->v);
}

int main() {
    freopen("data.in", "r", stdin);
    scanf("%d", &N);
    rep(i, 0, N) scanf("%d", &mid[i]);
    rep(i, 0, N) scanf("%d", &pre[i]);

    node *prt = build(pre, mid, N);
    print_path(prt);
    return 0;
}

输入样例 节点个数+中序+前序：

7
1 2 3 4 5 6 7
4 1 3 2 6 5 7

输出样例：
2 3 1 5 7 6 4

后中求前序

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<(b);++i)
const int maxN = 35;
int N, M;

struct node { node *lch, *rch; int v; };

node* build(int *mid, int *post, int len) {
    if (len == 0)
        return 0;
    int rt_idx;
    for (rt_idx = 0; rt_idx < len; ++rt_idx)
        if (mid[rt_idx] == *(post + len - 1))
            break;

    node *rt = new node;
    rt->v = mid[rt_idx];

    rt->lch = build(mid, post, rt_idx);
    rt->rch = build(mid + rt_idx + 1, post + rt_idx, len - (rt_idx + 1));
    return rt;
}

void print_tree(node *rt) {
    if (rt == nullptr)
        return;
    printf("%d ", rt->v);
    print_tree(rt->lch);
    print_tree(rt->rch);
}

int main() {
    // freopen("data.in", "r", stdin);

    int post[maxN], mid[maxN];
    scanf("%d", &N);
    rep(i, 0, N) scanf("%d", &mid[i]);
    rep(i, 0, N) scanf("%d", &post[i]);

    node* rt = build(mid, post, N);
    print_tree(rt);
    return 0;
}

输入样例 节点个数+中序+后序：

7
1 2 3 4 5 6 7
2 3 1 5 7 6 4

输出样例：
4 1 3 2 6 5 7

还遇到一道题:

知道一颗树的bfs遍历和dfs遍历序列.其中遍历过程选择孩子的时候,总是选序号小的
比如一棵树如图,其bfs序列为 4 3 5 1 2 8 7 6，dfs序列为4 3 1 7 2 6 5 8

       4
     /    \
    3       5
   /  \      \
  2    1      8
  |    | 
  6    7

目的是求树重建后,所有节点的子节点列表.注意,如果树不唯一,随意输出一棵
题目戳这里
方法是:把bfs理解成每个节点离root的距离.
把root入栈, 遍历dfs的每个点:

• 若是当前点的距离 > 比栈顶元素距离+1, 意味着当前点是栈顶元素的孩子,图里做记录
• 否则,要么应该是到了某个祖先节点的兄弟了,当前子树已经搜索完毕,不断出栈

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define pb push_back
const int maxN = 1e3 + 5;
int N, dis[maxN];
vector<int> G[maxN];


int main() {
    // freopen("data.in", "r", stdin);
    while (~scanf("%d", &N)) {
        int e;
        rep(i, 1, N + 1) {
            scanf("%d", &e);
            G[i].clear();
            dis[e] = i;
        }

        int rt;
        stack<int> st;
        scanf("%d", &rt);
        st.push(rt);

        rep(i, 1, N) {
            scanf("%d", &e);
            while (1) {
                int u = st.top();
                if (u == rt || dis[e] > dis[u] + 1) {
                    G[u].pb(e);
                    st.push(e);
                    break;
                } else {
                    st.pop();
                }
            }
        }

        rep(i, 1, N + 1) {
            printf("%lld:", i);
            rep(j, 0, G[i].size())
                printf(" %d", G[i][j]);
            puts("");
        }
    }
    return 0;
}