I am here trying to implement BST using smart pointers and template. For implementation of BST, I will be creating following classes.
1. BinTreeNode
2. BinTree
Also, In order to test I will be writing simple unit test file (source.cpp)
1. BinTreeNode.h
2. BinTree
3. Source.cpp
1. BinTreeNode
2. BinTree
Also, In order to test I will be writing simple unit test file (source.cpp)
1. BinTreeNode.h
#pragma once
#include <memory>
#include <iostream>
#include <string>
template <class T>
class BinTreeNode;
template <class T>
std::ostream& operator<<(std::ostream& out, const BinTreeNode<T>& binNode);
template <class T>
class BinTreeNode {
public:
T m_data;
std::shared_ptr<BinTreeNode> m_spleftNode, m_sprightNode;
std::weak_ptr<BinTreeNode> m_wpparentNode;
BinTreeNode(T data) :m_data(data), m_spleftNode(nullptr), m_sprightNode(nullptr) {}
~BinTreeNode() {}
bool operator==(const BinTreeNode<T>& binNode) {
if (m_data == binNode.m_data)
return true;
return false;
}
bool insertNode(std::shared_ptr<BinTreeNode<T>> binNode) {
if (binNode->m_data > m_data) {
if (m_sprightNode == nullptr)
m_sprightNode = binNode;
else
m_sprightNode->insertNode(binNode);
}
else if (binNode->m_data == m_data) {
std::cout << "Data already present!!\n";
return false;
}
else {
if (m_spleftNode == nullptr)
m_spleftNode = binNode;
else
m_spleftNode->insertNode(binNode);
}
return true;
}
friend std::ostream& operator<< <>(std::ostream& out, const BinTreeNode<T>& binNode);
};
template <class T>
std::ostream& operator<<(std::ostream& out, const BinTreeNode<T>& binNode) {
if (binNode.m_spleftNode != nullptr)
out << "[Left: " << *(binNode.m_spleftNode) << " ] ";
out << "(" << binNode.m_data << ")";
if (binNode.m_sprightNode != nullptr)
out << " [Right: " << *(binNode.m_sprightNode) << " ]";
return out;
}
2. BinTree
#pragma once
#include <iostream>
#include <memory>
#include "BinTreeNode.h"
template <typename T>
class BinTree;
template <typename T>
std::ostream& operator<<(std::ostream& out, const BinTree<T>& binTree);
template <typename T>
class BinTree {
public:
std::shared_ptr<BinTreeNode<T> > m_sproot;
BinTree() {}
~BinTree() {}
bool insertdata(T data) {
std::shared_ptr<BinTreeNode<T>> spbinNode(new BinTreeNode<T>(data));
if (m_sproot == nullptr) {
m_sproot = spbinNode;
return true;
}
std::shared_ptr<BinTreeNode<T>> binNode(new BinTreeNode<T>(data));
return m_sproot->insertNode(binNode);
}
friend std::ostream& operator<< <>(std::ostream& out, const BinTree<T>& binTree);
};
template <typename T>
std::ostream& operator<<(std::ostream& out, const BinTree<T>& binTree) {
out << *(binTree.m_sproot);
return out;
}
3. Source.cpp
#include <iostream>
#include <string>
#include "BinTreeNode.h"
#include "BinTree.h"
int main() {
BinTree<std::string> bintree;
bintree.insertdata(std::string("text"));
bintree.insertdata(std::string("binary"));
bintree.insertdata(std::string("search"));
bintree.insertdata(std::string("tree"));
bintree.insertdata(std::string("implementation"));
std::cout << bintree;
getchar();
}