1

タイトルはそれを要約しています、私はノードを含む配列を持っています。

左右のポインタは与えられていません

4

1 に答える 1

0

私があなたの質問を正しく理解したかどうかはわかりませんが、BSTの順序付けられた後継者は、単に次に高い要素を意味します。この情報が提供されると、複数のBSTを作成することができます。たとえば、[{1,4}、{2,1}、{3,2}、{5,3}]ここで、{a、b}はaがノードであり、bが順序付けられた後続であることを意味します。したがって、ツリーの可能な実装の1つは、4 IPO(読み取りはの親)1とNULL、1 IPO 2とNULL、2 IPO 3とNULL、最後に3IPO5とNULLです。この情報は、配列を1回だけトラバースする必要があるため、O(n)の複雑さで見つけることができます。

于 2013-03-23T12:44:16.323 に答える