Threaded binary tree not present #268
Description
`#include
using namespace std;
class node{
public:
int data;
int rbit,lbit; // rbit = 1 when right child is normal and 0 if right child is thread
// lbit = 1 when left child is normal and 0 if it is thread
node *left,*right;
};
class tree{
public:
node * insert(node *,int ); //to insert data
node * getnode(int ); //for allocation of memory and initializing the node
void inorder(node *);
node * inorderSuc(node *); //will return inorder successor
node * preorderSucc(node *);
void preorder(node *);
};
//to allocate and initialize the node
node * tree :: getnode(int d){
node * p = new node;
p->data = d;
p->left = p->right = NULL;
p->rbit = p->lbit = 0;
}
//insertion in tbt(double)
node * tree :: insert(node * a,int d){
node *p,*q,*r;
p = a;
q = a;
if(a == NULL){
a = getnode(d);
return a;
}
while(p!=NULL && q->data != d){
q = p;
if(q->data > d){
if(q->lbit == 1){
p = q->left;
}
else{
break;
}
}
else if(q->data < d){
if(q->rbit == 1){
p = q->right;
}
else{
break;
}
}
}
if(q->data == d){
cout << "TREE CANNOT HAVE DUPLICATE ELEMENTS\n";
return a;
}
else if(q->data > d){
r = getnode(d);
r->left = q->left;
q->lbit = 1; //now it has normal child
q->left = r;
r->right = q;
}
else{
r = getnode(d);
r->left = q;
q->rbit = 1; //now it has normal child
r->right = q->right;
q->right = r;
}
return a;
}
node * tree :: inorderSuc(node *r){
node *p = r;
if(p->rbit == 0){
return p->right;
}
p = p->right;
while(p->lbit == 1){
p = p->left;
}
return p;
}
// INORDER TRAVERSAL => (LEFT , ROOT , RIGHT)
void tree :: inorder(node *r){
/*as we can obtain the inorder successor using the above function we will travell to the left most
node of the tree and start printing the inorder successors */
node * p = r;
while(p->lbit == 1){ //continue untill thread comes
p = p->left;
}
while(p!=NULL){
cout << p->data << " " ;
p = inorderSuc(p);
}
}
int main(){
tree b;
node *root=NULL;
cout << "Data insertion in TBT\n" ;
root = b.insert(root,3);
root = b.insert(root,4);
root = b.insert(root,5);
root = b.insert(root,1);
root = b.insert(root,2);
cout << "Inorder traversal\n";
b.inorder(root);
return 0;
}`
I wanna contribute this, will be adding other traversals and deletion of nodes in tree.so Please tell how should I contribute