How to delete a binary search tree from memory?

Question

I have a BST, which is a linked list in C ++. How can I delete all this from memory? Will it be made from a class function?

Answer 1

Just remove the children:

struct TreeNode { TreeNode *l, *r, *parent; Data d; TreeNode( TreeNode *p ) { l = nullptr; r = nullptr; parent = p; } TreeNode( TreeNode const & ) = delete; ~TreeNode() { delete l; // delete does nothing if ptr is 0 delete r; // or recurses if there an object } }; 

or if you use unique_ptr or some that you don’t even need:

 struct TreeNode { unique_ptr< TreeNode > l, r; TreeNode *parent; Data d; TreeNode( TreeNode *p ) { l = nullptr; r = nullptr; parent = p; } TreeNode( TreeNode const & ) = delete; ~TreeNode() = default; }; 

Answer 2

If you have access to the most linked list, this is a piece of cake:

 // Making liberal assumptions about the kind of naming / coding conventions that might have been used... ListNode *currentNode = rootNode; while(currentNode != NULL) { ListNode *nextNode = currentNode->Next; delete currentNode; currentNode = nextNode; } rootNode = NULL; 

If this is a custom implementation of BST, then this may be the way it works internally if it is bound to a specific data structure.

If you do not have access to the internal parts, the response to Potatoswatter must be enabled. Assuming that the BST is configured as they assume, simply deleting the root of the node should automatically delete all allocated memory, as each parent in the tree will delete its children.

If you ask how to manually iterate over a binary tree, then you will perform the following recursive step:

 void DeleteChildren(BSTNode *node) { // Recurse left down the tree... if(node->HasLeftChild()) DeleteChildren(node->GetLeftChild()); // Recurse right down the tree... if(node->HasRightChild()) DeleteChildren(node->GetRightChild()); // Clean up the data at this node. node->ClearData(); // assume deletes internal data // Free memory used by the node itself. delete node; } // Call this from external code. DeleteChildren(rootNode); 

I hope I did not miss this moment and one of this helps.

Answer 3

Perform a postoperative tree traversal (for example, visiting children in front of parents) and delete each node when visiting it.

Regardless of whether this relates to classes, it is entirely up to your implementation.

Answer 4

With limited information provided ....

If you assigned new nodes or malloc (or related functions) to the nodes, then you need to go through all the nodes and release or delete them.

An alternative is to place shared_ptr (and weak_ptr to kill loops) in your distributions - if you do it right, you will not need to free nodes manually

If you used the quality implementation that you chose on the Internet than assuming the classes do not leak, you need not worry about anything.

Answer 5

Use smart pointers and forget about it.