Dec 18, 2008 at 12:05am UTC
how to convrt a binary tree into a doubly linked list?
can anybody come up with the code
i think it requires a bfs traversal of the tree
but is there any better solution
std::cout<<"thanks in advance"<<endl;
Dec 18, 2008 at 12:40am UTC
node * dlroot =null;
node * q =null;
BtoDL (node *p){
if (p){
BtoDL(p->left);
BtoDL(p->right);
if(dlroot )
{
q->right = p; // putting right and left pointer of traversed node
p->left = q;
q=q->right; //updating node of DL.
}
else { //This part of code will execute only once.
dlroot = p;
dlroot->right=dlroot->left =null;
q=dlroot;
}
}// enf outer if.
} //end of function.
this is the code by the way
Dec 19, 2008 at 7:45am UTC
Do the nodes in the DLL have to be in some special order with resopect to the original BT?
Dec 19, 2008 at 4:04pm UTC
no need
but the solution i posted is based on postorder traversal
if u cud modify the algorithm to perform the changes while doing an inorder traversal
we ll get the sorted data in doubly linked list
i wonder if we cud perform a bfs or a dfs to do the same
any suggestion
can anybody come up with a better solution
Jan 5, 2009 at 5:30pm UTC
Do any traversal and just make
node * temp = new node ();
and than like it with the previous one in that trversal .. and the code is like this . with bit changes .. i find this way bit easier ,
Jan 8, 2009 at 11:11am UTC
@above
the main thing is to change the tree into dll.....
not creating a new one