0

余分なスペースを使用せずに、バイナリツリーをバイナリ検索ツリーに変換します。次のアルゴリズムを思いつきましたが、機能しません。

BTtoBST(ノード *ルート)

1.ルートが NULL の場合は return

2.else 現在 = ルート

3.if (current->left > current) swap(current->left , current)

4.if (current->right < current) swap(current->right , current)

5.現在=現在->左

6 現在の場合は 3 へ!=NULL でなければ 4 へ

7.現在=現在->右

前もって感謝します

PS:このリンクを見ましたが、あまり役に立ちませんでした!! バイナリ ツリーの変換 -> BST (元のツリー形状を維持)

4

2 に答える 2

1

AVL ツリーhttp://en.wikipedia.org/wiki/AVL_treeのように、サブツリー (ノード コンテンツだけでなく) を含むノードを交換できます。

BST 制約に違反している限りスワップを続け、各スワップ後にルートからディープ ファースト検索を再開します。

于 2011-03-29T07:42:49.647 に答える
0

ツリーのポストオーダー (ボトムアップ) トラバーサルを実行し、アクセスしたノードを取得して BST に挿入します。

「余分なスペースなし」は再帰を排除しますか?

そうでない場合は、次のようになります。

# top level call passes null for bst
bt_to_bst (root, bst)
  # nothing to add to bst; just return it
  if null(root) -> return bst
  # if this is a leaf node, stick it into the BST
  if null(root->left) && null(root->right)
    return bst_insert(bst, root)
  # otherwise add all of left subtree into the bst and then the right tree
  bst = bt_to_bst (root->left, bst);
  return bt_to_bst (root->right, bst);

bt_to_bstフィルタリング操作です。既存の bst を受け取り、指定されたノードが追加された新しい bst を返します。

リーフ ノードを に追加することは安全です。これは、二度とアクセスしないためです。そのため、そのおよびポインタbstを上書きできます。leftright

于 2012-03-28T17:49:46.473 に答える