@Gene :
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);*
}
what *tree(left_subtree, root)* function doing here??
On Sun, May 27, 2012 at 7:12 PM, Gene <gene.ress...@gmail.com> wrote:
> 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 <jalaj.jaiswa...@gmail.com> 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
> > <sanjaypandey...@gmail.com>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 algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
