binary tree

an implementation of binary trees in c++. this includes a way of printing the tree and adding elements to a sorted type of tree. Additionally, it can also balance an unbalanced tree

how to compile?

this project uses the meson buildsystem for compiling commands for compilation (in root directory of project):

• meson setup <build_directory_name>
• cd <build_directory_name> && meson compile
• ./binary_tree

explenation

i have implemented a binary-tree by creating a tempalted class binary_node, which has, among simple getters, setters, constructors and destructors, also the following methods with fitting explentations:

• sorted_insert(T value) inserts a value into the binary tree, assuming that the lefter nodes get smaller and the righter ones get bigger. it works by simply binary-searching until finding either itself, and doing nothing, or inserting itself at the correct place.
• balanced_insert(T value) inserts a value by calling the sorted_insert(T value) function, and then ballances it out by first using the to_array() function to convert to a sorted array, and then calls the balance function to balance out the tree.
• balance(std::vector sorted_values, binary_node* top_node) this function balances the tree, by first find the median, setting it as the top node, and then recursively calling itself with the left-sided and right-sided "halfs" of the inputet array of sorted values.
• to_array() uses a depth-first treversal algorithm to go through the array and save all values (which will be sorted if the values were always inserted with the isorted_insert or balanced_insert functions) into an array. it then returns that very array. and to add onto that, some simple printing functions, to be able to display/print a tree.

final notes:

• i could have improved the class by not using a type, but references and pointers everywhere, but i didn't bother since it's just here to demonstrate the algorithms and functionality
• i could have embeded the print functions into the binary_node class itself, but this would build on the support of the std, to print this very type, which was a little uncomfortable.
• this was fun ^o^

licence

this project is released under the gnu affero general public license