Left-child right-sibling binary tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computer science, a left-child, right-sibling binary tree is a binary tree representation of a k-ary tree.[1] The process of converting from a k-ary tree to an LC-RS binary tree (sometimes called Knuth transform[2]).

6-ary tree represented as a binary tree

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.[3]

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

See also[edit]

References[edit]

  1. ^ Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein (2001). Introduction To Algorithms (2nd ed.). MIT Press. pp. 214–217. ISBN 9780262032933. 
  2. ^ Computer Data Structures. John L. Pfaltz.
  3. ^ Paul E. Black, Left child-right sibling binary tree at the NIST Dictionary of Algorithms and Data Structures.