1. a binary search tree in c++ using a generic approach with both BFS and DFS approach
working tree
https://www.onlinegdb.com/edit/HkuQLdA-w
code=>
some properties of binary search tree->
1. binary search tree is not always a balanced tree.
2. Inorder, traversing gives you sorted data.
3. best is o(log n) and worst is O(n).
4. left node data is always less than root data and right node data always be greater than root data.
5. red-black tree STL map is a balanced binary search tree.
*******************************************************************************/
#include <stdio.h>
#include<iostream>
#include<queue>
using namespace std;
template < typename T > class Node
{
//can store any type of data
private:
//genric data or store any type of data
T data;
//reference of left pointer
Node *left = nullptr;
//reference of right pointer
Node *right = nullptr;
public:
Node ()
{
};
~Node ()
{
};
//set data
Node (T _data)
{
data = _data;
}
//all setter and getter
void setLeftNode (Node * _left)
{
left = _left;
}
void setRightNode (Node * _right)
{
right = _right;
}
Node < T > *getLeftNode ()
{
return left;
}
Node < T > *getRightNode ()
{
return right;
}
T getData ()
{
return data;
}
void setData (T _data)
{
data = _data;
}
};
template < typename T > class BTree
{
private:
Node < T > *root = nullptr;
public:
BTree ()
{
};
~BTree ()
{
};
void append (T data)
{
Node < T > *node = new Node < T > (data);
//if no root for Tree
if (root == nullptr)
{
root = node;
node->setLeftNode (nullptr);
node->setRightNode (nullptr);
}
else
{
appendChild (root, data);
}
}
void appendChild (Node < T > *root, T data)
{
if (data < root->getData ())
{
//if no left child
if (root->getLeftNode () == nullptr)
{
Node < T > *node = new Node < T > (data);
root->setLeftNode (node);
}
else
{
appendChild (root->getLeftNode (), data);
}
}
else if (data > root->getData ())
{
if (root->getRightNode () == nullptr)
{
Node < T > *node = new Node < T > (data);
root->setRightNode (node);
}
else
{
appendChild (root->getRightNode (), data);
}
}
}
Node < T > *getRootNode ()
{
if (root == nullptr)
{
std::cout << "Invisible Tree :)" << std::endl;
}
return root;
}
//Tree Traversals (Inorder, Preorder and Postorder) DFS
//root left right
void Preorder (Node < T > *node)
{
if (node != nullptr)
{
std::cout << node->getData () << endl;
Preorder (node->getLeftNode ());
Preorder (node->getRightNode ());
}
}
//left root right
//point to remember Inorder sorted data would be printed
void Inorder (Node < T > *node)
{
if (node != nullptr)
{
Inorder (node->getLeftNode ());
std::cout << node->getData () << endl;
Inorder (node->getRightNode ());
}
}
//right left root
void Postorder (Node < T > *node)
{
if (node != nullptr)
{
Postorder (node->getRightNode ());
Postorder (node->getLeftNode ());
std::cout << node->getData () << endl;
}
}
//Tree Traversals level order of BFS queue based approach ;
void levelOrder (Node < T > *node)
{
if (node == nullptr)
{
std::cout << "Invisible Tree :)" << std::endl;
return;
}
queue < Node < T > *>Queue;
Queue.push (node);
while (!Queue.empty ())
{
Node < T > *node = Queue.front ();
std::cout << node->getData () << endl;
Queue.pop ();
if (node->getLeftNode () != nullptr)
{
Queue.push (node->getLeftNode ());
}
if (node->getRightNode () != nullptr)
{
Queue.push (node->getRightNode ());
}
}
}
};
int
main ()
{
//with int data
BTree < int >*tree = new BTree < int >();
tree->append (22);
tree->append (11);
tree->append (32);
tree->append (62);
tree->append (82);
tree->levelOrder (tree->getRootNode ());
//with string data is printed in string
cout << "----------------------------" << endl; //look i used inorder data is printed in sorted maanner
BTree < string > *treestr = new BTree < string > ();
treestr->append ("zupan");
treestr->append ("manish");
treestr->append ("ranjeet");
treestr->append ("deepak");
treestr->append ("anu");
treestr->append ("seema");
treestr->Inorder (treestr->getRootNode ());
return 0;
}
Comments
Post a Comment