Another approach is to form a singly linked, NULL-terminated list
(connected e.g. by 'left' pointers). This is a harder problem, and
it
might be required if you have a purpose for the other (right)
pointer. If you need a doubly linked list it's easy to walk down the
singly linked one, creating 'previous' pointers as you go.
The converter accepts both a tree and list that's already in the
correct order, which should be appended at the end of the converted
tree. The result of the append operation should be returned.
NODE *convert(NODE *root, NODE *list)
{
if (root == NULL) return list;
NODE *left_subtree = root->left;
root->left = convert(root->right, list);
return tree(left_subtree, root);
}
I like this solution because it's so simple. Initiate it with
convert(tree, NULL);
If you really need the double links:
void adjust(NODE *head)
{
NODE *p, *q;
for (q = NULL, p = head; p; q = p, p = p->next)
p->right = q;
head->right = q;
q->right = head;
}
On May 26, 3:07 am, jalaj jaiswal <[email protected]> wrote:
> Both the explanations above are wrong . It is true that BST can be
> converted to a Doubly linked list by doing inorder traversal.
>
> But the approach mentioned in the stanford link follows a postorder
> Approach , it is better because it avoids useage of a static/global
> variable which is required in inorder Approach.
> "recursively changing the small and large sub-trees into lists, and then
> append those lists together with the parent node to make larger lists" -
> quoted from the stanford page. (parent is visited after the subtrees)
>
> Explanation of the postorder Approach :-
>
> refer to the drawing in the page.
> FIrst of all it makes the node named 1 as a an independent node after that
> as in postorder it makes node 3 as an independent node . Independent here
> means
> root->left=root->right=NULL.
>
> After that it comes to node 2 . ( Note that it is happening in postorder
> fashion) .
> then it makes node 2 as independent and append it with the list returned
> from left side(which is independent node 1) and list returned from right
> side *(which is independent node 3) and make the left side returned node as
> head and follows the process recursively . The order is similar to inorder
> apptoach which is O(n).
>
> *IF you want to know the inorder approach as well, Here it is :-*
>
> void BSTTODLL( node *root){
> static int count = 0 ;
> static node * temp = NULL:
> if(root != NULL){
> BSTTODLL(root->left);
> if(count == 0) {
> temp = root;
> count++;
> }
> temp->right= root;
> root->left = temp;
> temp = root;
> BSTTODLL(root->right);
> }
>
> }
>
> // explanation is trivial , its just keeping a temp pointer to previous
> node and adjusting pointers in inorder fashion keeping the list sorted.
>
> Hope it Helps !
>
> On Thu, May 24, 2012 at 11:46 PM, sanjay pandey
> <[email protected]>wrote:
>
>
>
>
>
>
>
>
>
> > the main code is dis function only:::::i will explain dis
>
> > static Node treeToList(Node root) {
> > Node aList, bList;
>
> > if (root==NULL) return(NULL);*
> > /* the below next two lines are just lyk inorder traversal...u mst hv
> > done dis*/*
> > aList = treeToList(root->small);
> > bList = treeToList(root->large);
>
> > */* this is for breaking the links of its left n right child nodes n
> > pointing to itself*/*
> > root->small = root;
> > root->large = root;
>
> > * /* Appending leftchild parent n rightchild together in doublylinked
> > list form */*
> > aList = append(aList, root);
> > aList = append(aList, bList);
>
> > return(aList);
> > }
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> Regards,
>
> Jalaj Jaiswal
> Software Developer,
> Adobe Systems
> +91-9019947895
> *
> *
> FACEBOOK <http://www.facebook.com/jalaj.jaiswal89>
> LINKEDIN<http://www.linkedin.com/profile/view?id=34803280&trk=tab_pro>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
