二分木内の二等辺三角形の数

バイナリ ツリーは、各ノードが最大 2 つの子ノードを持つことができるデータ構造です。これらの子は、それぞれ左の子と右の子と呼ばれます。親の配列表現が与えられたとします。それを使用してバイナリ ツリーを作成する必要があります。二分木には複数の二等辺三角形が含まれる場合があります。この二分木で可能な二等辺三角形の総数を見つけなければなりません。

この記事では、C でこの問題を解決するためのいくつかの手法を検討します。

質問を理解する

親配列を提供します。配列インデックスがツリー ノードの値を形成し、配列内の値がその特定のインデックスの親ノードを与えるように、それをバイナリ ツリーの形式で表す必要があります。

-1 は常にルートの親ノードであることに注意してください。以下に、配列とそのバイナリ ツリー表現を示します。

リーリー

バイナリ ツリー -

どの二分木でも、3 種類の二等辺三角形を使用できます -

• 左二等辺三角形 − この三角形では、頂点は left 親ノードの子ノードと底辺(二等辺三角形の両辺)を形成する頂点が頂点の左側の子ノードとなります。子ノードは直接的または間接的です。上のツリーには、そのような二等辺三角形が 2 つあります - (2, 6, 3)、(3, 7, 1)。

• 右二等辺三角形 − この三角形の頂点は right親の子ですが、ベースを形成する頂点は頂点の正しい子です。子供は直接的または間接的です。上のツリーには、そのような二等辺三角形が 1 つだけあります (4、1、8)。

• 平衡二等辺三角形 − この三角形では、底辺を形成する頂点が頂点ノードの左右の子ノードです。上のツリーには、そのような二等辺三角形が 5 つあります (1, 3, 4)、(3, 2, 7)、(4, 8, 9)、(2, 5, 6)、(1, 2, 9)

したがって、上記の二分木には、合計 8 個の二等辺三角形 が存在します。

深さ優先検索を使用したトラバーサル

深さ優先検索 (DFS) は、ツリーのすべてのノードを深さ方向に走査する方法です。ルート ノードから開始され、各ブランチに移動し、その後バックトラックします。

• まず、DFS を使用してバイナリ ツリーの各ノードを走査し、各ノードが互いに隣接して表現されるようにグラフに変換します。これにより、トラバースが容易になります。

• 各ノードについて、子ノードがあるかどうかを確認します。確認後、sort(node[x].begin(), node[x].end()) 関数を使用して並べ替えます。

• 次に、現在のノードが対応する親ノードの左または右の後継ノードであるかどうかを確認します。バイナリ ツリーのすべてのノードで DFS 関数を再帰的に使用します。

• 現在のノードに 2 つの子がある場合 (直接的または間接的に)、それらの間のエッジを計算することで二等辺三角形が存在する可能性をチェックします。以下のコードにある graph 関数を使用して、それらの間のエッジを見つけます。

• 最後に、さまざまな位置にあるすべての可能な三角形を合計することで、二等辺三角形の総数を計算します。

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

親配列が与えられた場合に、二分木内の正三角形の総数を見つける方法について説明しました。これは、二分木を走査できる深さ優先検索を使用することで実現できます。

以上が二分木内の二等辺三角形の数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。