Algorithm :
1 Do inorder traversal and at the time of reading data from tree, add
data to doubly link list.
(Inorder traversal will give you sorted order data and it can be
added to DLL. Thus, we can get sorted DLL.)
Code :
struct node
{
struct node *left;
int data;
struct node *right;
};
struct dllist {
int number;
struct dllist *next;
struct dllist *prev;
};
struct dllist *head, *tail, *listnode;
void bstToDLL(struct node *treenode) {
treeTraverse(treenode);
for(listnode = head; listnode != NULL; listnode = listnode->next) {
printf("%d\n", listnode->number);
}
}
void treeTraverse(struct node *treenode)
{
if(treenode!=NULL)
{
treeTraverse(treenode->left);
listnode = (struct dllist *)malloc(sizeof(struct dllist));
listnode->number = treenode->data;
appendToDoublyLinkList(listnode);
treeTraverse(treenode->right);
}
else
return;
}
void appendToDoublyLinkList(struct dllist *listnode) {
if(head == NULL) {
head = listnode;
listnode->prev = NULL;
}
else {
tail->next = listnode;
listnode->prev = tail;
}
tail = listnode;
listnode->next = NULL;
}
On Mar 28, 3:13 pm, Piyush Verma <114piy...@gmail.com> wrote:
> how to convert a BST into a sorted doubly linked list.
> is there any solution of this question.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
