Skip to content

Instantly share code, notes, and snippets.

@toboqus
Last active October 20, 2023 16:38
Show Gist options
  • Save toboqus/7a7b3d334c9ac59f3d5a to your computer and use it in GitHub Desktop.
Save toboqus/7a7b3d334c9ac59f3d5a to your computer and use it in GitHub Desktop.
BST in C++ with templates
/*
* main.cpp
*
* Created on: 8 Nov 2015
* Author: Alex
*/
#include <iostream>
template <class T>
class BinaryTree
{
struct node{
T value;
struct node* right;
struct node* left;
};
public:
BinaryTree();
~BinaryTree();
void add(T val);
void printPreOrder();
void printInOrder();
void printPostOrder();
int size();
bool lookup(T val);
private:
struct node* root;
int treeSize;
void add(struct node** node, T val);
bool lookup(struct node* node, T val);
void printPreOrder(struct node* node);
void printInOrder(struct node* node);
void printPostOrder(struct node* node);
void deleteTree(struct node* node);
};
template <class T>
BinaryTree<T>::BinaryTree(){
this->root = NULL;
this->treeSize = 0;
}
template <class T>
BinaryTree<T>::~BinaryTree(){
deleteTree(this->root);
}
template <class T>
int BinaryTree<T>::size(){
return this->treeSize;
}
template <class T>
void BinaryTree<T>::add(T val){
add(&(this->root), val);
}
template <class T>
void BinaryTree<T>::add(struct node** node, T val){
if(*node == NULL) {
struct node* tmp = new struct node;
tmp->value = val;
tmp->left=NULL;
tmp->right = NULL;
*node = tmp;
this->treeSize++;
}else{
if(val > (*node)->value){
add(&(*node)->right, val);
}else{
add(&(*node)->left, val);
}
}
}
template <class T>
void BinaryTree<T>::printInOrder(){
printInOrder(this->root);
std::cout << std::endl;
}
template <class T>
void BinaryTree<T>::printInOrder(struct node* node){
if(node != NULL){
printInOrder(node->left);
std::cout << node->value << ", ";
printInOrder(node->right);
}
}
template <class T>
void BinaryTree<T>::printPreOrder(){
printPreOrder(this->root);
std::cout << std::endl;
}
template <class T>
void BinaryTree<T>::printPreOrder(struct node* node){
if(node != NULL) {
std::cout << node->value << ", ";
printInOrder(node->left);
printInOrder(node->right);
}
}
template <class T>
void BinaryTree<T>::printPostOrder(){
printPostOrder(this->root);
std::cout << std::endl;
}
template <class T>
void BinaryTree<T>::printPostOrder(struct node* node){
if(node != NULL){
printInOrder(node->left);
printInOrder(node->right);
std::cout << node->value << ", ";
}
}
template <class T>
void BinaryTree<T>::deleteTree(struct node* node){
if(node != NULL){
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
}
template <class T>
bool BinaryTree<T>::lookup(T val){
return lookup(this->root, val);
}
template <class T>
bool BinaryTree<T>::lookup(struct node* node, T val){
if(node == NULL){
return false;
}else{
if(val == node->value){
return true;
}
if(val > node->value){
return lookup(node->right, val);
}else{
return lookup(node->left, val);
}
}
}
int main(){
BinaryTree<int> tree;
tree.add(5);
tree.add(4);
tree.add(7);
tree.add(10);
tree.add(1);
tree.add(2);
tree.printPostOrder();
tree.printInOrder();
tree.printPreOrder();
std::cout << "Tree size: " << tree.size() << std::endl;
BinaryTree<char> tee;
tee.add('z');
tee.add('0');
tee.add('9');
tee.add('a');
tee.add('A');
tee.add('Z');
std::cout << "Contains 9? : "<< ((tee.lookup('9'))? "true" : "false" ) << std::endl;
tee.printPostOrder();
tee.printInOrder();
tee.printPreOrder();
std::cout << "Tree size: " << tee.size() << std::endl;
}
@vedant-shah
Copy link

Post order doesn't seem to be working correctly

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment