テクノロジ
木構造とは
英語名：Tree Structure
ひとことで言うと：ノードを親子関係で階層的につなぎ、根から枝分かれしてデータを表す非線形データ構造。
意味をわかりやすく解説
木構造では最上位を根（root）、子を持たないノードを葉（leaf）と呼びます。二分木では各ノードの子は高々二つで、二分探索木では一般に左部分木に小さい値、右部分木に大きい値を配置します。
木の走査には深さ優先・幅優先があり、二分木では先行順・中間順・後行順などの巡回順序があります。探索木やヒープなど、目的に応じた木構造の特徴を理解します。
具体例
二分探索木で根が8、左に3、右に12と配置されている場合、値5を探すときは8より小さいのでまず左部分木へ進みます。
似た用語との違い
グラフ構造
木は親へ戻る経路が一つの階層構造です。一般のグラフは複数の結び付きや循環も表せます。
基本情報技術者試験の試験ポイント
根・葉・高さ・部分木に加え、二分探索木の大小関係と巡回順序を追えるようにします。
CHECK QUESTION
二分探索木を中間順（左部分木→根→右部分木）で巡回すると、格納値は一般にどのような順になりますか。
答えを見る
昇順になります。二分探索木では左側に小さい値、右側に大きい値を配置するためです。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。