【誰でもわかる基本情報シリーズ】22.「木構造」

テクノロジー
スポンサーリンク

みなさんこんにちは!おさかなです!

今回から「誰でもわかる基本情報シリーズ」というテーマで「基本情報技術者試験」に合格するための知識をご紹介していきます!

第22弾は「木構造」について、書いていこうと思います!

それでは、レッツゴー!!!!!

想定読者
・「基本情報技術者試験」を受験しようと思っている人
・「基本情報」に必要な知識を身に着けたい人
・IT初心者の人

前回の復習

前回は「キューとスタック」について詳しく見ていきました!

【誰でもわかる基本情報シリーズ】21.「キューとスタック」
みなさんこんにちは!おさかなです! 今回から「誰でもわかる基本情報シリーズ」というテーマで「基本情報技術者試験」に合格するための知識をご紹介していきます! 第21弾は「キューとスタック」について、書いていこうと思います! ...

今回は「木構造」について学習していきます!

木構造(ツリー構造)

木構造(ツリー構造)」とは、階層の上位から下位に節点をたどることによって、データを取り出すことができるデータ構造のことです。

・〇 … 節(ノード)
・ー … 枝(ブランチ)
・最下位〇 … 葉(リーフ)

さらに、木構造の各節には、親子関係があります。

・上位の節 … 
・下位の節 … 
・節にぶら下がっているもの … 部分木
・右側にぶら下がっているもの … 右部分木
・左側にぶら下がっているもの … 左部分木

 

おさかな
おさかな

」を「逆さま」にしたイメージだよ!

2分木の種類

2分木とは、すべての枝の分岐が「2つ以下」であるものをいいます。同じ親を持つ子同士に順序関係がある「順序木」の1種で、様々な種類があるので1つずつ見ていきましょう!

完全2分木

完全2分木」とは、根から葉までの深さが全て等しい2分木です。
しかし、特例として深さが1だけ深い葉があり、木全体の左詰めになっているものも完全2分木とされます。

2分探索大

2分探索大」とは「左の子<親<右の子」という関係をもった2分木です。

 

2分探索木は主に、「データの探索」に利用されます。

〇データの探索方法

1.根から順に、各節の値と「比較
・節の値と「同じ」なら、探索を「終了」 →該当データが見つかった
・節の値より、「小さい」場合は、「左部分木」へ
・節の値より、「大きい」場合は、「右部分木」へ
2.これを繰り返す
3.葉まで達しても一致しないなら、探索を「終了」 →該当データが見つからなかった

 

ヒープ木

ヒープ木」とは、各節において「親<子」または「子<親」という関係を持った完全2分木です。

・「親<子」 … 根の値が「最小値
・「子<親」 … 根の値が「最大値
ヒープ木は主に、データを整列するのに利用されます。
おさかな
おさかな

データの整列」は次回解説するよ!

逆ポーランド記法

逆ポーランド記法(後置記法)」とは、2分木を使って算術式を表記する方法の1つです。

 … 演算子
 … 被演算数

この記法では、「左部分木」→「右部分木」→「節点」の順に取り出します。

おさかな
おさかな

」から式を見ていき、演算子があったら「直前の2つの項」を計算する流れだよ!

逆ポーランド記法では、「スタック」を使って演算します。

・被演算数はスタックにPUSHする
・演算子はスタックからデータを2個POPし、計算結果をスタックにPUSHする
おさかな
おさかな

しっかり復習しておこう!

おさかなが参考にした「書籍」一覧↓

(PDF・スマホ単語帳付)かんたん合格 基本情報技術者教科書 令和2年度

令和02年 イメージ&クレバー方式でよくわかる 栢木先生の基本情報技術者教室 情報処理技術者試験

キタミ式イラストIT塾 基本情報技術者 令和02年 (情報処理技術者試験)

令和02年【春期】【秋期】 基本情報技術者 合格教本

感想・まとめ

今回は「木構造」について、書いていきました…!

いかがだったでしょうか?

図を使いながら、構造をざっくくり理解することが出来たと思います!ぜひ、しっかりと復習して正しく読み取れるようにしておいてください。

おさかな
おさかな

4月19日に予定されていた、「基本情報技術者試験」およびIPA主催のその他の試験は中止となりました。
詳しくはコチラをご覧ください。

↓次回は「データの整列」について解説していきます!

【誰でもわかる基本情報シリーズ】23.「データの整列」
みなさんこんにちは!おさかなです! 今回から「誰でもわかる基本情報シリーズ」というテーマで「基本情報技術者試験」に合格するための知識をご紹介していきます! 第23弾は「データの整列」について、書いていこうと思います! それ...

お楽しみに~!

おさかなびではプログラミング学習中の人、ブログ初心者に向けて、「デジタル時代を楽しむためのミニ知識」をご紹介しています!
ぜひ他のページも覗いてみてください…!

それでは今回はこの辺で!

ここまで読んでくださり、ありがとうございました!

おさかなでした!

【おさかなび-osakanav-】では、この記事の感想!おさかなへの応援メッセージ!おさかなに聞きたい事、質問!記事にしてほしい内容!などを大募集中!

「氏名」「メールアドレス」「内容」の3点をご記入の上「osakana1699@gmail.com」までご応募ください!

タイトルとURLをコピーしました