排序二叉树（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;
}