SHARE
TWEET

LibraryBst

michalkowalczyk Mar 21st, 2019 45 in 152 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<memory>
  3. #include<sstream>
  4.  
  5. namespace bst {
  6.  
  7. struct node{
  8.         int value;
  9.  
  10.         std::unique_ptr<node> left_child;
  11.         std::unique_ptr<node> right_child;
  12.  
  13.  
  14.     };
  15.  
  16.  
  17.  
  18. std::unique_ptr<node> CreateLeaf(int val){
  19.  
  20.     std::unique_ptr<node> new_node = std::make_unique<node>();
  21.     new_node->value=val;
  22.  
  23.  
  24.  
  25.  
  26.  
  27.     return new_node;
  28. }
  29.  
  30. void PrintTreeInOrder(const std::unique_ptr<node> &root)
  31. {
  32.     if(root->left_child !=nullptr)
  33.         PrintTreeInOrder(root->left_child);
  34.  
  35.     std::cout<< root->value<< "\t";
  36.  
  37.     if(root->right_child !=nullptr)
  38.         PrintTreeInOrder(root->right_child);
  39.  
  40.  
  41.  
  42.  
  43.  
  44.     return;
  45. }
  46.  
  47. void PrintTreePreOrder(const std::unique_ptr<node> &root){
  48.  
  49.     std::cout<< root->value<< "\t";
  50.  
  51.     if(root->left_child !=nullptr)
  52.         PrintTreePreOrder(root->left_child);
  53.  
  54.  
  55.     if(root->right_child !=nullptr)
  56.         PrintTreePreOrder(root->right_child);
  57.  
  58.  
  59.  
  60.  
  61.  
  62. }
  63.  
  64. void PrintTreePostOrder(const std::unique_ptr<node> &root){
  65.  
  66.  
  67.  
  68.     if(root->left_child !=nullptr)
  69.         PrintTreePostOrder(root->left_child);
  70.  
  71.  
  72.     if(root->right_child !=nullptr)
  73.         PrintTreePostOrder(root->right_child);
  74.  
  75.     std::cout<< root->value<< "\t";
  76.  
  77. }
  78.  
  79. std::unique_ptr<node> InsertNode(std::unique_ptr<node> root,int val){
  80.  
  81.     std::unique_ptr<node> new_node = CreateLeaf(val);
  82.  
  83.     if(root==nullptr){
  84.         root=move(new_node);
  85.  
  86.     }
  87.  
  88.     else {
  89.  
  90.  
  91.  
  92.         if(root->value <= val){
  93.  
  94.             root->right_child = InsertNode(std::move(root->right_child),val);
  95.  
  96.  
  97.         }
  98.         else {
  99.  
  100.             root->left_child = InsertNode(std::move(root->left_child),val);
  101.  
  102.  
  103.         }
  104.  
  105.  
  106.  
  107.     }
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.     return root;
  115.  
  116. }
  117.  
  118. std::string DumpTree(const std::unique_ptr<node> &root)
  119. {
  120.     std:: stringstream ss_tree;
  121.  
  122.  
  123.     if(root==nullptr)
  124.         return  "";
  125.  
  126.     ss_tree<<root->value;
  127.  
  128.  
  129.     if(root->left_child==nullptr && root->right_child==nullptr)
  130.         return ss_tree.str();
  131.  
  132.  
  133.     if(root->left_child !=nullptr){
  134.         ss_tree<<'(';
  135.         ss_tree<<DumpTree(root->left_child);
  136.         ss_tree<<')';
  137.         }
  138.  
  139.     if(root->right_child !=nullptr){
  140.         ss_tree<<'(';
  141.         ss_tree<<DumpTree(root->right_child);
  142.         ss_tree<<')';
  143.     }
  144.  
  145.  
  146.  
  147.  
  148.     return ss_tree.str();
  149. }
  150.  
  151. std::unique_ptr<node> RestoreTree(const std::string &destroyed_tree){
  152.     std::unique_ptr<node> renew_tree;
  153.     int i =0;
  154.     std::string str_node;
  155.  
  156.  
  157.  
  158.     while(destroyed_tree[i]!='\0'){
  159.         //std::cout<<destroyed_tree[i];
  160.         if(destroyed_tree[i]>=48 && destroyed_tree[i]<=57)
  161.             str_node.push_back(destroyed_tree[i]);
  162.  
  163.         if(destroyed_tree[i]=='('  || i==destroyed_tree.size()-1){
  164.             std:: stringstream new_leaf(str_node);
  165.             int leaf;
  166.             new_leaf>>leaf;
  167.             renew_tree = InsertNode(std::move(renew_tree),leaf);
  168.             str_node.clear();
  169.  
  170.  
  171.         }
  172.  
  173.         i++;
  174.  
  175.  
  176.  
  177.     }
  178.  
  179.    /* //Renewing the last leaf in tree
  180.     std:: stringstream new_leaf(str_node);
  181.     int leaf;
  182.     new_leaf>>leaf;
  183.     renew_tree = InsertNode(std::move(renew_tree),leaf);
  184.     str_node.clear();*/
  185.  
  186.  
  187.     return renew_tree;
  188. }
  189.  
  190. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top