神刀安全网

Non-recursive program to delete an entire binary tree.

We have discussed recursive implementation to delete an entire binary treehere.

We strongly recommend you to minimize your browser and try this yourself first.

Now how to delete an entire tree without using recursion. This could easily be done with the help of Level Order Tree Traversal . The idea is for each dequeued node from the queue, delete it after queuing its left and right nodes (if any). The solution will work as we are traverse all the nodes of the tree level by level from top to bottom, and before deleting the parent node, we are storing its children into queue that will be deleted later.

/* Non-Recursive Program to delete an entire binary tree. */ #include <bits/stdc++.h> using namespace std;  // A Binary Tree Node struct Node {     int data;     struct Node *left, *right; };  /* Non-recursive function to delete an entire binary tree. */ void _deleteTree(Node *root) {     // Base Case     if (root == NULL)         return;      // Create an empty queue for level order traversal     queue<Node *> q;      // Do level order traversal starting from root     q.push(root);     while (!q.empty())     {         Node *node = q.front();         q.pop();          if (node->left != NULL)             q.push(node->left);         if (node->right != NULL)             q.push(node->right);          free(node);     } }  /* Deletes a tree and sets the root as NULL */ void deleteTree(Node** node_ref) {   _deleteTree(*node_ref);   *node_ref = NULL; }  // Utility function to create a new tree Node Node* newNode(int data) {     Node *temp = new Node;     temp->data = data;     temp->left = temp->right = NULL;      return temp; }  // Driver program to test above functions int main() {     // create a binary tree     Node *root =  newNode(15);     root->left = newNode(10);     root->right = newNode(20);     root->left->left = newNode(8);     root->left->right = newNode(12);     root->right->left = newNode(16);     root->right->right = newNode(25);      //delete entire binary tree     deleteTree(&root);      return 0; }

This article is contributed by Aditya Goel . If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Non-recursive program to delete an entire binary tree.

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址