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 (sometimes called Knuth transform) 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.
If the original tree was sorted, the new tree will be a binary search tree.
Famous quotes containing the words left, sibling and/or tree:
“But I was trying to tell you about a strange thing
That happened to me, but this is no way to tell about it,
By making it truly happen. It drifts away in fragments.
And one is left sitting in the yard
To try to write poetry
Using what Wyatt and Surrey left around....”
—John Ashbery (b. 1927)
“It seems to me that we have to draw the line in sibling rivalry whenever rivalry goes out of bounds into destructive behavior of a physical or verbal kind. The principle needs to be this: Whatever the reasons for your feelings you will have to find civilized solutions.”
—Selma H. Fraiberg (20th century)
“The tree which moves some to tears of joy is in the eyes of others only a green thing that stands in the way. Some see nature all ridicule and deformity ... and some scarce see nature at all. But to the eyes of the man of imagination, nature is imagination itself.”
—William Blake (1757–1827)