Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- template <typename K, typename T>
- struct node {
- K key;
- T data;
- node<K, T>* left;
- node<K, T>* right;
- node(): left(nullptr), right(nullptr) {}
- };
- template <typename K, typename T>
- node<K, T>* add_node(node<K, T>* root, const K& key, const T& value) {
- if (root == nullptr) {
- node<K, T> *new_node = new node<K, T>();
- new_node->key = key;
- new_node->data = value;
- return new_node;
- }
- if (key < root->key) {
- root->left = add_node(root->left, key, value);
- }
- else if (key > root->key) {
- root->right = add_node(root->right, key, value);
- }
- // if keys are equal do nothing
- return root;
- }
- using key_t = int;
- using value_t = std::vector<int>;
- template <typename K, typename T>
- void show(const node<K, T>* root) {}
- template <>
- void show(const node<key_t, value_t>* root) {
- if (root == nullptr) {
- return;
- }
- show(root->left);
- show(root->right);
- cout << "key: " << root->key << "; value: ";
- for (auto k: root->data) {
- cout << k << " ";
- }
- cout << endl;
- }
- template <typename K, typename T>
- node<K, T>* get_min(node<K, T>* root) {
- node<K, T> *current = root;
- while (current->left != nullptr) {
- current = current->left;
- }
- return current;
- }
- template <typename K, typename T>
- node<K, T>* remove_node(node<K, T>* root, const K& key) {
- if (root == nullptr) {
- return root;
- }
- if (key < root->key) {
- root->left = remove_node(root->left, key);
- }
- else if(key > root->key) {
- root->right = remove_node(root->right, key);
- }
- else {
- if (root->left == nullptr) {
- node<K, T>* temp = root->right;
- delete root;
- return temp;
- }
- else if (root->right == nullptr) {
- node<K, T>* temp = root->left;
- delete root;
- return temp;
- }
- node<K, T>* temp = get_min(root->right);
- root->key = temp->key;
- root->data = temp->data;
- root->right = remove_node(root->right, temp->key);
- }
- return root;
- }
- template <typename K, typename T>
- void find_max(node<K, T>* root, K& key_max) {
- if (root == nullptr) {
- return;
- }
- static int acc = 0;
- static int max = 0;
- find_max(root->left, key_max);
- find_max(root->right, key_max);
- for_each(root->data.begin(), root->data.end(), [](int k) {
- acc += k;
- });
- if (acc > max) {
- max = acc;
- key_max = root->key;
- }
- acc = 0;
- }
- int main() {
- node<key_t, value_t> *tree = nullptr;
- tree = add_node(tree, 5, {1, 2, 3, 4});
- tree = add_node(tree, 10, {4, 4, 5, 6});
- tree = add_node(tree, 7, {3, 4});
- tree = add_node(tree, 20, {1, 1, 2, 3});
- tree = add_node(tree, 1, {0, 3, 1, 2});
- show(tree);
- int key_max = 0;
- find_max(tree, key_max);
- cout << "key: " << key_max << endl;
- remove_node(tree, key_max);
- cout << "Tree after removing key\n";
- show(tree);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement