Skip to content

Instantly share code, notes, and snippets.

@Adanos020
Created May 8, 2018 12:22
Show Gist options
  • Save Adanos020/cf533b7e5b480c7a1a7a1a675439234d to your computer and use it in GitHub Desktop.
Save Adanos020/cf533b7e5b480c7a1a7a1a675439234d to your computer and use it in GitHub Desktop.
#pragma once
#include <string>
#include <vector>
#include "templates.hpp"
// These are used only for printing the tree.
#define SPACE_MIDSTICK std::string(u8" \u251c")
#define BAR_MIDSTICK std::string(u8"\u2502 \u251c")
#define BOTSTICK std::string(u8"\u2570")
/** Wrapper class facilitating the use of the binary search tree.
*/
generic(T) class BinaryTree
{
private: // Types.
/** Representation of a single node of a binary tree.
*/
struct Node
{
T data; ///< Payload.
Node* left; ///< Left branch.
Node* right; ///< Right branch.
};
private: // Fields.
Node* root; ///< First node of the tree.
size_t elements_count;
public: // Methods.
/** Default constructor.
*/
BinaryTree()
: root(NULL)
, elements_count(0)
{
}
~BinaryTree()
{
clear();
}
/** Adds a new entry to the tree. Duplicates are ignored.
*
* Params: data = Value of the new entry.
*/
void add(T data)
{
add(this->root, data);
}
/** Deletes all entries from the tree.
*/
void clear()
{
clear(this->root);
elements_count = 0;
}
/** Deletes the entry of given value from the tree. If
* the value is not found, no error is signalised.
*
* Params: data = Value to delete.
*/
void remove(T data)
{
remove(this->root, data);
}
/** Prints the tree in pseudographical representation.
*/
void print()
{
print(this->root);
}
/** Returns the number of entries in the tree.
*
* Returns: Number of entries in the tree.
*/
size_t size() const
{
return elements_count;
}
/** Performs a prefix traverse on the tree.
*
* Returns: Array of all elements in prefix traverse
* order.
*/
std::vector<T> prefix()
{
return prefix(this->root);
}
/** Performs a infix traverse on the tree.
*
* Returns: Array of all elements in infix traverse
* order.
*/
std::vector<T> infix()
{
return infix(this->root);
}
/** Performs a postfix traverse on the tree.
*
* Returns: Array of all elements in postfix traverse
* order.
*/
std::vector<T> postfix()
{
return postfix(this->root);
}
/** Generates a string representation of the tree.
*
* Returns: String representation of the tree.
*/
std::string to_string()
{
return to_string(this->root);
}
private: // Full implementations of methods above.
void add(Node*& root, T data)
{
if (!root) // Empty: creating a new tree.
{
root = new Node;
root->data = data;
++elements_count;
}
else if (data != root->data) // Not empty: adding to appropriate subtree.
{ // Ignoring if new data is already in the tree.
add(data < root->data ? root->left : root->right, data);
}
}
void clear(Node*& root)
{
if (!root) return; // Don't delete empty trees.
// Clearing all subrees.
clear(root->left);
clear(root->right);
delete root;
root = NULL; // Invalidating the root.
}
void remove(Node*& root, T data)
{
if (!root) return; // Don't delete from empty trees.
// Value not found here: look in appropriate subtree.
/**/ if (data < root->data) { remove(root->left, data); }
else if (data > root->data) { remove(root->right, data); return; }
// Value found here.
if (!root->left && !root->right) // Leaf: just remove and invalidate it.
{
delete root;
root = NULL;
}
else if (!root->left && root->right) // Has one child: replace it with the child.
{
Node* right = root->right;
delete root;
root = right;
}
else if (root->left && !root->right) // ditto
{
Node* left = root->left;
delete root;
root = left;
}
else // Has two children: replace it with the leftmost leaf of the right child.
{
Node* temp = root;
Node* parent = root;
Node* child = root->right;
while (child->left)
{
parent = child;
child = child->left;
}
delete root;
if (root == parent) // Right child is a leaf.
{
root = child;
root->left = temp->left;
}
else // Right child is a tree.
{
parent->left = child->right;
root = child;
child->right = temp->right;
child->left = temp->left;
}
}
--elements_count;
}
void print(Node*& root, std::string pre = "\u2500", bool left = true)
{
// If not null:
//> {pre}[{root->data}]
// Otherwise:
//> {pre}⊗
printf("%s\u2500%s\n", pre.c_str(), root ? ("[" + std::to_string(root->data) + "]").c_str() : u8"\u2297");
if (!root) return;
// Preparing the ornament preceding the value.
std::string prepre = left ? SPACE_MIDSTICK : BAR_MIDSTICK;
pre.replace(pre.size() - BOTSTICK.size(), prepre.size(), prepre);
print(root->right, pre, false);
pre.replace(pre.size() - BOTSTICK.size(), BOTSTICK.size(), BOTSTICK);
print(root->left, pre);
}
std::vector<T> prefix(Node*& root) const
{
std::vector<T> traverse;
if (root)
{
auto left = prefix(root->left);
auto right = prefix(root->right);
traverse.push_back(root->data);
traverse.insert(traverse.end(), left.begin(), left.end());
traverse.insert(traverse.end(), right.begin(), right.end());
}
return traverse;
}
std::vector<T> infix(Node*& root) const
{
std::vector<T> traverse;
if (root)
{
auto left = infix(root->left);
auto right = infix(root->right);
traverse.insert(traverse.end(), left.begin(), left.end());
traverse.push_back(root->data);
traverse.insert(traverse.end(), right.begin(), right.end());
}
return traverse;
}
std::vector<T> postfix(Node*& root) const
{
std::vector<T> traverse;
if (root)
{
auto left = postfix(root->left);
auto right = postfix(root->right);
traverse.insert(traverse.end(), left.begin(), left.end());
traverse.insert(traverse.end(), right.begin(), right.end());
traverse.push_back(root->data);
}
return traverse;
}
std::string to_string(Node*& root)
{
if (!root) return "null";
return std::to_string(root->data) + "("
+ to_string(root->left) + ","
+ to_string(root->right) + ")";
}
};
special void BinaryTree<std::string>::print(Node*& root, std::string pre, bool left)
{
// If not null:
//> {pre}["{root->data}"]
// Otherwise:
//> {pre}⊗
printf("%s\u2500%s\n", pre.c_str(), root ? ("[\"" + root->data + u8"\"]").c_str() : u8"\u2297");
if (!root) return;
// Preparing the ornament preceding the value.
std::string prepre = left ? SPACE_MIDSTICK : BAR_MIDSTICK;
pre.replace(pre.size() - BOTSTICK.size(), prepre.size(), prepre);
print(root->right, pre, false);
pre.replace(pre.size() - BOTSTICK.size(), BOTSTICK.size(), BOTSTICK);
print(root->left, pre);
}
special std::string BinaryTree<std::string>::to_string(Node*& root)
{
if (!root) return "null";
return "\"" + root->data
+ "\"(" + to_string(root->left)
+ "," + to_string(root->right)
+ ")";
}
#undef SPACE_MIDSTICK
#undef BAR_MIDSTICK
#undef BOTSTICK
#pragma once
// Helper macros to extract specific arguments from variadic macros.
// Maximum of 10 arguments is accepted.
#define _0_type(_call, ...)
#define _1_type(_call, x) _call(x)
#define _2_type(_call, x, ...) _call(x), _1_type(_call, __VA_ARGS__)
#define _4_type(_call, x, ...) _call(x), _2_type(_call, __VA_ARGS__)
#define _5_type(_call, x, ...) _call(x), _4_type(_call, __VA_ARGS__)
#define _6_type(_call, x, ...) _call(x), _5_type(_call, __VA_ARGS__)
#define _7_type(_call, x, ...) _call(x), _6_type(_call, __VA_ARGS__)
#define _8_type(_call, x, ...) _call(x), _7_type(_call, __VA_ARGS__)
#define _9_type(_call, x, ...) _call(x), _8_type(_call, __VA_ARGS__)
#define _nth_arg(_1, _2, _3, _4, _5, _6, _7, _8, _9, N, ...) N
#define _for_each(x, ...) _nth_arg("", ##__VA_ARGS__,\
_9_type,\
_2_type,\
_8_type,\
_7_type,\
_6_type,\
_5_type,\
_4_type,\
_1_type,\
_0_type)(x, ##__VA_ARGS__)
#define _declare_template_type(x) typename x
// Macros for templates for generic types.
#define generic(...) template<_for_each(_declare_template_type, ##__VA_ARGS__)>
#define special generic()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment