Thursday, January 24, 2013

Change the structure of a Tree node to hold a pointer for the next in-order element (sucessor).

Idea is simple, based on Threaded Trees concept.
We need to modify Morris In-Order Traversal algorithm a little to convert the tree into a linked list, where each node's right pointer will point to its in-order successor.

There is no need to change the current tree node structure.
struct node{
 int data;
 struct node* left;
 struct node* right;
};

/*Tree to InOrder list conversion*/
struct node*  MorrisInOrderConversion(struct node* root){
 struct node *curr,*pre,*head=NULL;
 
 if(root==NULL){
  return NULL;
 }
 
 curr=root;
 
 while(curr!=NULL){
  if(curr->left==NULL){
   if(head==NULL){
    head=curr;
   }
   curr=curr->right;
  }else{
   pre=curr->left;
   
   while(pre->right!=NULL && pre->right!=curr){
    pre=pre->right;
   }
   
   if(pre->right==NULL){
    pre->right=curr;
    curr=curr->left;
   }else{
    struct node* next=curr->right;
    struct node* temp=curr->right;
    curr->right=NULL;
    while(next->left!=NULL){
     next=next->left;
    }
    curr->right=next;
    curr=temp;
   }
  }
 }
 
 return head; //Returns head of the converted list
}

/*Traverse the Converted list*/
void traverseList(struct node* head){
 while(head!=NULL){
  printf("%d ",head->data);
  head=head->right;
 }
}

And One more approach also exists for this, which involves creating a new list without changing current tree structure.

This can be written with Morris In-Order Tree traversal algorithm or Generic In-Order traversal algorithm.

Below is the code for generic traversal algorithm.

struct node{
 int data;
 struct node* left;
 struct node* right;
};

/*New Node structure defined*/
struct iNode{
 struct node* pNode;
 struct iNode* successor;
};

/*Tree to InOrder List - Start */
void insertINode(struct node* p){
 struct iNode *temp = (struct iNode*)malloc(sizeof(struct iNode));
 temp->pNode=p;
 temp->successor=NULL;
 
 if(iHead==NULL){
  iHead=temp;
 }else{
  iList->successor=temp;
 }
 iList=temp; 
};

void inOrderList(struct node* root){
 if(root!=NULL){
  inOrderList(root->left);
  insertINode(root);
  inOrderList(root->right);
 }
};

void traverseIList(){
 struct iNode *curr=iHead; 
 while(curr!=NULL){
  printf("%d ",curr->pNode->data);
  curr=curr->successor;
 }
}
/*Tree to InOrder List - End */

No comments:

Post a Comment