二叉搜索树
二叉搜索树（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;
}
