N 進木の同型性

同型性は、同じ構造または鏡像構造を持つ 2 つのツリーとして定義されます。ミラー構造の場合、左側のノードのデータは常に右側のノードと一致します。たとえば、最も近い鏡像である数値を取り上げ、その逆数が何であるかを確認します。これが同型写像の真の概念です。

この記事では、2 つの異なる二分木が同型であるかどうかを確認します。

N 分木の同型性を例として考えてみましょう-

L は左側のノードを表し、R は右側のノードを表すことに注意してください

左から 2 番目の左パーティションの P ツリーと Q ツリーのミラー構造

これら 2 つの図は、4 つの一致条件 (P と Q のルート ノード) を与えることによって、それらがどのように相互に同型であるかを示しています。

• 左右のノードは一致できます。

• どちらも右ノードと右ノードを一致させることができます。

• 左右のノードの両方を照合できます。

• 右と左のどちらかが一致することはありません。

＃＃＃文法＃＃＃

次の構文はプログラムで使用されます -

リーリー

パラメータ

• struct

  -このキーワードは、構造データ型を表すために使用されます。

• name_of_ Structure

  - 構造に任意の名前を指定します。

構造とは、関連するさまざまな変数を 1 か所に集めたものです。

• ＃＃＃アルゴリズム＃＃＃

'iostream'

というヘッダー ファイルからプログラムを開始します。

• 整数型

  'd'
と初期化されたポインタ変数
• 'l'

  を含む 'tree_node' という構造体を作成しています。 'r'は、それぞれ左と右の子ノードのデータを表します。 ここで、

  'create_node()'
という関数を使用して別の構造を作成します。この関数は、
• 'data'

  というパラメーターを受け取り、ルート (ノードの値) を指定します。同時に、'tree_node' という名前のポインターを作成し、指定されたデータを使用して左右の子ノード ポインターを null に初期化し、ルート ノードを返します。この機能を使って、左の子ノードと右の子ノードのノードを挿入していきます。 ここでは

  'check_isomorphism_tree
という関数を作成しています。これはブール データ型を使用し、2 つの
• tree_node

  ポインター p と q# を受け取ります。 ## を入力パラメータとして使用し、ブール値を返します。その中で、「if ステートメント」を 2 回作成して、p のデータが q のデータと等しいかどうかを確認します。 p と q の両方が null かどうかを確認し、そうであれば、ツリーは同型であるため true を返します。

• p または q のいずれかが null であるかどうかを確認し、null である場合は、2 つのツリーが同型ではないため false を返します。

• 'check_isomorphism_tree'
関数では、論理演算子 "&&" と "||" を使用して、ノード
'p'
• と

  を再帰的にチェックします。 'q ' の左右の子ノードの可能なすべての組み合わせ。 main 関数から開始し、情報を提供する 2 つのツリー ノード "p" と "q" を作成します。

• main 関数では、if ステートメントを使用して

  'check_isomorphism_tree'

  関数を呼び出し、指定されたパラメーター p と q を渡して、これらの整数値が同型であるかどうかを確認します。それらが同型である場合、print ステートメントは「この指定されたノード情報により同型ツリーが生成されます」となり、そうでない場合はその逆になります。

• Example の中国語訳は次のとおりです:

  Example

このプログラムでは、2 つの二分木が同型であるかどうかを確認します。

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

このプログラムでは、N 分木の同型性の概念を理解します。構造を使用してツリー ノードを表す方法と、左-左ノード、右-左ノード、左-右-左ノードなどを使用してツリーを構築する方法を説明しました。次の操作は、ツリーの同型性を満たすのに役立ちます。

以上がN 進木の同型性の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。