3 木と二分木

コンピュータの木構造は現実の形状とは逆で、逆さまの木です〜

コース内容#

木#

木の構成：ノード + エッジ
- ノード 👉 集合、エッジ 👉 関係
- ルートノード：全体集合；子ノード：部分集合
  - ルートノードの全ての子ノードの集合の和集合 = 全体集合
  - 【考え方】大きな問題を木として抽象化し、小さな問題を子ノードとして抽象化する

構造の定義#

【ノード + エッジ】

一方向の木はリンク構造であり、一つの枝を持つ木構造です
三方向の木の場合、リンクのポインタを next [3] 配列に変更するだけです

属性、特性#

深さ、高さ
- 木の深さと高さは同じ値です：最大のレベル
- ノードの深さと高さは異なります
  - 深さ：ルートノードから数えて、そのノードが何番目のレベルにあるか
  - 高さ：最も深いレベルから数えて、そのノードが何番目のレベルにあるか
次数：子の数
⭐【重要な公式】ノード数 = エッジ数 + 1

二分木#

2 進数は任意の進数に変換できるように、二分木も同様です
- 最初に簡単です
- また、すべての木構造を表すことができます
  - 方法：左の子、右の兄弟法、十字リンク法とも呼ばれます
  - 上から下へ、左から右へ、ノードの子は左側に配置し、ノードの隣接する兄弟は右側に配置します
n 分木の場合、n は不確定ですが、二分木は確定しています
- n 分木は二分木で実現できます
- したがって、二分木を使用することで、不確定性の問題をコンピュータが解決できる確定性のある問題に変換できます
⭐【重要な公式】二分木では、次数 0 のノードの数は次数 2 のノードの数より 1 つ多いです
- 別の重要な公式を利用します：ノード数 = エッジ数 + 1
- ni を次数 i のノードの数とします
- すると：[ノード数] n0 + n1 + n2 = n1 + 2 * n2 + 1 [エッジ数 + 1]
- 得られる：n0 = n2 + 1
トラバース方法：いつ [最初、中間、最後] にルートノードを訪れるかによって決まります
- 前順トラバース：ルート左右
- 中順トラバース：左ルート右
- 後順トラバース：左右ルート
- トラバース時の左、右はそれぞれ左、右の部分木を表します
- 左右の相対的な順序は常に左が前で、右が後ろです
二分木の分類【国際版】、参考Binary tree: Types of binary trees-Wikipedia
- 完全二分木：最後のレベルの最右端を除いて、連続したノードが欠けている場合があります
- 満たされた二分木：次数 0 または 2 であることができます
- 完全二分木：次数がすべて 2 で、すべての葉ノードが同じレベルにある場合
- PS：中国版では完全二分木と満たされた二分木のみを区別し、満たされた二分木の定義は国際版の完全二分木と同じです
完全二分木の特徴 [完全二分木も同様]
- 番号 i のノードの左右の子の番号はそれぞれ 2 * i、2 * i + 1 です
- 連続した空間（配列）を使用して格納し、アルゴリズムの最適化に使用します：記録式👉計算式
  - 子ノードのアドレスを構造体で格納する必要はなく、直接式から配列内のインデックスを計算できます
幅優先探索：木の文字列化
- 表示方法はさまざまで、一般的には最も簡単な方法を使用します。上の図の赤い枠を参照してください：方法 1、方法 2
二分探索木では、中順トラバースは順序通りです
2 つのトラバースから第 3 のトラバース結果を得ることができます
- 前順トラバース / 後順トラバースでルートノードを得ることができ、中順トラバースで子の位置を得ることができます
- 【必須】中順トラバースが必要であり、それだけで子の左右を確定できます

コードデモ#

二分探索木#

構造の定義、操作の定義、トラバース結果の表示

木とノードの操作は別々に実装され、独立してカプセル化されています
挿入操作
- フラグを使用して挿入の状態を取得します
- 二分探索木には重複する値はありません
トラバース操作
- 3 つのトラバースの内部実装は、左右根の順序を交換するだけです
- 二分探索木の中順トラバースは順序通りで、小さい順に並べ替えられます
出力：幅優先探索形式は前述の方法 2 です
❓構造体のノードはすべてポインタ形式で定義されていますが、自分の理解では
- ノードは構造体であり、アドレスを保存するためにポインタを使用すると、スペースを節約できます
- 構造体ポインタでメンバーを呼び出すのは簡単です：->
- ノードを解放するのが簡単です

幅優先探索で木を復元する#

含まれる関係のある問題には、スタックを使用します
スタックにはノードのアドレス [Node *] が格納されます：文字をノードと見なします
変換プロセス
|(|,|)|その他の文字 [アルファベット]|
|:----:|:----:|:----:|:----:|
|【要素をスタックに入れる】
次の ',' までの要素は左の子になります | 次の文字が【右の子】として封装されるかを決定します | スタックトップを記録し、【要素をスタックから取り出す】|①文字を【ノードポインタ型】に封装し、スタックの要素として使用します
②【関係を確定】スタックが空でない場合、この文字が ',' に対してどの位置にあるかに応じて、スタックトップの左の子または右の子になります |

コード

構造の定義、操作の定義：スタック、二分木
【重要】変換のマッチングルール

ヒント#

ノードと構造体の違い
- ノードは実体であり、処理能力を持っています
- 構造体は交差点、マーカーです
- アルゴリズムでは、一般的に点はノードと呼ばれ、データセットでは、各データ要素は要素値が書かれた中央にマークされた四角形で表され、ノードと呼ばれます
- 参考：ノードと構造体の違い-php 中文网
産業界では、赤黒木以外の木はおもちゃのような木構造です