Skip to content

anonymous / BinaryTreeLinkedList.h secret
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
#pragma once
#include<vector>
#include<queue>
#include<stack>
#include "BinaryTreeADT.h"
using namespace std;
template<typename T>
struct Node
{
Node<T> *left,*right;
T val;
Node(T val):left(NULL),right(NULL),val(val){}
};
template<typename T>
class BinaryTreeLinkedList:BinaryTreeADT<T>
{
Node<T>* root;
void removeNode(Node<T>* &p);
void inorder(Node<T>* r)const;
void preorder(Node<T>* r)const;
void postorder(Node<T>* r)const;
void insertRec(T item,Node<T>*& root);
bool searchRec(T item,Node<T>* root);
Node<T>* findMin(Node<T> *t);
void bstHelper(Node<T>* root,vector<T> &v );
Node<T>* findMax(Node<T> *t);
bool isSorted(const vector<T>& v);
void removeRec(T item,Node<T>*& t);
void copyTree(Node<T>*& copiedTree,Node<T>* othertree);
void destroy(Node<T>*& r);
void destroy();
void linkedListToArray(Node<T>* r,vector<T> &v);
public:
BinaryTreeLinkedList():root(NULL){}
void insert(T item);
void remove(int item);
void search(T toFind);
void insertRec(T item);
void searchRec(T item);
void removeRec(T item);
void inOrder() const;
void preOrder() const;
void postOrder()const;
bool isBst();
void levelOrder();
BinaryTreeLinkedList(const BinaryTreeLinkedList<T>& other);
const BinaryTreeLinkedList& operator=(const BinaryTreeLinkedList<T>& other);
~BinaryTreeLinkedList();
friend bool operator==(BinaryTreeLinkedList<T>& T1,BinaryTreeLinkedList<T>& T2);
vector<T> linkedListToArray();
void arrayToLinkedList();
};
#pragma once
#include<vector>
template<typename T>
class BinaryTreeADT
{
public:
virtual void insert(T item)=0;
virtual void remove(T item)=0;
virtual void search(T item)=0;
virtual void insertRec(T item)=0;
virtual void removeRec(T item)=0;
virtual bool isBst()=0;
virtual void preOrder()const=0;
virtual void postOrder()const=0;
virtual void inOrder()const=0;
virtual void levelOrder()=0;
virtual std::vector<T> linkedListToArray()=0;
virtual void arrayToLinkedList()=0;
};
#include "BinaryTreeLinkedList.h"
template<typename T>
void BinaryTreeLinkedList<T>::removeNode(Node<T>* &p)
{
Node<T> *current,*trailing,*temp;
if(p==NULL) cerr << "Can not remove from empty tree (1)"<<endl;
else if(p->left == NULL && p->right==NULL){
temp = p;
p=NULL;
delete temp;
}
else if(p->left==NULL){
temp = p;
p = p->right;
delete temp;
}
else if(p->right==NULL){
temp = p;
p = p->left;
delete temp;
}
else {
current = p->left;
trailing = NULL;
while (current->right != NULL)
{
trailing=current;
current = current->right;
}
p->val = current->val;
if(trailing==NULL)
p->left = current->left;
else
trailing->right = current->left;
delete current;
}
}
template<typename T>
void BinaryTreeLinkedList<T>::inorder(Node<T>* r)const
{
if(r==NULL) return;
else
{
inorder(r->left);
cout << r->val<<endl;
inorder(r->right);
}
}
template<typename T>
void BinaryTreeLinkedList<T>::preorder(Node<T>* r)const
{
if(r==NULL) return;
else
{
cout << r->val<<endl;
preorder(r->left);
preorder(r->right);
}
}
template<typename T>
void BinaryTreeLinkedList<T>::postorder(Node<T>* r)const
{
if(r==NULL) return;
else
{
postorder(r->left);
postorder(r->right);
cout << r->val<<endl;
}
}
template<typename T>
void BinaryTreeLinkedList<T>::insertRec(T item,Node<T>*& root)
{
if(root==NULL)
root = new Node<T>(item);
else if( item < root->val)
insertRec(item,root->left);
else
insertRec(item,root->right);
}
template<typename T>
bool BinaryTreeLinkedList<T>::searchRec(T item,Node<T>* root)
{
if(root==NULL)
return false;
if(root->val == item)
return true;
else if(item < root->val)
return searchRec(item,root->left);
else
return searchRec(item,root->right);
return false;
}
template<typename T>
Node<T>* BinaryTreeLinkedList<T>::findMin(Node<T> *t)
{
if(t==NULL)
return NULL;
if(t->left==NULL)
return t;
return findMin(t->left);
}
template<typename T>
void BinaryTreeLinkedList<T>::bstHelper(Node<T>* root,vector<T> &v )
{
if(root==NULL)
return;
else
{
bstHelper(root->left,v);
v.push_back(root->val);
bstHelper(root->right,v);
}
}
template<typename T>
Node<T>* BinaryTreeLinkedList<T>::findMax(Node<T> *t)
{
if(t==NULL)
return;
if(t->right==NULL)
return t;
return findMax(t->right);
}
template<typename T>
bool BinaryTreeLinkedList<T>::isSorted(const vector<T>& v)
{
for(unsigned int i=0;i<v.size()-1;i++)
if(v.at(i) <= v.at(i+1))
continue;
else
return false;
return true;
}
template<typename T>
void BinaryTreeLinkedList<T>::removeRec(T item,Node<T>*& t)
{
if(t==NULL)
return;
if(item < t->val)
removeRec(item,t->left);
else if(item > t->val)
removeRec(item,t->right);
else if(t->left!=NULL && t->right!=NULL)
{
t->val = findMin(t->right)->val;
removeRec(t->val,t->right);
}
else
{
Node<T>* old = t;
t = (t->left !=NULL)?t->left:t->right;
delete old;
}
}
template<typename T>
void BinaryTreeLinkedList<T>::copyTree(Node<T>*& copiedTree,Node<T>* othertree)
{
if(othertree==NULL)
copiedTree=NULL;
else
{
copiedTree = new Node<T>(othertree->val);
copyTree(copiedTree->left, othertree->left);
copyTree(copiedTree->right, othertree->right);
}
}
template<typename T>
void BinaryTreeLinkedList<T>::destroy(Node<T>*& r)
{
if(r!=NULL)
{
destroy(r->left);
destroy(r->right);
delete r;
r=NULL;
}
}
template<typename T>
void BinaryTreeLinkedList<T>::destroy()
{
destroy(root);
}
template<typename T>
void BinaryTreeLinkedList<T>::linkedListToArray(Node<T>* r,vector<T> &v)
{
if(!r)
return;
queue<Node<T>* > q;
q.push(root);
while(!q.empty())
{
Node<T>* temp = q.front();
q.pop();
v.push_back(temp->val);
if(temp->left!=NULL)
q.push(temp->left);
if(temp->right!=NULL)
q.push(temp->right);
}
}
template<typename T>
void BinaryTreeLinkedList<T>::insert(T item)
{
Node<T>* current;
Node<T>* trailing;
Node<T>* data = new Node<T>(item);
if(root==NULL)
root = data;
else
{
current = root;
while (current!=NULL)
{
trailing=current;
if(item < current->val)
{
current = current->left;
}
else
{
current = current->right;
}
}
if(item < trailing->val)
trailing->left = data;
else
trailing->right = data;
}
}
template<typename T>
void BinaryTreeLinkedList<T>::remove(int item)
{
Node<T>* current,*trailCurrent;
bool found = false;
if(root == NULL) cout << "Tree is Empty!!"<<endl;
else {
current=root;
while(current != NULL && !found){
if(current->val == item)
found = true;
else {
trailCurrent=current;
if(item < current->val)
current = current->left;
else
current = current->right;
}
}
if(current==NULL)
cout << "Node to be deleted is not in tree"<<endl;
else if(found)
{
if(current==root)
removeNode(root);
else if(item < trailCurrent->val)
removeNode(trailCurrent->left);
else removeNode(trailCurrent->right);
}
}//else block ends
}
template<typename T>
void BinaryTreeLinkedList<T>:: search(T toFind)
{
if(root==NULL)
cout << "Can not search empty tree"<<endl;
else
{
Node<T> *ptr = root;
bool found = false;
while (ptr!=NULL && !found)
{
if(toFind == ptr->val)
{
found=true;
}
if(toFind < ptr->val)
{
ptr = ptr->left;
}
else
{
ptr = ptr->right;
}
}
if(!found)
cout << "Vale not found"<<endl;
else
cout << "Found"<<endl;
}
}
template<typename T>
void BinaryTreeLinkedList<T>:: insertRec(T item)
{
insertRec(item,root);
}
template<typename T>
void BinaryTreeLinkedList<T>:: searchRec(T item)
{
if(root==NULL)
cout << "Can not search empty tree"<<endl;
else if(searchRec(item,root)) cout << "Found"<<endl;
else cout << "Value does not exists"<<endl;
}
template<typename T>
void BinaryTreeLinkedList<T>::removeRec(T item)
{
removeRec(item,root);
}
template<typename T>
void BinaryTreeLinkedList<T>::inOrder() const
{
inorder(root);
}
template<typename T>
void BinaryTreeLinkedList<T>::preOrder() const
{
preorder(root);
}
template<typename T>
void BinaryTreeLinkedList<T>::postOrder()const
{
postorder(root);
}
template<typename T>
bool BinaryTreeLinkedList<T>::isBst()
{
if(root==NULL)
return true;
vector<T> vec;
bstHelper(root,vec);
if(isSorted(vec))
return true;
return false;
}
template<typename T>
void BinaryTreeLinkedList<T>::levelOrder()
{
queue<Node<T>* > q;
q.push(root);
while(!q.empty())
{
Node<T>* temp = q.front();
q.pop();
cout << temp->val<<endl;
if(temp->left!=NULL)
q.push(temp->left);
if(temp->right!=NULL)
q.push(temp->right);
}
}
template<typename T>
BinaryTreeLinkedList<T>::BinaryTreeLinkedList(const BinaryTreeLinkedList<T>& other) //Copy Constructor
{
if(other.root==NULL)
root=NULL;
else
copyTree(root,other.root);
}
template<typename T>
const BinaryTreeLinkedList<T>& BinaryTreeLinkedList<T>::operator=(const BinaryTreeLinkedList<T>& other)//Assignement Operator
{
if(this!=&other)
{
if(root!=NULL)
destroy(root);
if(other.root==NULL)
root=NULL;
else
copyTree(root,other.root);
}
return *this;
}
template<typename T>
BinaryTreeLinkedList<T>::~BinaryTreeLinkedList()
{
destroy(root);
}
template<typename T>
bool operator==(BinaryTreeLinkedList<T>& T1,BinaryTreeLinkedList<T>& T2)
{
vector<T> v1;
T1.bstHelper(T1.root,v1);
vector<T> v2;
T2.bstHelper(T2.root,v2);
if(v1.size()!=v2.size())
return false;
for(int i=0;i<v1.size();i++)
if(v1.at(i)!=v2.at(i))
return false;
return true;
}
template<typename T>
vector<T> BinaryTreeLinkedList<T>::linkedListToArray()
{
vector<T> v;
linkedListToArray(root,v);
return v;
}
template<typename T>
void BinaryTreeLinkedList<T>::arrayToLinkedList()
{
cout << "Not implemented"<<endl;
}
#include<iostream>
#include"BinaryTreeLinkedList.h"
using namespace std;
void main()
{
BinaryTreeLinkedList<int> bst;
/*bst.insertRec(80);
bst.insertRec(200);
bst.insertRec(300);
bst.insertRec(150);
bst.insertRec(70);
bst.insertRec(90);
bst.insertRec(60);
*/
bool exit = false;
do
{
int val;
cout << "Enter a Val: ";cin>>val;
cout <<"*******Insertion*******"<<endl;
cout << "1 To Add New Node (Iteratively)"<<endl;
cout << "2 To Add New Node (Recursively)"<<endl;
cout <<"*******Searching*******"<<endl;
cout << "3 To Search for Node (Iteratively)"<<endl;
cout << "4 To Search for Node (Recursively)"<<endl;
cout <<"*******Removal*********"<<endl;
cout << "5 To Remove Node (Iteratively)"<<endl;
cout << "6 To Remove Node (Recursively)"<<endl;
cout <<"*******Transversal*****"<<endl;
cout << "7 In Order (Recursively)"<<endl;
cout << "8 Pre Order (Recursively)"<<endl;
cout << "9 Post Order (Recursively)"<<endl;
cout << "10 Level Order (Recursively)"<<endl;
cout << "=========================="<<endl;
int option;cin>>option;
cout << "=========================="<<endl;
switch (option)
{
case 1:
bst.insert(val);
break;
case 2:
bst.insertRec(val);
break;
case 3:
bst.search(val);
break;
case 4:
bst.searchRec(val);
break;
case 5:
bst.remove(val);
break;
case 6:
bst.removeRec(val);
break;
case 7:
bst.inOrder();
break;
case 8:
bst.preOrder();
break;
case 9:
bst.postOrder();
break;
case 10:
bst.levelOrder();
break;
default:
exit=true;
break;
}
} while (!exit);
/*bst.insert(80);
bst.insert(200);
bst.insert(300);
bst.insert(150);
bst.insert(70);
bst.insert(90);
bst.insert(60);*/
/*bst.levelOrder();
vector<int> v;
v = bst.linkedListToArray();
for (int i = 0; i < v.size(); i++)
{
cout << v.at(i)<< ' ';
}*/
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.