二重連鎖木

二重連鎖木（にじゅうれんさぎ、英: doubly chained tree）や左-子，右-兄弟表現（英: left-child, right-sibling representation）^[1]や子-兄弟表現（英: child-sibling representation）^[2]や filial-heir chain^[3] とは、多分木を、直接子ノードのポインタの集合で管理するのではなく、子ノード1つと兄弟ノード1つのポインタで管理する方法。つまり多分木を二分木に変換する。1963年に Edward H. Sussenguth が発表した^[4]。

ノード n の k 番目の子供を取得するには、以下のように行う。ノードは child と next-sibling を保持している。

procedure kth-child(n, k):
    child ← n.child
    while k ≠ 0 and child ≠ nil:
        child ← child.next-sibling
        k ← k − 1
    return child  // nil を返す場合もある

参照