CODEWITHSUNDEEP
listdata-structuresbinary-search-tree
hiway
hiway

Reputation: 3976

how to transform a binary search tree to a bidirectional list?

This is a binary search tree：

enter image description here

now I want to transform it to a bi-directional list like this: 4<->6<->8<->10<->12<->14<->16, how to do it?

Thx

Upvotes: 0

Views: 452

Answers (2)

Amarnath Krishnan
Amarnath Krishnan

Reputation: 1263

You can do the inorder traversal of the tree and insert the data into the list.

// Doubly linked list structure
typedef struct node
{
  int data;
  struct node *prev;
  struct node *next;
 }list;

// Create node  
list* createnode(int x)
{
   list* temp=(list*)malloc(sizeof(list));
   temp->data=x;
   temp->prev=NULL;
   temp->next=NULL;
   return temp;
}

list *head=NULL; // To keep track of head
list *ptr=NULL; //To keep track of last pointer in list
Inorder(tree * root)
{
   if(root==NULL) return;
   Inorder(root->left);
   // Insert head node
   if(head==NULL) 
   {
       head=createnode(root->data);
       ptr=head;
   }
   // Insert other nodes and provide links
   else
   {
      list *temp=createnode(root->data);
      ptr->next=temp;
      temp->prev=ptr;
      ptr=temp;
   }
   Inorder(root->right);
}

Upvotes: 2

Alex
Alex

Reputation: 759

Do an inorder tree traversal: http://en.wikipedia.org/wiki/Tree_traversal#In-order Where visit(node) is appending the node to a doubly linked list.

Upvotes: 0

Related Questions