c++ code for Binary search Tree in a Generic Way copy and paste the code in editor (c++) run
#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;
}
#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