Left-child right-sibling binary tree
Every multi-way or k-ary tree structure studied in computer science admits a representation as a binary tree, which goes by various names including child-sibling representation, left-child, right-sibling binary tree, doubly chained tree or filial-heir chain.
In a binary tree that represents a multi-way tree T, each node corresponds to a node in T and has two pointers: one to the node's first child, and one to its next sibling in T. The children of a node thus form a singly-linked list. To find a node n's k'th child, one needs to traverse this list:
procedure kth-child(n, k): child ← n.child while k ≠ 0 and child ≠ nil: child ← child.next-sibling k ← k − 1 return child // may return nil
The process of converting from a k-ary tree to an LC-RS binary tree is sometimes called the Knuth transform. 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.
Doubly chained trees were described by Sussenguth in 1963.
- Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. (1986). "The pairing heap: a new form of self-adjusting heap" (PDF). Algorithmica 1 (1): 111–129. doi:10.1007/BF01840439.
- Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001) . Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 214–217. ISBN 0-262-03293-7.
- Black, Paul E. "Binary tree representation of trees". Dictionary of Algorithms and Data Structures. NIST.
- Computer Data Structures. John L. Pfaltz.
- Sussenguth, Edward H. (1963). "Use of tree structures for processing files". Communications of the ACM 6 (5): 272–279. doi:10.1145/366552.366600.
|This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.|