c++非指针实现方法
题目描述
构造一个二叉搜索树,就是一个左边的值一定要比根节点的值要小,右边一定要比根节点要大,并且题目要求一定不要构造有两个值相同的节点
样例
5
1 6 5 9 8
1 6 5 9 8
1 5 6 8 9
5 8 9 6 1
算法1
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstdio>
#include <vector>
#include <unordered_set>
#include <cmath>
#include <map>
#include <set>
#include <deque>
using namespace std;
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define x first
#define y second
typedef pair<int, int > PII;
typedef pair<int, pair<int, int>> PIII;
const int N = 1e3 + 10, M = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m, k, root, idx;
int d1[] = {0, 0, 1, -1};
int d2[] = {1, -1, 0, 0};
int a[N];
struct edge{
int val;
int left, right;
}tr[N];
//这个build是我们用来递归构造二叉搜索树的方法,建议按照标的顺序来看
void build(int u, int val){
//4. 如果当前这个位置没有被赋予过值(题目上表明了输入数据必定大于等于1),那么把val赋给当前子节点并且退出递归
if(!tr[u].val){
tr[u].val = val;
return ;
}
//5. 如果值重复了直接退出递归即可
if(tr[u].val == val) return ;
//1. 我们先构造出根节点的左右儿子,如果tr[u].left或者tr[u].right为零就是没有构造过,我们用++idx来构造出来左右子树
if(!tr[u].left) tr[u].left = ++idx;
if(!tr[u].right) tr[u].right = ++idx;
//2. 如果根节点比我们要构造的值小,就证明这个值应该在右子树
if(tr[u].val < val) build(tr[u].right, val);
//3. 如果根节点比我们构造的值要大,就证明这个值应该在左子树
if(tr[u].val > val) build(tr[u].left, val);
}
//前序遍历二叉搜索树
void displaypre(int u){
cout << tr[u].val << ' ';
if(tr[tr[u].left].val) displaypre(tr[u].left);
if(tr[tr[u].right].val) displaypre(tr[u].right);
}
//后序遍历二叉搜索树
void displaylast(int u){
if(tr[tr[u].left].val) displaylast(tr[u].left);
if(tr[tr[u].right].val) displaylast(tr[u].right);
cout << tr[u].val << ' ';
}
//中序遍历二叉搜索树
void displaymid(int u){
if(tr[tr[u].left].val) displaymid(tr[u].left);
cout << tr[u].val << ' ';
if(tr[tr[u].right].val) displaymid(tr[u].right);
}
int main(void){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
// 我们把1这个点当做根节点(虽然这个root并没有什么意义);
root = 1;
tr[root].val = a[1];
idx = 1;
// 把第二个点开始往后的每一个点加入二叉搜索树里
for(int i = 2; i <= n; i ++){
build(1, a[i]);
}
displaypre(root);
cout << endl;
displaymid(root);
cout << endl;
displaylast(root);
return 0;
}
太nb了大佬
你在狗叫什么