c - 二分木のノードを比較する

Question

2 つのバイナリツリーがある場合、すべてのノードの要素が等しいかどうかを確認するにはどうすればよいでしょうか。

この問題を解決する方法についてのアイデアはありますか?

score 7 · Accepted Answer

並列ツリートラバーサルを実行します。順序を選択します (事前順序、事後順序、順序順)。現在のノードに格納されている値が異なる場合はいつでも、2 つのツリーも異なります。左側のノードの 1 つが null で、もう 1 つがそうでない場合、ツリーは異なります。右のノードについても同様です。

score 2 · Accepted Answer

ノードの順序は重要ですか? この回答では、次の2つのツリーがあると想定しています:

  1       1
 / \     / \
3   2   2   3

比較ではノードの位置と順序が考慮されるため、等しくありません。

いくつかのヒント

2 つの空の木が等しいことに同意しますか?
同一のノード値を持つルートノードのみを持つ 2 つのツリーは等しいことに同意しますか?
このアプローチを一般化できませんか？

もう少し正確に

次のジェネリックツリーを検討してください。

       rootnode(value=V)
           /      \
          /        \
      --------    ------- 
     |  left  |  | right |
     | subtree|  |subtree|
      --------    -------

rootnodeは単一ノードです。2 つの子はより一般的で、バイナリツリーを表します。子は、空、単一ノード、または完全に成長したバイナリツリーのいずれかです。

この表現は、あらゆる種類の空でない二分木を表現するのに十分一般的であることに同意しますか? たとえば、この単純なツリーを私の表現に分解できますか?

この概念を理解していれば、この分解は問題の解決に役立ちます。概念は理解できても、アルゴリズムについてこれ以上進めることができない場合は、ここにコメントしてください。もう少し具体的に説明します :)

score 1 · Accepted Answer

1

Tree Traversalのようなものを使用して、各値を確認できます。

于 2009-06-15T02:03:08.603 に答える

score 0 · Accepted Answer

ツリーがバイナリサーチツリーである場合、事前注文ウォークによって信頼性の高い繰り返し可能なアイテムの注文が生成され、既存の回答が機能します。それらが任意のバイナリツリーである場合は、さらに興味深い問題があり、ハッシュテーブルを調べる必要があります。

score 0 · Accepted Answer

2 つのツリーが同じツリートラバーサルロジックを通過し、出力が一致するようにします。1 つのノードデータでも一致しない場合、ツリーは一致しません。

または、単純なツリートラバーサルロジックを作成し、各再帰でノード値を比較することもできます。

score 0 · Accepted Answer

私の解決策は、2 つのツリーを (レベル順を使用して) 2 つの配列にフラット化し、各項目を反復処理して比較することです。両方の配列が同じ順序であることがわかります。配列のサイズが異なり、2 つのツリーが同じでない場合など、簡単な事前チェックを行うことができます。

Level Order はかなり簡単に実装できます。ウィキペディアのツリートラバーサルに関する記事では、コードを含め、基本的に必要なものはすべて提供されています。質問で効率が求められている場合は、非再帰的なソリューションが最適であり、FIFO リスト (C# 用語のキュー - 私は C プログラマーではありません) を使用して実行されます。

score 0 · Accepted Answer

ポインターと再帰を使用して、ノードが等しいかどうかを確認してから、サブツリーを確認できます。コードは Java 言語で次のように記述できます。

public boolean sameTree(Node root1, Node root2){
//base case :both are empty
if(root1==null && root2==null )
   return true;

if(root1.equals(root2)) {
    //subtrees
    boolean left=sameTree(root1.left,root2.left);
    boolean right=sameTree(root1.right,root2.right);
    return (left && right);
}//end if
else{
    return false;
}//end else

}//sameTree() を終了

c - 二分木のノードを比較する

9 に答える 9

Related

Reference