代码在本地跑能把数据正确输出,但最后会显示程序停止运行(return value 255)。
如果把析构函数注释掉的话能在本地正常运行(return value 0),但交上来会RE。 代码如下:
#include <cstdio>
#include <iostream>
using namespace std;
template <typename Type>
class BST {
private:
//默认值
Type DefaultValue;
//节点
struct Node {
//数据
Type Value;
//同样的数据有多少个
int Number;
//该节点的左右分别各有多少个数据,注意不是节点的个数
int LeftNumber, RightNumber;
//左右孩子
struct Node *LeftChild, *RightChild;
//Node的构造函数
Node(Type value) {
this->Value = value;
this->Number = 1;
this->LeftNumber = this->RightNumber = 0;
this->LeftChild = this->RightChild = NULL;
}
} * root;
//递归删除节点以及它的两个子节点
void del(struct Node* node) {
if (node != NULL) {
del(node->LeftChild);
del(node->RightChild);
delete node;
node=NULL;
}
}
public:
//构造函数
BST(Type defaultValue);
//析构函数
~BST(void);
//插入数据
void insert(Type data);
//获取数据的排位
int getTurn(Type data);
//获取排位的数据
Type getValue(int turn);
//获取数据的前一个数据
Type getFront(Type data);
//获取数据的后一个数据
Type getBack(Type data);
};
template <typename Type>
BST<Type>::BST(Type defaultValue) {
root = NULL;
DefaultValue = defaultValue;
}
template <typename Type>
BST<Type>::~BST(void) {
del(root);
}
template <typename Type>
void BST<Type>::insert(Type data) {
if (root == NULL) {
root = new struct Node(data);
return;
}
struct Node* node = root;
while (!(node->Value == data)) {
if (data < node->Value) {
node->LeftNumber++;
if (node->LeftChild == NULL) {
node->LeftChild = new struct Node(data);
return;
} else {
node = node->LeftChild;
}
} else {
node->RightNumber++;
if (node->RightChild == NULL) {
node->RightChild = new struct Node(data);
return;
} else {
node = node->RightChild;
}
}
}
node->Number++;
}
template <typename Type>
int BST<Type>::getTurn(Type data) {
int turn = 0;
struct Node* node = root;
while (!(node == NULL) && !(node->Value == data)) {
if (node->Value > data) {
node = node->LeftChild;
} else {
turn += node->LeftNumber;
turn += node->Number;
node = node->RightChild;
}
}
if (node == NULL) {
return 0;
} else {
return turn + node->LeftNumber + 1;
}
}
template <typename Type>
Type BST<Type>::getValue(int turn) {
struct Node* node = root;
while (1) {
if (turn <= node->LeftNumber) {
node = node->LeftChild;
} else if (node->LeftNumber < turn && turn <= node->LeftNumber + node->Number) {
return node->Value;
} else {
turn -= node->LeftNumber;
turn -= node->Number;
node = node->RightChild;
}
}
}
template <typename Type>
Type BST<Type>::getFront(Type data) {
struct Node* node = root;
Type parentValue = -1 * DefaultValue;
while (node != NULL && !(node->Value == data)) {
if (data < node->Value) {
node = node->LeftChild;
} else {
parentValue = node->Value;
node = node->RightChild;
}
}
if (node == NULL) {
return -1 * DefaultValue;
} else if (node->LeftChild == NULL) {
return parentValue;
} else {
return node->LeftChild->Value;
}
}
template <typename Type>
Type BST<Type>::getBack(Type data) {
struct Node* node = root;
Type parentValue = DefaultValue;
while (!(node->Value == data) && node != NULL) {
if (data < node->Value) {
parentValue = node->Value;
node = node->LeftChild;
} else {
node = node->RightChild;
}
}
if (node == NULL) {
return DefaultValue;
} else if (node->RightChild == NULL) {
return parentValue;
} else {
return node->RightChild->Value;
}
}
int main(void) {
BST<int> bst(2147483647);
int q, t, x;
cin >> q;
while (q--) {
cin >> t >> x;
switch (t) {
case 1:
cout << bst.getTurn(x) << endl;
break;
case 2:
cout << bst.getValue(x) << endl;
break;
case 3:
cout << bst.getFront(x) << endl;
break;
case 4:
cout << bst.getBack(x) << endl;
break;
case 5:
bst.insert(x);
break;
}
}
bst.~BST();
return 0;
}