Problem : To convert a BST to a sorted Double Linked List.
#include<iostream.h>
#include<stdio.h>
//Using same node struct for Tree and List.
class Node{
public:
int data;
Node* left;
Node* right;
};
Node *head=NULL;
Node* lastNode =NULL;
void createList(Node *temp)
{
if(head==NULL)
{
head=temp;
lastNode=head;
}
else
{
lastNode->right = temp;
temp->left=lastNode;
lastNode = temp;
}
}
void print(Node* node)
{
if(node)
{
print(node->left);
cout<<" node data : "<<node->data <<endl;
print(node->right);
}
};
void inorder(Node* node)
{
if(node)
{
inorder(node->left);
createList(node);
inorder(node->right);
}
};
Node* create(int data,Node *node)
{
if(node==NULL)
{
cout<<"Adding first node "<<endl;
node=new Node();
node->data=data;
node->left=NULL;
node->right=NULL;
return node;
}
if(node->data>=data)
{
cout<<"Adding to the left"<<endl;
node->left=create(data,node->left);
}
else
{
cout<<"Adding to the right"<<endl;
node->right=create(data,node->right);
}
return node;
}
void main()
{
int data;
Node *temp=NULL;
char b='a';
while(b!='k')
{
cout<<"enter data"<<endl;
cin>>data;
temp=create(data,temp);
cout<<"enter choice"<<endl;
cin>>b;
}
print(temp);
cout<<"converitng to double linked list by calling tree inorder"<<endl;
inorder(temp);
Node* t=head;
while(t)
{
cout<<"Data :"<<t->data<<endl;
t=t->right;
}
cout<<"printing from end"<<endl;
t=lastNode;
while(t)
{
cout<<"Data :"<<t->data<<endl;
t=t->left;
}
}
No comments:
Post a Comment