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;
}

标签：return,val,--,define,int,GPLT,NULL,root,BST
From： https://www.cnblogs.com/Aidan347/p/17322570.html

GPLT--BST