3

int の二分探索木を使用して、指定された整数x値より小さいすべての整数のリンク リストを作成します。

私が試したことは？

1)残忍な解決策(非効率)

BSTの 順不同の訪問、Bst のすべての整数のリストにノードを挿入し、x から始まるリストのすべてのノードを解放します。

2)より効率的だが間違っている

検索を行い、x を見つけたら、x を見つけたノードの左側の息子を順番に訪問するリストを作成します。

たとえば、次の BST を考慮すると、明らかに間違っています。

                         10
                        /  \
                       9    11
                      /       \
                     5         15
                    / \        / \
                   1   8      13  19
                             /  \
                            12  14

このソリューションでは、x=15 の場合、{12,13,14} と考えます。x=root に対してのみ機能します。

質問は、どうすればよいですか？

4

3 に答える 3

1

各ノードの親ノードを保存すると、結果リスト内の要素の順序を気にしない限り、より効率的なソリューションを実装できます。

  1. 結果を保存するための新しいリストを作成する
  2. 関心のあるノードを見つける
  3. ステップ2で見つかったノードの左側のサブツリーにあるすべてのノードを、必要なトラバーサル（順序どおり、事前順序など）を使用してリストに追加します。
  4. 手順2で見つかったノードの親から始めて、現在のノードがルートノードまたはその親の左側のノードになるまで、すべての親を調べて各ノードを追加します。
  5. 最後に、ステップ4で見つかったノードの左側にすべての要素を追加します。ここでも、トラバーサルを使用します。
于 2013-02-04T20:41:31.867 に答える
1

疑似コード。vは現在の頂点、ansは回答リスト、someTraversalはツリーを走査してその要素のリストを返すメソッドです。

  1. v := ルート、ans := []
  2. v.value > x の場合
    、 v := v.left、goto 2;
  3. ans.append( someTraversal ( v.left ))
  4. v.value = x の場合、 ans
    を返します。
  5. ans.append( v.value )
  6. v:= v.right;
  7. 2に移動します。
于 2013-02-04T20:19:39.323 に答える
0

以下は、ノードの値が > x の場合に終了する、インオーダー トラバーサルの修正版です。

def nums_less_than(n, x, l=None):
  if l == None:
    l = []
  if n.left:
    nums_less_than(n.left, x, l)
  if n.value < x:
    l.append(n.value)
    if n.right:
      nums_less_than(n.right, x, l)
  return l
于 2015-10-08T04:49:54.943 に答える