データ構造/木構造 - nkym_memo @ ウィキ

木構造(tree structure)

階層関係(上下関係)を表現するためのデータ構造

例)
UNIX,WindowsのOSでの階層ディレクトリ

1. １つの節は、それ自体が木である。この木に含まれるただ１つの節が、この木の根である。
2. k個の木T1〜Tkがあり、それぞれの根を節n1〜nkとする。 　節nを節n1〜nkの親にすると、節nを根とする新しい木Tが得られる。 　このとき、木T1〜Tkは、木Tの部分木(subtree)であるという。 　部分木の根n1〜nkは、節nの子であるという。

&attachref

キーワード

• ノード、節(node) 木構造におけるデータ

• ラベル(label) 節のもつ値

• 根(root) 節のなかで最上位のもの

• 親(parent),子(child) 節の階層関係（上下関係）

• 葉(leaf),端節(terminal node),外部節(external node) 子をもたない節

• 非終端節(non-terminal node),枝節(branch node),内部節(internal node) 葉以外の節

• 部分木(subtree) 特定の節の子を根にする木

• 兄弟(sibling) 同じ親をもつ節同士のこと

• 先祖(ancestor),子孫(descendant) ある節から、根に向かって(上方に)節をたどるとき、途中に出現する節

• レベル(level) 根を０として、階層をたどる回数

• 空の木(null tree) 節を持たない木

順序木/無順序木

• 順序木(ordered tree) 兄弟間で左が兄、右が弟という順序づけを行った木

• 無順序木(unorderd tree),有向木(oriented tree) 兄弟間に順序の無い木

---

参考文献

• 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤嘉雪,ソフトバンククリエイティブ,1998)