回顾下BST建树及相关性质
BST定义：
1、左子树的所有节点小于其根节点
2、右子树的所有节点大于其根节点
3、每个节点的左右子树也为二叉排序树
4、没有值相等的节点
BST性质之一：
中序遍历为有序序列
BST建树：
1、创建根节点
2、如果待插入的值小于该结点的左子节点，在该节点的左子树进行插入
3、如果待插入的值小于该结点的左子节点，在该节点的左子树进行插入
BST查找：
1、如果该结点的值等于val，则找到该节点
2、否则，若val小于该结点的值，查找其左子树
3、否则，若val大于该结点的值，查找其右子树
终止条件：该结点为空节点，或者找到该结点
完全二叉搜索树
- 给定序列建树并输出层序遍历
- 排序后进行中序遍历并赋值
实现：
#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2000010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
int T;
int n;
int len;
int a[N], res[N];
void dfs(int u)
{
if (u > n)
return;
dfs(u << 1);
res[u] = a[++len];
dfs(u << 1 | 1);
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
dfs(1);
for (int i = 1; i <= n; i++)
cout << res[i] << (i == n ? "" : " ");
}
signed main()
{
FAST;
T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
是否完全二叉搜索树
- 建树并判断是否为完全二叉数，层序遍历
- 这里tp结点类，左右指针指向左右子结点
实现：
#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2000010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
int T;
int n, m;
int a[N];
typedef struct Node
{
int val;
struct Node *lson;
struct Node *rson;
} *st, *tr;
void build(tr &root, int x)
{
if (root == NULL)
{
root = new Node();
root->val = x;
return;
}
if (root->val > x)
build(root->rson, x);
else
build(root->lson, x);
}
bool dfs(st a, tr b)
{
if (a == NULL && b == NULL)
return true;
else if ((a == NULL && b != NULL) || (a != NULL && b == NULL))
return false;
else if (a->val == b->val)
return dfs(a->lson, b->lson) && dfs(a->rson, b->rson);
return false;
}
void solve()
{
cin >> m;
st u = NULL;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
build(u, a[i]);
}
while (m--)
{
tr root = NULL;
for (int i = 1, x; i <= n; i++)
{
cin >> x;
build(root, x);
}
if (dfs(u, root))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
signed main()
{
FAST;
T = 1;
// cin >> T;
while (cin >> n && n)
solve();
return 0;
}
是否为同一棵BST
- 由插入序列判断是否为同一颗BST
- 由标准插入序列建立标准BST，再由比较插入序列分别建立比较BST
- dfs判断两者前序遍历是否相等
实现：
#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2000010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
int T;
int n, m;
int a[N];
typedef struct Node
{
int val;
struct Node *lson;
struct Node *rson;
} *st, *tr;
void build(tr &root, int x)
{
if (root == NULL)
{
root = new Node();
root->val = x;
return;
}
if (root->val > x)
build(root->rson, x);
else
build(root->lson, x);
}
bool dfs(st a, tr b)
{
if (a == NULL && b == NULL)
return true;
else if ((a == NULL && b != NULL) || (a != NULL && b == NULL))
return false;
else if (a->val == b->val)
return dfs(a->lson, b->lson) && dfs(a->rson, b->rson);
return false;
}
void solve()
{
cin >> m;
st u = NULL;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
build(u, a[i]);
}
while (m--)
{
tr root = NULL;
for (int i = 1, x; i <= n; i++)
{
cin >> x;
build(root, x);
}
if (dfs(u, root))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
signed main()
{
FAST;
T = 1;
// cin >> T;
while (cin >> n && n)
solve();
return 0;
}