アルゴリズム導論-第12章-二叉探索木:ランダム二叉探索木データ構造C++実現(前中後序遍歴、挿入、探索、前後隣接要素、最大最小値)
5848 ワード
#include
#include
#include
#include
using namespace std;
struct Node {
int key{};
Node* left_son{ nullptr };
Node* right_son{ nullptr };
Node* parent{ nullptr };
};
class BinarySearchTree {
public:
BinarySearchTree(vector v);
~BinarySearchTree() { delete root; };
void insert(int key);
void randomize_built_tree(int[], int[]);
void inorder_tree_walk_recursion(Node* node);
void preorder_tree_walk_recursion(Node* node);
void postorder_tree_walk_recursion(Node* node);
int maximum(Node* _root);
int minimum(Node* _root);
Node* search(Node* _root, int key);
Node* successor(int key);
Node* predecessor(int key);
Node* getRoot() { return root; }
private:
Node* root;
size_t size;
};
BinarySearchTree::BinarySearchTree(vector v) : root{ nullptr }, size{ v.size() } {
int* A = new int[size];
int* select_flag = new int[size] {};
int index{};
for_each(v.begin(), v.end(), [=](int x)mutable{ A[index++] = x; });
randomize_built_tree(A, select_flag);
delete[]A;
delete[]select_flag;
}
void BinarySearchTree::insert(int key) {
if (!root) {
root = new Node;
root->key = key;
return;
}
else {
Node* tmp = nullptr;
Node* tmp_parent = nullptr;
bool is_set_aside_left = false;
tmp = root;
while (tmp) {
if (key <= tmp->key) {
tmp_parent = tmp;
tmp = tmp->left_son;
is_set_aside_left = true;
}
else {
tmp_parent = tmp;
tmp = tmp->right_son;
is_set_aside_left = false;
}
}
if (is_set_aside_left) {
tmp = new Node;
tmp->key = key;
tmp->parent = tmp_parent;
tmp_parent->left_son = tmp;
return;
}
else {
tmp = new Node;
tmp->key = key;
tmp->parent = tmp_parent;
tmp_parent->right_son = tmp;
return;
}
}
}
void BinarySearchTree::randomize_built_tree(int A[], int select_flag[]) {
random_device rd{};
default_random_engine e{ rd() };
uniform_int_distribution u{};
bool flag = false;
while (true) {
size_t index = static_cast(round(round(u(e)))) % size;
for (int i = 0; i < size; ++i) {
if (!select_flag[i]) {
flag = true;
if (i == index) {
select_flag[index] = 1;
insert(A[index]);
break;
}
}
}
if (!flag) {
return;
}
else{
flag = false;
}
}
}
void BinarySearchTree::inorder_tree_walk_recursion(Node* node) {
if (node) {
inorder_tree_walk_recursion(node->left_son);
cout << node->key << " ";
inorder_tree_walk_recursion(node->right_son);
}
}
void BinarySearchTree::preorder_tree_walk_recursion(Node* node) {
if (node) {
cout << node->key << " ";
inorder_tree_walk_recursion(node->left_son);
inorder_tree_walk_recursion(node->right_son);
}
}
void BinarySearchTree::postorder_tree_walk_recursion(Node* node) {
if (node) {
postorder_tree_walk_recursion(node->left_son);
postorder_tree_walk_recursion(node->right_son);
cout << node->key << " ";
}
}
int BinarySearchTree::minimum(Node* _root) {
Node* node = _root;
Node* result = nullptr;
while (node) {
result = node;
node = node->left_son;
}
return result->key;
}
int BinarySearchTree::maximum(Node* _root) {
Node* node = _root;
Node* result = nullptr;
while (node) {
result = node;
node = node->right_son;
}
return result->key;
}
Node* BinarySearchTree::search(Node* _root, int key) {
Node* node = _root;
while (node) {
if (key == node->key) {
return node;
}
else if (key < node->key) {
node = node->left_son;
}
else {
node = node->right_son;
}
}
return node;
}
Node* BinarySearchTree::successor(int key) {
Node* node = search(root, key);
Node* parent = nullptr;
if (!node) {
return nullptr;
}
else {
if (node->right_son) {
search(node->right_son, minimum(node->right_son));
}
else {
parent = node->parent;
while (parent && node == parent->right_son) {
node = parent;
parent = parent->parent;
}
return parent;
}
}
}
Node* BinarySearchTree::predecessor(int key) {
Node* node = search(root, key);
Node* parent = nullptr;
if (!node) {
return nullptr;
}
else {
if (node->left_son) {
search(node->left_son, maximum(node->left_son));
}
else {
parent = node->parent;
while (parent && node == parent->left_son) {
node = parent;
parent = parent->parent;
}
return parent;
}
}
}
int main(int argc, char* argv[]) {
vector v{};
int elememt{};
cout << "please enter the elements :" << endl;
while (cin >> elememt) {
v.push_back(elememt);
}
BinarySearchTree bst{ v };
cout << "bst preorder walk: " << endl;
bst.preorder_tree_walk_recursion(bst.getRoot());
cout << endl;
cout << "bst inorder walk: " << endl;
bst.inorder_tree_walk_recursion(bst.getRoot());
cout << endl;
cout << "bst postorder walk: " << endl;
bst.postorder_tree_walk_recursion(bst.getRoot());
cout << endl;
cin.clear();
cin.ignore(10000, '
');
int key;
cout << "please choose the key you want to find its' predecessor and successor :" << endl;
while (cin >> key) {
Node* pNode = bst.predecessor(key);
Node* sNode = bst.successor(key);
if (!pNode) {
cout << "no predecessor" << endl;
}
else {
cout << "predecessor :" << pNode->key << endl;
}
if (!sNode) {
cout << "no successor" << endl;
}
else {
cout << "successor :" << sNode->key << endl;
}
}
return 0;
}