cartesianTree

cartesian tree

笛卡尔树是一颗二叉树,他满足中序遍历为维护的序列,且满足堆的性质

build

我们使用单调栈来维护树根到叶子的链,在单调栈的构建中完成树的构建

ct代码
treeview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*
#pragma once
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#include "../memery_management/memery_pool.h"
#include "tree.h"

template <class T>
class CT {
struct node {
node *ls, *rs;
T key;
};
memery_pool<node> pool;
node* root = nullptr;
node* newnode(const T& w) {
node* res = pool.get();
res->ls = res->rs = nullptr;
res->key = w;
return res;
}
void preorder(node*& rt, void (*f)(const T&)) {
if (rt == nullptr) return;
f(rt->key);
preorder(rt->ls, f);
preorder(rt->rs, f);
}
void midorder(node*& rt, void (*f)(const T&)) {
if (rt == nullptr) return;
midorder(rt->ls, f);
f(rt->key);
midorder(rt->rs, f);
}
void erase(node*& rt) {
if (rt == nullptr) return;
erase(rt->ls);
erase(rt->rs);
pool.erase(rt);
}

public:
CT() { root = nullptr; }
void preorder(void (*f)(const T&)) { preorder(root, f); }
void midorder(void (*f)(const T&)) { midorder(root, f); }
void build(T* a, int n) {
std::stack<node*> s; // 栈中维护从根到叶子的链
std::vector<node*> v;
for (int i = 0; i < n; i++) {
while (!s.empty() && a[i] > s.top()->key) {
v.push_back(s.top());
s.pop();
}
for (unsigned int i = 1; i < v.size(); i++) {
v[i]->rs = v[i - 1];
}
s.push(newnode(a[i]));
if (!v.empty()) {
s.top()->ls = v.back();
v.clear();
}
}
while (!s.empty()) {
v.push_back(s.top());
root = s.top();
s.pop();
}
for (unsigned int i = 1; i < v.size(); i++) {
v[i]->rs = v[i - 1];
}
v.clear();
}
void clear() { erase(root); }
};

void test() {
using namespace std;
CT<int> tree;
while (true) {
string input;
getline(cin, input);
stringstream line(input);
vector<int> v;
int x;
while (line >> x) v.push_back(x);
CT<int> ct;
ct.build(v.data(), v.size());
ct.preorder([](const int& w) { cout << w; });
cout << endl;
ct.midorder([](const int& w) { cout << w; });
cout << endl;
}
}*/