nav_indian
August 16th, 2009, 09:58 AM
Hi,
I know its a bit strange to ask abt explanation of some portion of a specific book. But I don't know if there is a better place to post my query on Net anywhere else. Sorry abt that.
So here it goes. In Horowitz Sahni book's chapter on trees, the authors explain that the number of distinct binary trees with n nodes is equal to number of distinct permutations obtainable by passing the numbers 1 through n through a stack and deleting in all possible ways.
Now I don't understand how I can use a stack to do this and how to go about passing & deleting numbers from the stack.
This concept is explained by authors in both of these books:-
(a) Fundamentals of Data Structures --- Page 272, 273
(b) Fundamentals of Data Structures in C (2nd Ed) --- Page 260, 261
If someone can explain me this concept for a 3-node binary tree i.e. for n = 3 as an example (which is how the authors also try to explain it but not very clearly), it would be a great help to me! Many thanks.
Kind Regards,
Naveen
I know its a bit strange to ask abt explanation of some portion of a specific book. But I don't know if there is a better place to post my query on Net anywhere else. Sorry abt that.
So here it goes. In Horowitz Sahni book's chapter on trees, the authors explain that the number of distinct binary trees with n nodes is equal to number of distinct permutations obtainable by passing the numbers 1 through n through a stack and deleting in all possible ways.
Now I don't understand how I can use a stack to do this and how to go about passing & deleting numbers from the stack.
This concept is explained by authors in both of these books:-
(a) Fundamentals of Data Structures --- Page 272, 273
(b) Fundamentals of Data Structures in C (2nd Ed) --- Page 260, 261
If someone can explain me this concept for a 3-node binary tree i.e. for n = 3 as an example (which is how the authors also try to explain it but not very clearly), it would be a great help to me! Many thanks.
Kind Regards,
Naveen