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.
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.
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