JustAnotherCatgirl

Treez nutz

Apr 25th, 2023 (edited)
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.40 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <stack>
  5. #define _STACK_
  6. // https://github.com/justanothercatgirl/Treez_nuts_2
  7. template <typename T>
  8. struct TreeNode
  9. {
  10.     TreeNode<T>* left;
  11.     TreeNode<T>* right;
  12.     T value;
  13.    
  14.     TreeNode(T n_value = 0, TreeNode<T>* n_left = nullptr, TreeNode<T> *n_right = nullptr)
  15.     : left{n_left}, right{n_right}, value{n_value} {}
  16.    
  17.     ~TreeNode()
  18.     {
  19.         delete left;
  20.         delete right;
  21.     }
  22.    
  23.     inline bool one_free_leaf()
  24.     {
  25.         return static_cast<bool>(left) != static_cast<bool>(right);
  26.     }
  27.    
  28. };
  29.  
  30. template <typename T>
  31. class Tree
  32. {
  33. public:
  34.    
  35.     TreeNode<T>* root;
  36.      
  37.     Tree(TreeNode<T> *node = nullptr): root{node}
  38.     {}
  39.    
  40.     template <typename lambda>
  41.     TreeNode<T>* BFS(lambda criteria)
  42.     {
  43.         if(!root) return nullptr; //nullptrs should never be in the queue
  44.        
  45.         std::queue<TreeNode<T>*> q;
  46.         q.push(root);
  47.        
  48.         while(!q.empty())
  49.         {
  50.             TreeNode<T>* current_node = q.front();
  51.             q.pop();
  52.            
  53.             if (criteria(current_node))
  54.                 return current_node;
  55.                
  56.             if(current_node->left)
  57.                 q.push(current_node->left);
  58.             if(current_node->right)
  59.                 q.push(current_node->right);
  60.         }
  61.         return nullptr;
  62.     }
  63.    
  64.     void insert_node(TreeNode<T>* node)
  65.     {
  66.         TreeNode<T> *target = BFS(           \
  67.         [](TreeNode<T> *n) -> bool           \
  68.         {return !(n->left && n->right);} );  
  69.        
  70.         if(!target) {root = node; return;}
  71.        
  72.         if(!target->left) {target->left = node; return;}
  73.         if(!target->right) {target->right = node; return;}
  74.     }
  75.    
  76.     void insert_value(T val)
  77.     {
  78.         insert_node(new TreeNode<T>(val));
  79.     }
  80.    
  81. };
  82.  
  83. template <typename T>
  84. Tree<T> construct(std::vector<T> &arr)
  85. {
  86.     Tree<T> ret;
  87.     for (T x: arr)
  88.     {
  89.         ret.insert_value(x);
  90.     }
  91.        
  92.     return ret;
  93. }
  94.  
  95. int main()
  96. {
  97.     #ifdef _STACK_
  98.         std::stack
  99.     #else
  100.         std::queue
  101.     #endif
  102.     <TreeNode<int>*> q_s;
  103.    
  104.     std::vector<int> vect{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
  105.     Tree<int> t = construct(vect);
  106.    
  107.     q_s.push(t.root);
  108.    
  109.     while(!q_s.empty())
  110.     {
  111.         std::cout << '\n';
  112.        
  113.         TreeNode<int> *n =
  114.         #ifdef _STACK_
  115.             q_s.top();
  116.         #else
  117.             q_s.front();
  118.         #endif
  119.        
  120.         q_s.pop();
  121.        
  122.         if(n) std::cout << n->value << ' ';
  123.        
  124.         if(n->right) q_s.push(n->right);
  125.         if(n->left) q_s.push(n->left);
  126.        
  127.     }
  128.    
  129. }
Advertisement
Add Comment
Please, Sign In to add comment