排序二叉树是一棵有顺序,且没有重复元素的二叉树。
对每个节点而言:
如果左子树不为空,则左子树上的所有节点的权值都小于该节点的权值。
如果右子树不为空,则右子树上的所有节点的权值都大于该节点的权值。
上图为一棵排序二叉树。相信你已经发现,将排序二叉树上的节点的权值按照中序遍历顺序排列成的序列,一定是严格单调递增的。
下面我们来讲一下如何构造一棵排序二叉树,我们主要运用 DFS 的方法。
算法思想:
假定我们要将数值 X 插入二叉树中。
- 判断当前节点是否为空节点,若为空,则将 X 插入到该节点处。
- 若不为空,比较当前节点的权值与 X 的大小。
- X 小于当前节点的值,进入当前节点的左子树。
- X 大于当前节点的值,进入当前节点的右子树。
- 重复 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;
}