Convet Binary tree to Circular linked list
-
Hi All, How to convert a Binary tree to Circular linked list? Any help would be appreciated. With Regards, A.Ilamparithi.
-
Hi All, How to convert a Binary tree to Circular linked list? Any help would be appreciated. With Regards, A.Ilamparithi.
Ilamparithi wrote:
How to convert a Binary tree to Circular linked list?
Why would you want to? homework assignment? or change of design? Because of that possibility, I won't give you code. Any tree is read very easily. You have a descending key branch and an ascending key branch. A balanced tree has equal descending key branches as ascending key branches, each node is compared high or low to a key search and you follow either branch as appropriate, when you find equal, you stop. A binary tree, like a binary search is a minimal path to solution design, very efficient in search, but very poor design for sequential access. Lists are very poor random search but exceedingly fast in sequential search operations. To follow a tree in sequential order is easy, you always follow a branch until your reach a bottom leaf and then back track and follow the next. // psuedo-code this will NOT compile!! process (node) { if (node->left not empty ) process (node->left) display (node) if (node->right not empty ) process (node->right) } pretty simple, but the stack flow from recursion has severe overhead, especially for large trees. You can change the display node portion to add to a sequential list, and add the necessary passed parameters to do so. But on large trees the overhead of process will be very high. If you notice most of the time is spent calling functions, so the cpu is spending 66% of its time doing nothing but calling code, only 33% processing a node. ouch. If you have a design that must change from random access priority speed to sequential access priority speed, this is a great one-time tool to rebuild your list. If the list does not need to be ordered, then it doesn't matter what order you process left right and display operations. Circular linked lists are often random order, so I guess it doesn't matter, I highly dislike random order data because of the unpredictability factor. In my business "knowing" that a process will always take n milliseconds is more important than making it fast (though I try to do both in balanced form). read this: http://en.wikipedia.org/wiki/Tree_search[^] _________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)