cartesianTree

发表于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

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;
  }
}*/