みなさんこんにちは！おさかなです！
今回から「誰でもわかる基本情報シリーズ」というテーマで「基本情報技術者試験」に合格するための知識をご紹介していきます！
第22弾は「木構造」について、書いていこうと思います！
それでは、レッツゴー！！！！！
・「基本情報技術者試験」を受験しようと思っている人
・「基本情報」に必要な知識を身に着けたい人
・IT初心者の人
前回の復習
前回は「キューとスタック」について詳しく見ていきました！
今回は「木構造」について学習していきます！
木構造(ツリー構造)
「木構造(ツリー構造)」とは、階層の上位から下位に節点をたどることによって、データを取り出すことができるデータ構造のことです。
・ー … 枝(ブランチ)
・最下位〇 … 葉(リーフ)
さらに、木構造の各節には、親子関係があります。
・上位の節 … 親
・下位の節 … 子
・節にぶら下がっているもの … 部分木
・右側にぶら下がっているもの … 右部分木
・左側にぶら下がっているもの … 左部分木
「木」を「逆さま」にしたイメージだよ！
2分木の種類
「2分木」とは、すべての枝の分岐が「2つ以下」であるものをいいます。同じ親を持つ子同士に順序関係がある「順序木」の1種で、様々な種類があるので1つずつ見ていきましょう！
完全2分木
しかし、特例として深さが1だけ深い葉があり、木全体の左詰めになっているものも完全2分木とされます。
2分探索大
「2分探索大」とは「左の子＜親＜右の子」という関係をもった2分木です。
2分探索木は主に、「データの探索」に利用されます。
〇データの探索方法
1．根から順に、各節の値と「比較」
・節の値と「同じ」なら、探索を「終了」 →該当データが見つかった
・節の値より、「小さい」場合は、「左部分木」へ
・節の値より、「大きい」場合は、「右部分木」へ
2．これを繰り返す
3．葉まで達しても一致しないなら、探索を「終了」 →該当データが見つからなかった
ヒープ木
「ヒープ木」とは、各節において「親＜子」または「子＜親」という関係を持った完全2分木です。
・「子＜親」 … 根の値が「最大値」
「データの整列」は次回解説するよ！
逆ポーランド記法
「逆ポーランド記法(後置記法)」とは、2分木を使って算術式を表記する方法の１つです。
・葉 … 被演算数
この記法では、「左部分木」→「右部分木」→「節点」の順に取り出します。
「左」から式を見ていき、演算子があったら「直前の2つの項」を計算する流れだよ！
逆ポーランド記法では、「スタック」を使って演算します。
・演算子はスタックからデータを2個POPし、計算結果をスタックにPUSHする
しっかり復習しておこう！
おさかなが参考にした「書籍」一覧↓
・(PDF・スマホ単語帳付)かんたん合格 基本情報技術者教科書 令和2年度
・令和02年 イメージ＆クレバー方式でよくわかる 栢木先生の基本情報技術者教室 情報処理技術者試験
・キタミ式イラストIT塾 基本情報技術者 令和02年 (情報処理技術者試験)
感想・まとめ
今回は「木構造」について、書いていきました…！
いかがだったでしょうか？
図を使いながら、構造をざっくくり理解することが出来たと思います！ぜひ、しっかりと復習して正しく読み取れるようにしておいてください。
4月19日に予定されていた、「基本情報技術者試験」およびIPA主催のその他の試験は中止となりました。
詳しくはコチラをご覧ください。
↓次回は「データの整列」について解説していきます！
お楽しみに～！
おさかなびではプログラミング学習中の人、ブログ初心者に向けて、「デジタル時代を楽しむためのミニ知識」をご紹介しています！
ぜひ他のページも覗いてみてください…！
それでは今回はこの辺で！
ここまで読んでくださり、ありがとうございました！
おさかなでした！
【おさかなび-osakanav-】では、この記事の感想！おさかなへの応援メッセージ！おさかなに聞きたい事、質問！記事にしてほしい内容！などを大募集中！
「氏名」「メールアドレス」「内容」の3点をご記入の上「osakana1699@gmail.com」までご応募ください！
