JellyKuo

DS_Homework_2_1

Nov 29th, 2020
373
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <sstream>
  3. #include <string>
  4. #include <tuple>
  5. #include <vector>
  6. #include <cmath>
  7.  
  8. using namespace std;
  9.  
  10. struct Node
  11. {
  12.     Node(const int& value) {
  13.         this->value = value;
  14.         this->leftChild = nullptr;
  15.         this->rightChild = nullptr;
  16.     };
  17.  
  18.     Node() {
  19.         this->value = -1;
  20.         this->leftChild = nullptr;
  21.         this->rightChild = nullptr;
  22.     };
  23.  
  24.     int value;
  25.     Node* leftChild;
  26.     Node* rightChild;
  27. };
  28.  
  29. void insert(Node* node, const int& value);
  30. void remove(Node* node, Node* parent);
  31. tuple<Node*, Node*> find(Node* node, Node* parent, const int& value);
  32. tuple<Node*, Node*> findMax(Node* node, Node* parent);
  33. void postOrder(Node* node, vector<int>& result);
  34. void inOrder(Node* node, vector<int>& result, const int& maxDepth = 100000000, const int& currentDepth = 0);
  35. void preOrder(Node* node, vector<int>& result);
  36. void printResult(const vector<int>& result);
  37.  
  38. int main() {
  39.     string inputLine;
  40.     getline(cin, inputLine);
  41.     stringstream inputBuffer = stringstream(inputLine);
  42.     int valueBuffer = -1;
  43.  
  44.     Node* tree = new Node();
  45.     inputBuffer >> tree->value;
  46.  
  47.     int nodeCount = 1;
  48.     while (inputBuffer >> valueBuffer) {
  49.         insert(tree, valueBuffer);
  50.         nodeCount++;
  51.     }
  52.  
  53.     getline(cin, inputLine);
  54.     inputBuffer = stringstream(inputLine);
  55.  
  56.     vector<int> result = vector<int>();
  57.     postOrder(tree, result);
  58.     printResult(result);
  59.     cout << "\n";
  60.     result.clear();
  61.  
  62.  
  63.     while (inputBuffer >> valueBuffer) {
  64.         tuple<Node*, Node*> deletingNode = find(tree, nullptr, valueBuffer);
  65.         remove(get<0>(deletingNode), get<1>(deletingNode));
  66.         nodeCount--;
  67.     }
  68.  
  69.     int targetNodeCount = nodeCount / 2;
  70.     int level = 0;
  71.     int levelNodeCount = 1;
  72.     vector<Node*> levelNodes = vector<Node*>();
  73.     levelNodes.push_back(tree);
  74.     while (true)
  75.     {
  76.         vector<Node*> newLevelNodes = vector<Node*>();
  77.         int newLevelNodeCount = levelNodeCount;
  78.         for (int i = 0; i < levelNodes.size(); i++) {
  79.             if (levelNodes[i]->leftChild != nullptr) {
  80.                 newLevelNodes.push_back(levelNodes[i]->leftChild);
  81.                 newLevelNodeCount++;
  82.             }
  83.             if (levelNodes[i]->rightChild != nullptr) {
  84.                 newLevelNodes.push_back(levelNodes[i]->rightChild);
  85.                 newLevelNodeCount++;
  86.             }
  87.         }
  88.  
  89.         if (abs(targetNodeCount - levelNodeCount) < abs(targetNodeCount - newLevelNodeCount)) {
  90.             levelNodes = newLevelNodes;
  91.             levelNodeCount = newLevelNodeCount;
  92.             break;
  93.         }
  94.  
  95.         levelNodes = newLevelNodes;
  96.         levelNodeCount = newLevelNodeCount;
  97.  
  98.         level++;
  99.     }
  100.  
  101.     inOrder(tree, result, level);
  102.     printResult(result);
  103.     cout << "\n";
  104.     result.clear();
  105.  
  106.     for (int i = 0; i < levelNodes.size(); i++) {
  107.         preOrder(levelNodes[i], result);
  108.     }
  109.     printResult(result);
  110.  
  111.     return 0;
  112. }
  113.  
  114. /// <summary>
  115. /// Insert a node recursively into the binary search tree
  116. /// </summary>
  117. /// <param name="node">The current node, when starting it should be the root node</param>
  118. /// <param name="value">The value to insert</param>
  119. void insert(Node* node, const int& value) {
  120.     if (value < node->value) {
  121.         if (node->leftChild == nullptr) {
  122.             node->leftChild = new Node(value);
  123.         }
  124.         else {
  125.             insert(node->leftChild, value);
  126.         }
  127.     }
  128.     else if (value > node->value) {
  129.         if (node->rightChild == nullptr) {
  130.             node->rightChild = new Node(value);
  131.         }
  132.         else {
  133.             insert(node->rightChild, value);
  134.         }
  135.     }
  136. }
  137.  
  138. void remove(Node* node, Node* parent) {
  139.     if (node->leftChild == nullptr && node->rightChild == nullptr) {
  140.         if (parent->leftChild == node) {
  141.             parent->leftChild = nullptr;
  142.         }
  143.         else {
  144.             parent->rightChild = nullptr;
  145.         }
  146.         delete node;
  147.     }
  148.     else if (node->leftChild != nullptr && node->rightChild != nullptr) {
  149.         tuple<Node*, Node*> maxNode = findMax(node->leftChild, node);
  150.         node->value = get<0>(maxNode)->value;
  151.         remove(get<0>(maxNode), get<1>(maxNode));
  152.     }
  153.     else {
  154.         Node* childNode = node->leftChild != nullptr ? node->leftChild : node->rightChild;
  155.         node->value = childNode->value;
  156.         node->leftChild = childNode->leftChild;
  157.         node->rightChild = childNode->rightChild;
  158.         delete childNode;
  159.     }
  160. }
  161.  
  162. /// <summary>
  163. /// Find a node with a given value in a BST
  164. /// </summary>
  165. /// <param name="node">The current node, when starting it should be the root node</param>
  166. /// <param name="value">The value to find</param>
  167. /// <returns></returns>
  168. tuple<Node*, Node*> find(Node* node, Node* parent, const int& value) {
  169.     if (value < node->value) {
  170.         return find(node->leftChild, node, value);
  171.     }
  172.     else if (value > node->value) {
  173.         return find(node->rightChild, node, value);
  174.     }
  175.     else {
  176.         return make_tuple(node, parent);
  177.     }
  178. }
  179.  
  180. tuple<Node*, Node*> findMax(Node* node, Node* parent) {
  181.     if (node->rightChild == nullptr) {
  182.         return make_tuple(node, parent);
  183.     }
  184.     else {
  185.         return findMax(node->rightChild, node);
  186.     }
  187. }
  188.  
  189. void postOrder(Node* node, vector<int>& result) {
  190.     if (node->leftChild != nullptr) {
  191.         postOrder(node->leftChild, result);
  192.     }
  193.     if (node->rightChild != nullptr) {
  194.         postOrder(node->rightChild, result);
  195.     }
  196.     result.push_back(node->value);
  197. }
  198.  
  199. void inOrder(Node* node, vector<int>& result, const int& maxDepth, const int& currentDepth) {
  200.     if (currentDepth > maxDepth) {
  201.         return;
  202.     }
  203.     if (node->leftChild != nullptr) {
  204.         inOrder(node->leftChild, result, maxDepth, currentDepth + 1);
  205.     }
  206.     result.push_back(node->value);
  207.     if (node->rightChild != nullptr) {
  208.         inOrder(node->rightChild, result, maxDepth, currentDepth + 1);
  209.     }
  210. }
  211.  
  212. void preOrder(Node* node, vector<int>& result) {
  213.     result.push_back(node->value);
  214.     if (node->leftChild != nullptr) {
  215.         preOrder(node->leftChild, result);
  216.     }
  217.     if (node->rightChild != nullptr) {
  218.         preOrder(node->rightChild, result);
  219.     }
  220. }
  221.  
  222. void printResult(const vector<int>& result) {
  223.     for (int i = 0; i < result.size() - 1; i++) {
  224.         cout << result[i] << " ";
  225.     }
  226.     cout << *(result.end() - 1);
  227. }
RAW Paste Data