バイナリツリーのノードを比較する

Question

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

どのようにこの問題を解決するためのアイデアですか？

Answer 1

あなたは、並行したツリー走査を行います - あなたの注文（先行予約、後予約、順不同）を選択します。現在のノードに格納されている値がいつでも変わる場合は、2つのツリーも同じです。 1つの左のノードがヌルであり、もう1つのノードがヌルでない場合、ツリーは異なります。右ノードの場合は同上。

Answer 2

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

Answer 3

木がバイナリの場合は、検索ツリーです。そのため、事前予約の散歩では、信頼性の高い繰り返し可能なアイテムの順序が生成されるため、既存の回答が機能します。それらが任意のバイナリツリーであれば、はるかに興味深い問題があり、hash tablesを調べる必要があります。

Answer 4

ノードの順序は重要ですか？私は次の二つの木、この答えを想定しています：ノード位置及び順序は、比較のために考慮されているので

1  1 
/\ /\ 
3 2 2 3 

は、等しくありません。

いくつかのヒント

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

もう少し正確なので

この一般的なツリーを考えてみましょう：

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

ルートノードは、単一のノードです。 2人の子供はより一般的で、バイナリツリーを表します。子ノードは空でも、単一のノードでも、完全に拡張されたバイナリツリーでもかまいません。

この表現は、空でないバイナリツリーを表すのに十分な汎用性があることに同意しますか？あなたは、私の表現にthis simple treeを分解することができますか？

この概念を理解すれば、この分解は問題の解決に役立ちます。あなたがコンセプトを理解しているが、アルゴリズムでそれ以上のことはできないなら、ここでコメントしてください。もう少し具体的になるでしょう:)

Answer 5

私の解決策は2つのツリーを2つの配列に平坦化することですレベルの順序）、各項目を反復して比較します。両方の配列が同じ順序であることは分かっています。配列のサイズが異なり、2つのツリーが同じでない場合など、簡単な事前チェックができます。

レベルオーダーは非常に簡単です。tree traversalのウィキペディアの記事では、基本的にコードを含め、必要なものすべてを提供しています。問題で効率が求められる場合は、非再帰的な解決策が最適であり、FIFOリスト（C＃の用語でキュー - 私はCプログラマではない）を使用して実行するのが最適です。

Answer 6

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

単純なツリートラバーサルロジックを作成して、各再帰でノード値を比較するだけです。

Answer 7

ノードが等しいかどうかを確認するためにポインタと再帰を使用し、サブツリーをチェックすることができます。コードは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 

} //タグが質問に言及したようにCコードを書く端sameTree（）

Answer 8

。

int is_same(node* T1,node* T2) 
{ 
    if(!T1 && !T2) 
    return 1; 
    if(!T1 || !T2) 
    return 0; 

    if(T1->data == T2->data) 
    { 
     int left = is_same(T1->left,T2->left); 
     int right = is_same(T1->right,T2->right); 
     return (left && right); 
    } 
    else 
    return 0; 
} 

構造体も値も考慮します。

Answer 9

2つのバイナリツリーノードが等しい（同じ値と同じ構造）かどうかを確認するには、1行のコードで十分です。

bool isEqual(BinaryTreeNode *a, BinaryTreeNode *b) 
{ 
    return (a && b) ? (a->m_nValue==b->m_nValue && isEqual(a->m_pLeft,b->m_pLeft) && isEqual(a->m_pRight,b->m_pRight)) : (a == b); 
}