どのようにBSTのデストラクタをC++で実装しますか？

-1

どのようにBSTのデストラクタをC++で実装しますか？私はデストラクタで呼び出される別の関数を作っています。テンプレートBSTです。どのようにBSTのデストラクタをC++で実装しますか？

これはクラス用ですのでコードを入力しないでください。ちょうどロジックまたはいくつかの疑似コードありがとう！

2016-05-21 buttonSmasher96

CComBSTRを参照してください。https://msdn.microsoft.com/en-us/library/zh7x9w3f.aspx –

なぜ関数でパラメータを取ることができませんか？それはかなり珍しい制限のように思えます。 – templatetypedef

私が見たことは、葉に至るまで再帰的な関数を使い、子を削除し、ルートに戻ってポインタをnullにすることです。

function recursiveRelease(root) 
if root!= null 
    if (leftchild) 
    recursiveRelease(leftchild) 
    remove leftchild from tree 
    make pointer to leftchild = nullptr 
    if (rightchild) 
    recursiveRelease(rightchild) 
    remove rightchild from tree 
    make pointer to rightchild = nullptr

その後、ルートが破棄されます。うまくいけば助けて！

出典

2016-05-21 18:20:11

再帰を必要としないBST内のすべてのノードを削除するためのO（n）時間、O（1） - 空間アルゴリズムがあります。

ルートに左の子がない場合、ツリーの右の子へのポインタをキャッシュし、ルートノードを削除してから、正しいサブツリーであったツリーの削除を続行します。

ルートに左の子がある場合は、tree rotationを実行して、ルートの上にある左の子を回転させます。

このプロセスは、ツリー内のすべてのノードを削除し、再帰を必要とせず、一定の余分なスペースしか必要としません。

これは、あなたのヘルパー関数にパラメータを持たせることができないということは本当に奇妙です。それはかなり恣意的な制限のように思えます。それがどうして正確なのか尋ねたいかもしれません。

出典

2016-05-21 18:22:28 templatetypedef

ああ、とてもきれいです。この回答を書いてくれてありがとう。 – blazs

デストラクタをまったく書きたくないと思います。

BSTクラスがルートノードにunique_ptrを格納し、各ノードがその子ノードにunique_ptr-sを格納していることを確認してください。その後、BSTオブジェクトが破棄されると、ツリー全体が自動的に破棄されます。

出典

2016-05-21 18:39:36 stgatilov

どのようにBSTのデストラクタをC++で実装しますか？

答えて

関連する問題