Jump to content

Left-child right-sibling binary tree

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Cybercobra (talk | contribs) at 19:38, 17 January 2012 (→See also). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer science, a left child-right sibling binary tree is a binary tree representation of a k-ary tree. The process of converting from a k-ary tree to an LC-RS binary tree is not reversible in general without additional information.

To form a binary tree from an arbitrary k-ary tree by this method, the root of the original tree is made the root of the binary tree. Then, starting with the root, each node's leftmost child in the original tree is made its left child in the binary tree, and its nearest sibling to the right in the original tree is made its right child in the binary tree.[1]

If the original tree was sorted, the new tree will be a binary search tree.

See also

References

  1. ^ Public Domain This article incorporates public domain material from Paul E. Black. "Left child-right sibling binary tree". Dictionary of Algorithms and Data Structures. NIST.


Stub icon

This computer science article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Left-child_right-sibling_binary_tree&oldid=471914393"