排序二叉树（c++）

排序二叉树是一棵有顺序，且没有重复元素的二叉树。

对每个节点而言：

如果左子树不为空，则左子树上的所有节点的权值都小于该节点的权值。
如果右子树不为空，则右子树上的所有节点的权值都大于该节点的权值。

上图为一棵排序二叉树。相信你已经发现，将排序二叉树上的节点的权值按照中序遍历顺序排列成的序列，一定是严格单调递增的。

下面我们来讲一下如何构造一棵排序二叉树，我们主要运用 DFS 的方法。

算法思想：

假定我们要将数值 X 插入二叉树中。

1. 判断当前节点是否为空节点，若为空，则将 X 插入到该节点处。
2. 若不为空，比较当前节点的权值与 X 的大小。
3. X 小于当前节点的值，进入当前节点的左子树。
4. X 大于当前节点的值，进入当前节点的右子树。
5. 重复 1,2,3,4 步。

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

int tree[1010], pos[1010];
void dfs(int &root, int x) {
    if(tree[root] == -1){
        tree[root] = x;
        return ;
    }
    if (x < tree[root]){
        root *= 2;;
        dfs(root, x);
    } else if (x > tree[root]){
        root *= 2;
        root++;
        dfs(root, x);
    }
}
int main() {
    int n;
    cin >> n;
    memset(tree, -1, sizeof(tree));
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        pos[i] = 1;
        dfs(pos[i], x);
    }
    for (int i = 1; i <= n; i++) {
        cout << tree[pos[i]] << ' ' << tree[pos[i] * 2] << ' ' << tree[pos[i] * 2 + 1] << endl;
    }
    return 0;
}