WE'll be taking inorder traversal of the tree and during the traversal will modify the right pointers only(using method "make_right") such that a linked list is formed having only valid right pointers. Then another method "make_left" is called to make the left pointers of the nodes point to valid previous nodes.
#include<iostream.h>
class node
{
protected:
int info;
node* left;
node* right;
public:
void insert(node ** root,int n)
{
if((*root) == NULL)
{
(* root)=new node;
(* root)->info=n;
(* root)->left=NULL;
(* root)->right=NULL;
}
else
{
node * ptr=(* root);
while(1)
{
if(n > ptr->info && ptr->right!=NULL)
ptr=ptr->right;
else if(n > ptr->info && ptr->right==NULL)
{
ptr->right=new node;
ptr=ptr->right;
// cout<<"RIGHT";
ptr->info=n;
ptr->left=NULL;
ptr->right=NULL;
break;
}
else if(n <= ptr->info && ptr->left!=NULL)
ptr=ptr->left;
else
{
ptr->left=new node;
ptr=ptr->left;
// cout<<"left";
ptr->info=n;
ptr->left=NULL;
ptr->right=NULL;
break;
}
}
}
}
void inorder(node * ptr)
{
if(ptr->left!=NULL)
inorder(ptr->left);
cout<<"\n--"<<ptr->info;
if(ptr->right!=NULL)
inorder(ptr->right);
}
void make_right(node* root,node **start)
{
if(root== NULL)
return;
make_right(root->left,start);
(*start)->right=root;
(*start)=root;
make_right(root->right,start);
}
node* make_left(node* root)
{
if(root==NULL)
return NULL;
node *ptr=root;
while((ptr->right) != NULL)
{
ptr->right->left=ptr;
ptr=ptr->right;
}
root->left=NULL;
return (ptr);
}
void make_dll(node *root,node **start,node **end)
{
if(root==NULL)
{
(*end)=NULL;
return;
}
(*start)=new node;
node *st=(*start);
make_right(root,start);
(*start)=st->right;
(*end)=make_left(*start);
}
void print_list(node *st)
{
cout<<"\n\n";
while(st!=NULL)
{
cout<<st->info<<" --> ";
st=st->right;
}
}
void print_rev_list(node *st)
{
cout<<"\n\n";
while(st!=NULL)
{
cout<<st->info<<" --> ";
st=st->left;
}
}
};
int main()
{
node *root=NULL;
root->insert(&root,5);
root->insert(&root,8);
root->insert(&root,6);
root->insert(&root,3);
root->insert(&root,2);
root->insert(&root,4);
root->insert(&root,7);
root->insert(&root,9);
root->inorder(root);
node* end;
node*start;
root->make_dll(root,&start,&end);
root->print_list(start);
root->print_rev_list(end);
return 0;
}
