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