data-structures - 二分探索木の一意の順序付け?

Question

値 V の任意のセットが与えられ、値を左から右に挿入してツリーを構築する場合、(最小の高さと最大の高さのツリーを構築するために) これらの値の順序付けが一意であるかどうかを尋ねられたら、それはどういう意味ですか?

ハミルトニアン パスをたどらなければならないということをインターネットで読んだことがありますが、これを学んだことはありません。また、ハミルトニアン パスとは何かもよくわかりません。

私が選択した順序付けが一意の順序付けであるという証拠はありますか?

Answer 1

私は (完全に肯定的ではありませんが) 質問は、同じツリーを生成する BST に値を挿入できる複数の異なる順序があるかどうかを尋ねていると思います。

たとえば、次のツリーを考えてみましょう。

  1
 / \
0   2

このツリーに値を追加してこの結果を生成するには、1、0、2 と 1、2、0 の 2 つの順序があります。

一方、このツリーは次の 1 つの方法でしか形成できません。

1
 \
  2

つまり、最初に 1 を挿入し、次に 2 を挿入する必要があります。

お役に立てれば！