7

私が読んでいる本では、バイナリ ツリーBがバイナリ ツリーのサブツリーであるかどうかを確認する方法の 1 つは、両方のツリーのおよび文字列 (各ツリーの順序と順序を表す文字列)Aを作成し、andの部分文字列は の部分文字列です。inorder文字列とpreorder 文字列の両方で部分文字列の一致を確認する必要があると主張していることに注意してください。inorderpreorderinorder_Binorder_A preorder_Bpreorder_A

inorder 文字列と preorder 文字列の両方で部分文字列の一致を確認する必要は本当にありますか? どちらかを確認するだけで十分ではないでしょうか。誰かが私が間違っていることを証明する例を提供できますか (つまり、本の主張が正しいことを証明します)? 2 つのツリーが等しくない例を思いつきませんでしたが、preorder または inorder 文字列は一致します。

4

4 に答える 4

7

AとBをノードとする2つの2つのノードツリーについて考えてみます。ツリー1には、ルートとしてBがあり、左の子としてAがあります。ツリー2には、ルートとしてAがあり、右の子としてBがあります。順序のないトラバーサルは一致しますが、ツリーは異なります。

于 2013-01-11T22:58:17.417 に答える
1

木が二分探索木ではなく単純な二分木である場合、両方が必要だと思います。ノードの任意のセットは、予約注文表記にすることができます。二分木 a,b,c,d,e,f,g,h があり、サブツリーが cdef であるとします。サブツリー cde と別のサブツリー fg を持つ別のツリーを作成できます。違いを知る方法はありません。

ただし、二分探索木である場合は、順序を指定する必要はありません。

ついでに、面白いアルゴリズムの問​​題があります: 与えられたプレオーダー表記から、それを満たす二分木の数を見つけてください。

于 2013-01-11T23:03:41.930 に答える
0

user1952500の回答の補足として：それが二分探索木の場合、事前注文または事後注文のみが一意にすることができますが、順序のみはできません。例えば：

  5
 / \
3   6

inorder: 3-5-6 ただし、別の二分探索木が同じ順序を持つ場合があります。

3
 \
  5
   \
    6

また、 preorder+inorder+string_comparison は、2 つのツリーが同一かどうかを確認するためにのみ機能すると思います。ツリーが別のツリーのサブツリーであるかどうかを確認できません。例を確認するには、プレオーダー文字列とインオーダー文字列を使用して、バイナリ ツリーが別のバイナリ ツリーのサブツリーであるかどうかを判断するを参照してください。

于 2013-12-30T05:08:22.597 に答える