与えられたプレオーダー トラバーサルから BST を構築するために、プレオーダーで与えられたのと同じ順序で BST に挿入しようとすると、BST が得られます。では、要素を並べ替えたり、他のアルゴリズムを実行したりして、順序を作成する必要はありませんか?
要素を挿入するだけではツリーを構築できないことを示す例はありますか?
質問する
516 次
1 に答える
2
おっしゃる通りです...事前順序トラバーサルによって指定された順序でノードを挿入するだけで、ツリーを再構築できます。
挿入された最初のノードは正しい場所に配置する必要があります。これはルートであり、事前順序トラバーサルは常にルートを最初に配置するためです。preorder トラバーサルに続くのは、左側のサブツリーとそれに続く右側のサブツリーの preorder レイアウトです。左のサブツリー ノードが挿入されると、ルートから左に移動して挿入され、そのサブツリーに同じ手順を再帰的に適用します。右側のサブツリーも同じ方法で再構築されます。必要に応じて、帰納法を使用してこれを正式に証明できます。
お役に立てれば！
于 2013-10-28T16:54:10.180 に答える