Talk:Left-child right-sibling binary tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing (Rated Stub-class)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Stub-Class article Stub  This article has been rated as Stub-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
Note icon
This article has been automatically rated by a bot or other tool as Stub-Class because it uses a stub template. Please ensure the assessment is correct before removing the |auto= parameter.

Additional information?[edit]

N-ary to binary.svg

It says, "[...] is not reversible in general without additional information". As I see it, a K-ary Tree and a LC-RS Tree are just different representations of the same high-level data structure (like a directory structure). The tree in the example image is reversible (just think of the right one as being rotated 45 degrees clockwise) and going back and forth between a linked list and a subtree is trivial.

There is a small discrepancy that in a K-ary Tree the number of children is limited to K and in a LC-RS Tree there is no such limit. Only when a tree is converted to LC-RS, mutated, and attempted to convert back to K-ary, there is a chance that K needs to grow, which makes them incompatible. But if you think of it as converting from and back to a generic tree (as if K is infinite or variable), they're completely interchangeable. --Zom-B (talk) 21:14, 14 December 2012 (UTC)

If its reversible or not depends on the computational representation. If the representation of the tree distinguish left and right sons (most commons case is using pointers in C), its reversible. But if its represented as a simple graph G=(P,E) with P being a set of nodes and E a set of edges, then is not reversible, because you need to separate blue and black edges. It would be reversible if we had G=(P,E1,E2) being E1 the set of blue edges and E2 the set of black edges. We could include a section about the computational representation of the tree but I couldn't find many good sources on this.--Neo139 (talk) 18:23, 15 December 2012 (UTC)

A couple of other readers also found this confusing. Suggest moving the explanation from talk section to main article. — Preceding unsigned comment added by (talk) 16:40, 10 April 2013 (UTC)