Рубрики

Нерекурсивная программа для удаления всего двоичного дерева

Мы обсудили рекурсивную реализацию для удаления всего двоичного дерева здесь .

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Теперь, как удалить все дерево без использования рекурсии. Это легко сделать с помощью обхода дерева уровней . Идея заключается в том, чтобы для каждого удаленного узла из очереди удалить его после постановки в очередь его левого и правого узлов (если они есть). Решение будет работать, когда мы пересекаем все узлы уровня дерева по уровням сверху вниз, и перед удалением родительского узла мы сохраняем его дочерние элементы в очередь, которая будет удалена позже.

C ++

/ * Нерекурсивная программа для удаления всего двоичного дерева. * /
#include <bits/stdc++.h>

using namespace std;

  
// Узел двоичного дерева

struct Node

{

    int data;

    struct Node *left, *right;

};

  
/ * Нерекурсивная функция для удаления всего двоичного дерева. * /

void _deleteTree(Node *root)

{

    // Базовый вариант

    if (root == NULL)

        return;

  

    // Создать пустую очередь для прохождения порядка уровней

    queue<Node *> q;

  

    // Делаем прохождение порядка уровня, начиная с корня

    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);

    }

}

  
/ * Удаляет дерево и устанавливает корень как NULL * /

void deleteTree(Node** node_ref)

{

  _deleteTree(*node_ref);

  *node_ref = NULL;

}

  
// Сервисная функция для создания нового дерева Node

Node* newNode(int data)

{

    Node *temp = new Node;

    temp->data = data;

    temp->left = temp->right = NULL;

  

    return temp;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // создаем двоичное дерево

    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);

  

    // удаляем все двоичное дерево

    deleteTree(&root);

  

    return 0;

}

Джава

/ * Нерекурсивная программа для удаления всего двоичного дерева * /

import java.util.*;

  
// Узел двоичного дерева

class Node 

{

    int data;

    Node left, right;

  

    public Node(int data) 

    {

        this.data = data;

        left = right = null;

    }

}

  

class BinaryTree 

{

    Node root;

  

    / * Нерекурсивная функция для удаления всего двоичного дерева. * /

    void _deleteTree() 

    {

        // Базовый вариант

        if (root == null)

            return;

  

        // Создать пустую очередь для прохождения порядка уровней

        Queue<Node> q = new LinkedList<Node>();

  

        // Делаем прохождение порядка уровня, начиная с корня

        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);

        }

    }

  

    / * Удаляет дерево и устанавливает корень как NULL * /

    void deleteTree() 

    {

        _deleteTree();

        root = null;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args) 

    {

        // создаем двоичное дерево

        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);

  

        // удаляем все двоичное дерево

        tree.deleteTree();

    }

}

  
// Этот код предоставлен Mayank Jaiswal (mayank_24)

питон

# Python программа для удаления всего двоичного дерева
# используя нерекурсивный подход

  
# Узел двоичного дерева

class Node:

      

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
# Нерекурсивная функция для удаления двоичного дерева записей

def _deleteTree(root):

      

    # Базовый вариант

    if root is None:

        return 

  

    # Создать пустую очередь для прохождения порядка уровней

    q = []

  

    # Делать прохождение порядка уровней, начиная с корня

    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

  
# Удаляет дерево и устанавливает корень как None

def deleteTree(node_ref):

    node_ref = _deleteTree(node_ref)

    return node_ref

  
# Программа драйвера для проверки вышеуказанной функции

  
# Создать двоичное дерево

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)

  
# удалить все двоичное дерево

root = deleteTree(root)

  

  
# Эта программа предоставлена Nikhil Kumar Singh (nickzuck_007)

C #

/ * Нерекурсивная программа для удаления всего двоичного дерева * /

using System;

using System.Collections.Generic;

  
// Узел двоичного дерева

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;

  

    / * Нерекурсивная функция для

    удалить все двоичное дерево. * /

    void _deleteTree() 

    {

        // Базовый вариант

        if (root == null)

            return;

  

        // Создать пустую очередь для прохождения порядка уровней

        Queue<Node> q = new Queue<Node>();

  

        // Делаем прохождение порядка уровня, начиная с корня

        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);

        }

    }

  

    / * Удаляет дерево и устанавливает корень как NULL * /

    void deleteTree() 

    {

        _deleteTree();

        root = null;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void Main(String[] args) 

    {

        // создаем двоичное дерево

        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);

  

        // удаляем все двоичное дерево

        tree.deleteTree();

    }

}

  
// Этот код предоставлен 29AjayKumar

Эта статья предоставлена Aditya Goel . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Нерекурсивная программа для удаления всего двоичного дерева

0.00 (0%) 0 votes