木構造(tree structure)
階層関係(上下関係)を表現するためのデータ構造
例) UNIX,WindowsのOSでの階層ディレクトリ
- １つの節は、それ自体が木である。この木に含まれるただ１つの節が、この木の根である。
- k個の木T1～Tkがあり、それぞれの根を節n1～nkとする。
節nを節n1～nkの親にすると、節nを根とする新しい木Tが得られる。
このとき、木T1～Tkは、木Tの部分木(subtree)であるという。
部分木の根n1～nkは、節nの子であるという。
キーワード
- ノード、節(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)