0

ツリーをトラバースし、必要に応じてメモリを削除することにより、ツリーに割り当てられたメモリを復元しようとしています。たとえば、次のツリー構造があるとします。

struct tree
{
   int *value;
   tree *left;
   tree *right;
}

tree *root; //always points to the root of this tree

再帰呼び出しのたびにそれぞれにアクセスしvalue、削除してから次のノード (または のleftいずれかright) に移動する必要があることはわかっていますが、再帰プロセスは非常に直観に反しているように見えます (特に、左に移動する部分または移動する部分)。権利）。

「ルートで何かを行い、再帰的に左を呼び出し、次に再帰的に右を呼び出す」というルールに従おうとしていますが、コードの機能の仕方がわかりにくいです。の不変量を維持するにはどうすればよいrootですか? 誰かがコンセプトを絵で説明できるとしたら、それは素晴らしいことです。

4

2 に答える 2

0

ツリーは、1 つのルートと 2 つのリーフを持ち、各リーフが別のツリーのルートを指しているツリーと考えることができます。

実際、これが「ルートの不変量」を維持する方法です。葉のポインタをたどるとすぐに、他のツリーのルートにたどり着くからです。

root -> branch -> leaf
|
V
branch -> leaf

とも考えられます

root -> tree1
|
V
tree2

これは順番に

root -> (root -> leaf)
|
V
(root -> leaf)

したがって、元のブランチをたどると、再びルートになります。

于 2012-12-09T00:33:29.930 に答える
0

削除中のトラバーサルにツリーが必要なため、アイデアはリターン時に削除することです

void del_tree(tree *t) {

  if (t->left) {
    // there is a left subtree existing. delete it
    del_tree(t->left);  // first go deeper on left side
    // left branch now completely empty
    delete t->left;     // nothing left behind t->left
    t->left=0;          // just in case
  } else {
    // there is no left subtree existing
    // we are in a leaf or in an unbalanced node
  }

  if (t->right) {
    // there is a right subtree existing. delete it
    del_tree(t->right);  // now go deeper on right side
    // right branch now completely empty
    delete t->right;     // nothing left behind t->right
    t->right=0;          // just in case
  } else {
    // there is no rigt subtree existing
    // we are in a leaf or this was an unbalanced node
    // (before we deleted the left subtree)
  }

  // both branches are now completely empty
  // either they were from the beginning (leaf)
  // or we have successfully reduced this node to a leaf
  // now do the node visit

  if (t->value) {
    delete t->value;     // tidy up
    t->value=0;          // just in case
  }
  // now we are completely clean and empty
  // after return t will be deleted
}

void main() {
  tree *my_tree;

  // stuff

  del_tree(my_tree);   // delete the whole tree
  delete my_tree;      // delete the remaining root node
}

再帰の非常に重要な側面は、いつ停止するかです。構造体の NULL ポインターは、サブツリーがないことを示していると思います。

戦略は、左と右の両方で NULL ポインターに到達したときに、可能な限り深く進むことif (t->left) del_tree(t->left); であり、リーフで立ち往生しています。葉をきれいにして (値を削除して)、戻ります。delete t->left;が実行されると、このノードの左側のサブツリーには何も残っておらず、右側のサブツリーに続きます。

ここで、トラバーサルの素敵な画像を見つけました

ツリーを削除する問題は 3 つの部分に分けられます。左のサブツリーを削除し、右のサブツリーを削除して、自分自身をクリーンアップします。サブツリー (左または右) の削除は、ツリー自体の削除とほとんど同じ手順です。同じ関数を使用するので、これは再帰と呼ばれます。

ファイルシステム構造を削除することを考えてください。最初に「左」のフォルダー構造を削除する戦略を決定し、次にサブツリー「右」を削除し、最後にファイル「値」を削除します。この戦略の実行中にフォルダーを変更すると (左右に関係なく)、問題が同じように見えることに気付きます。したがって、この戦略をツリー内の任意のフォルダーに再度適用します。

何が起こるかというと、現在のディレクトリにディレクトリがもうない場合を除き、残っているディレクトリに繰り返し変更します。ファイル「値」を削除します。次に、1 つのフォルダーに戻り、「left」という名前のフォルダーを削除します。ここで、「right」という名前のフォルダーを探してそこに移動し、フォルダーが見つからないので、ファイル「value」を削除して、前のフォルダーに戻ります。空になった「権利」を削除し、最後にファイルの「値」も削除します。次は、さらに戻る (バックトラック) ことです。等々。

深く掘り下げている間、空でないフォルダを削除することはできません。撤退するときは削除する必要があります。

于 2012-12-09T00:17:17.677 に答える