1

2 つの二分探索木が類似しているかどうかを比較する必要があるとします。現在、基本的なアプローチは、ルートが等しいかどうかをチェックし、対応する右と左のサブツリーの等価性を引き続きチェックする再帰的な定式化です。

しかし、二分探索木が同じレベルの順序でトラバーサルしている場合、それらは同じであると述べるのは正しいでしょうか? 別の言い方をすれば、すべての BST には固有のレベル オーダー トラバーサルがありますか?

4

2 に答える 2

1

ええと、私はこの質問を私の友人と話し合ったので、答えは正確には私のものではありません! 、しかし、これが思いついたものです。BSTに対して行うレベル順トラバーサルはソートできるため、特定のBSTのインオーダートラバーサルを取得できます。これで、BST を一意に識別するために使用できる 2 つのトラバーサルが得られます。したがって、すべての BST が固有のレベルのオーダー トラバーサルを持っていると述べることは間違いではありません。

アルゴリズム：

ConstructBST(levelorder[] , int Size)
   1. Declare array A of size n.
   2. Copy levelorder into A
   3. Sort A
   From two traversals A and levelorder of a Binary Search Tree , of which one is inorder, construct the tree.
于 2013-08-30T05:41:31.690 に答える