Programa no recursivo para borrar un árbol binario completo

Hemos discutido la implementación recursiva para eliminar un árbol binario completo aquí .
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Ahora, cómo eliminar un árbol completo sin usar la recursividad. Esto podría hacerse fácilmente con la ayuda de Level Order Tree Traversal . La idea es que cada Node fuera de cola de la cola, lo elimine después de poner en cola sus Nodes izquierdo y derecho (si los hay). La solución funcionará a medida que atravesemos todos los Nodes del árbol nivel por nivel de arriba a abajo, y antes de eliminar el Node principal, almacenamos sus elementos secundarios en la cola que se eliminará más tarde.
 

C++

/* 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;
}

Java

/* Non-recursive program to delete the entire binary tree */
import java.util.*;
  
// A binary tree node
class Node 
{
    int data;
    Node left, right;
  
    public Node(int data) 
    {
        this.data = data;
        left = right = null;
    }
}
  
class BinaryTree 
{
    Node root;
  
    /* Non-recursive function to delete an entire binary tree. */
    void _deleteTree() 
    {
        // Base Case
        if (root == null)
            return;
  
        // Create an empty queue for level order traversal
        Queue<Node> q = new LinkedList<Node>();
  
        // Do level order traversal starting from root
        q.add(root);
        while (!q.isEmpty()) 
        {
            Node node = q.peek();
            q.poll();
  
            if (node.left != null)
                q.add(node.left);
            if (node.right != null)
                q.add(node.right);
        }
    }
  
    /* Deletes a tree and sets the root as NULL */
    void deleteTree() 
    {
        _deleteTree();
        root = null;
    }
  
    // Driver program to test above functions
    public static void main(String[] args) 
    {
        // create a binary tree
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(15);
        tree.root.left = new Node(10);
        tree.root.right = new Node(20);
        tree.root.left.left = new Node(8);
        tree.root.left.right = new Node(12);
        tree.root.right.left = new Node(16);
        tree.root.right.right = new Node(25);
  
        // delete entire binary tree
        tree.deleteTree();
    }
}
  
// This code has been contributed by Mayank Jaiswal(mayank_24)

Python3

# Python program to delete an entire binary tree
# using non-recursive approach
  
# A binary tree node
class Node:
      
    # A constructor to create a new node
    def __init__(self, data):
        self.data = data 
        self.left = None
        self.right = None
  
# Non-recursive function to delete an entrie binary tree
def _deleteTree(root):
      
    # Base Case
    if root is None:
        return 
  
    # Create a empty queue for level order traversal
    q = []
  
    # Do level order traversal starting from root
    q.append(root)
    while(len(q)>0):
        node = q.pop(0)
      
        if node.left is not None:
            q.append(node.left)
  
        if node.right is not None:
            q.append(node.right)
  
        node = None
    return node
  
# Deletes a tree and sets the root as None
def deleteTree(node_ref):
    node_ref = _deleteTree(node_ref)
    return node_ref
  
# Driver program to test above function
  
# Create a binary tree
root = Node(15)
root.left = Node(10)
root.right = Node(20)
root.left.left = Node(8)
root.left.right = Node(12)
root.right.left = Node(16)
root.right.right = Node(25)
  
# delete entire binary tree
root = deleteTree(root)
  
  
# This program is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

/* Non-recursive program to delete the entire binary tree */
using System;
using System.Collections.Generic;
  
// A binary tree node
public class Node 
{
    public int data;
    public Node left, right;
  
    public Node(int data) 
    {
        this.data = data;
        left = right = null;
    }
}
  
public class BinaryTree 
{
    Node root;
  
    /* Non-recursive function to
    delete an entire binary tree. */
    void _deleteTree() 
    {
        // Base Case
        if (root == null)
            return;
  
        // Create an empty queue for level order traversal
        Queue<Node> q = new Queue<Node>();
  
        // Do level order traversal starting from root
        q.Enqueue(root);
        while (q.Count != 0) 
        {
            Node node = q.Peek();
            q.Dequeue();
  
            if (node.left != null)
                q.Enqueue(node.left);
            if (node.right != null)
                q.Enqueue(node.right);
        }
    }
  
    /* Deletes a tree and sets the root as NULL */
    void deleteTree() 
    {
        _deleteTree();
        root = null;
    }
  
    // Driver program to test above functions
    public static void Main(String[] args) 
    {
        // create a binary tree
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(15);
        tree.root.left = new Node(10);
        tree.root.right = new Node(20);
        tree.root.left.left = new Node(8);
        tree.root.left.right = new Node(12);
        tree.root.right.left = new Node(16);
        tree.root.right.right = new Node(25);
  
        // delete entire binary tree
        tree.deleteTree();
    }
}
  
// This code has been contributed by 29AjayKumar

Javascript

<script>
/* Non-recursive program to delete the entire binary tree */
  
// A binary tree node
class Node 
{
    constructor(data)
    {
        this.data = data;
        this.left = this.right = null;
    }
}
  
let root;
  
/* Non-recursive function to delete an entire binary tree. */
function _deleteTree() 
{
    // Base Case
        if (root == null)
            return;
    
        // Create an empty queue for level order traversal
        let q = [];
    
        // Do level order traversal starting from root
        q.push(root);
        while (q.length != 0) 
        {
            let node = q.shift();
              
    
            if (node.left != null)
                q.push(node.left);
            if (node.right != null)
                q.push(node.right);
        }
}
  
    /* Deletes a tree and sets the root as NULL */
function deleteTree() 
{
    _deleteTree();
        root = null;
}
  
// Driver program to test above functions
root = new Node(15);
root.left = new Node(10);
root.right = new Node(20);
root.left.left = new Node(8);
root.left.right = new Node(12);
root.right.left = new Node(16);
root.right.right = new Node(25);
  
// delete entire binary tree
deleteTree();
          
// This code is contributed by rag2127
</script>

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *