StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>as you need the tree for traversal during delete the idea is to delete on return</p> <pre><code>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 } </code></pre> <p>a very important aspect on recursion is when to stop. i assume that a NULL pointer in your struct indicates that there is no subtree.</p> <p>the strategy is now to go as deep as possible <code>if (t->left) del_tree(t->left);</code> when we reach a NULL pointer on both, left and right we are stranded in a leaf. we now clean the leaf (deleting value) and return. on return <code>delete t->left;</code> is executed, this node has nothing left on the left subtree and continues on its right subtree.</p> <p>here i found a nice image of the <a href="http://www.flickr.com/photos/bjoernknafla/5622204938/" rel="nofollow">traversal</a></p> <hr> <p>the problem of deleting a tree is divided into 3 parts. deleting the left subtree, deleting the right subtree and cleaning up self. the deleting of a subtree (left or right) is very much the same procedure as deleting the tree itself. so you use the same function, this is called recursion.</p> <p>think of deleting a file system structure. you decide for the strategy to delete the 'left' folder structure first, then you delete the subtree 'right' and finally you delete the file 'value'. when during the execution of this strategy you change into a folder (no matter whether left or right) you notice that the problem looks the same. so you apply this strategy again to any folder in the tree.</p> <p>what happens is, that you change into the directory left repeatedly unless there is no more directory in the current one. you delete the file 'value'. then you go back one folder and delete the folder named 'left'. now you look for a folder named 'right', change into it, find no folders, delete file 'value' and return to the previous folder. you delete the now empty 'right' and finally delete the file 'values as well. next is to do a further return (backtracking). and so on.</p> <p>you cannot delete non empty folders during going deeper. you have to delete when retreating.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload