コンピュータの木は現実の形態とは逆で、逆さまの木です～
コース内容#
木#
- 木の構成：ノード + 辺
- ノード 👉 集合、辺 👉 関係
- 根ノード：全集；子ノード：部分集合
- 根ノードのすべての子ノードの集合の和 = 全集
- 【思想】大きな問題を木に抽象化し、小さな問題を子ノードに抽象化
構造定義#
【ノード + 辺】
-
-
一叉木はリンクリスト構造で、分岐が 1 つの木構造
-
三叉木の場合は、リンクリストの next ポインタを next [3] 配列に変えるだけです
属性、性質#
-
-
深さ、高さ
- 木の深さと高さは同じ値：最大層数
- ノードの深さと高さは異なる
- 深さ：根ノードから数えて、そのノードは何層目か
- 高さ：最深の層から数えて、そのノードは何層目か
-
度：いくつの子ノードがいるか
-
⭐【重要な公式】ノード数 = 辺数 + 1
二分木#
- 二進法は任意の進法に変換でき、二分木も同様です
- まずは簡単
- すべての木構造を表現できます
- 方法：左の子、右の兄弟法、別名十字リンクリスト法
-
- 上から下、左から右に、ノードの子は左に、隣接する兄弟は右に配置します
- 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- ウィキペディア
-
- 完全二分木：最後の層の最右側にいくつかの連続ノードが欠けることができるが、他の場所はすべて満たされている
- 満二分木：度が 0 または 2 である
- 完璧な二分木：すべての葉ノードが同じ層にある
- PS：中国版では完全二分木と満二分木のみを区別し、満二分木の定義は国際版の完璧な二分木と同じです
-
- 完全二分木の特徴 [完璧な二分木も同様に満たす]
- 番号 i のノードの左右の子の番号はそれぞれ 2 * i、2 * i + 1 です
- 連続した空間（配列）を使用して保存し、アルゴリズムの最適化に利用：記録式👉計算式
- 子ノードのアドレスを構造体で保存する必要がなく、公式を通じて配列内のインデックスを直接計算できます
- 一般表：木の文字列化
-
-
- 多くの表現方法があり、一般的に簡単な方法を使用します。上の図の赤枠：方法一、方法二
-
- 二分探索木の場合、中順遍歴は順序通りです
- 二つの遍歴から三つ目の遍歴結果を得ることができます
- 前順遍歴 / 後順遍歴で根ノードを得て、中順遍歴で左右の子の位置を得ます
- 【必須】中順遍歴が必要で、これだけが子の左右を確定できます
コードデモ#
二分探索木#
構造定義、構造操作、遍歴結果表示
-
-
-
-
木とノードの操作は分けて実装され、独立してカプセル化されています
-
挿入操作
- フラグを使用して挿入状態を取得
- 二分探索木には重複値がありません
-
遍歴操作
- 三つの遍歴の内部実装は、左右根の訪問順序を入れ替えるだけです
- 二分探索木の中順遍歴は順序通りで、小から大にソートされます
-
出力：一般表形式は前述の第二の方法です
-
❓構造体内のノードはすべてポインタ形式として定義されており、自分の理解は
- ノードは構造体で、ポインタでアドレスを保存する方がスペースを節約できます
- 構造体ポインタでメンバーを呼び出す方が便利です：->
- ノードを free するのが便利です
一般表から二分木を復元#
-
-
完全包含関係の問題は、スタックを使用します
-
スタックにノードアドレス [Node *] を保存します：一般表の文字をノードと見なします
-
変換プロセス
|(|,|)|他の文字【アルファベット】|
|:----:|:----:|:----:|:----:|
|【要素をスタックに入れる】
次の ',' 前の要素は左の子 | 次の文字で封装される要素は【右の子】| スタックのトップを記録し、【要素をポップ】|①文字を【封装】してノードポインタ型にし、スタックの要素として使用
②【関係を確定】スタックが空でない場合、その文字が ',' に対してどの位置にあるかに基づいて、スタックのトップ要素の左の子または右の子になります |
コード
-
-
-
-
-
-
構造定義、操作定義：スタック、二分木
-
【重要】変換のマッチングルール
ヒント#
- ノードと結点の違い
- ノードは一つの実体で、処理能力を持っています
- 結点は交差点、マークです
- アルゴリズムの点は一般的に結点と呼ばれ、データ集合の各データ要素は中間に要素値が記載されたボックスで表され、これを結点と呼びます
- 参考ノードと結点の違い-php 中国網
- 工業界では、赤黒木を除いて、他の木はおもちゃレベルの木構造です
-
