5

並べ替えられたリンク リストから BST を作成したいと考えています。私は問題を再帰的に解決しましたが、問題の複雑さを変えずに同じ問題の反復的な解決策を書く方法を考えていました。

[編集]

注: 独自のスタックを実装したくありません。

[編集2]

自分自身を再帰的に呼び出す関数は f です。疑似コードを以下に示します。からのヘッドポインタで f を呼び出しますmain

node * f(int start_index, int end_index, node *ptr) {
     if ( start>end) return NULL
     middle_index = start_index + (end_index-start_index)/2
     node *l_child = f(start_index, middle_index-1, ptr)
     initialize parent with ptr's value 
     parent->left = l_child
     ptr = ptr->next
     parent->right = f(middle_index+1, end, ptr)
     return parent
}
4

2 に答える 2

0

事前に次のようにしたいと仮定すると、大まかに次のようになります。

    _______
   /       \
  / \     / \
 /   \   /   \
/ \ / \ / \ /
1 2 3 4 5 6 7

次に、構造を明示的に解くことができます。この場合、ある整数 N に対して長さ L<2 Nのリストの場合、すべてのノードを作成し、いくつかの葉を「null」のままにしておく (または、それらのノードを作成することさえしない) と仮定すると、合計数は次のようになります。ツリー内のノードは (2*2 N )-1に等しくなります。ノードは次のようになります。

    12345678
   /       \
  1234    5678
  / \     / \
 12  34  56  78
/ \ / \ / \ / \
1 2 3 4 5 6 7

ノードのサイズについて言及したのは、それがどのように処理を進めるかについての洞察を与えてくれるはずだからです: 列挙する何らかの方法があるはず{1,2}->12, {3,4}->34, {12,34}->1234, ...です。続行する 1 つの方法は、ノードのグループ化を下から開始することです。たとえば、これを N (3) 回のパスで行うことができます。

step 1:    1  2   3  4    5  6   7
step 2:   (1  2) (3  4)  (5  6) (7   )
step 3:  ((1  2) (3  4))((5  6) (7   ))
step 4: (((1  2) (3  4))((5  6) (7   )))

もう 1 つの方法は、スタックを使用して、より高いレベルのノードをグループ化して追跡することです。

もう 1 つの方法は、構造の明示的な式を作成することです。7 つのノードを作成し、それらの子を次のように設定します{1,2}, {3,4}, {5,6}, {7,null}, {12,34}, {56,78}, {1234,5678}。特に、線形スキームでノードにインデックスを付ける場合、このパターンは次のようになります9={1,2}, 10={3,4}, 11={5,6}, 12={7,null}, 13={9,10}, 14={11,12}, 15={13,14}。単純にインクリメントすると、バランスのとれた二分木の正確なパターンが得られるように見えます。これにより、追加のメモリは使用されません。

于 2012-08-29T08:01:19.700 に答える
-1

スタックをシミュレートすることで、再帰的なソリューションを「反復的な」ソリューションに変換できます。

于 2012-08-29T05:38:19.720 に答える