Рубрики

Напишите программу для удаления дерева

Чтобы удалить дерево, мы должны пройти все узлы дерева и удалить их один за другим. Итак, какой обход мы должны использовать — Inorder или Preorder или Postorder. Ответ прост — Postorder, потому что перед удалением родительского узла мы должны сначала удалить его дочерние узлы

Мы можем удалить дерево с другими обходами также с дополнительной пространственной сложностью, но зачем нам идти на другие обходы, если у нас есть Postorder, который выполняет работу, не сохраняя ничего в той же сложности времени.

Для следующего дерева узлы удаляются по порядку — 4, 5, 2, 3, 1

Пример дерева

Примечание: в Java происходит автоматическая сборка мусора, поэтому мы можем просто сделать root пустым, чтобы удалить дерево «root = null»;

C ++

// C ++ программа для удаления дерева

   
#include<bits/stdc++.h> 
#include<iostream>

using namespace std; 

  
/ * Узел двоичного дерева содержит данные,
указатель на левого ребенка и
указатель на правого ребенка * /

class node 

    public:

    int data; 

    node* left; 

    node* right; 

      

    / * Конструктор, который выделяет

    новый узел с заданными данными

    и NULL левый и правый указатели. * /

    node(int data)

    {

        this->data = data; 

        this->left = NULL; 

        this->right = NULL; 

    }

}; 

  

  
/ * Эта функция пересекает дерево
в порядке, чтобы удалить каждый
и каждый узел дерева * /

void deleteTree(node* node) 

    if (node == NULL) return

  

    / * сначала удалите оба поддерева * /

    deleteTree(node->left); 

    deleteTree(node->right); 

      

    / * затем удалить узел * /

    cout << "\n Deleting node: " << node->data; 

    free(node); 

  

  
/ * Код водителя * /

int main() 

    node *root = new node(1); 

    root->left     = new node(2); 

    root->right     = new node(3); 

    root->left->left = new node(4); 

    root->left->right = new node(5); 

      

    deleteTree(root); 

    root = NULL; 

  

    cout << "\n Tree deleted "

      

    return 0; 

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

С

// C программа для удаления дерева
#include<stdio.h>
#include<stdlib.h>

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct node 

{

    int data;

    struct node* left;

    struct node* right;

};

  
/ * Вспомогательная функция, которая выделяет новый узел с

   данные даны и NULL левый и правый указатели. * /

struct node* newNode(int data) 

{

    struct node* node = (struct node*)

                           malloc(sizeof(struct node));

  

    node->data = data;

    node->left = NULL;

    node->right = NULL;  

    return(node);

}

  
/ * Эта функция просматривает дерево в почтовом порядке, чтобы

    удалить каждый узел дерева * /

void deleteTree(struct node* node) 

{

    if (node == NULL) return;

  

    / * сначала удалите оба поддерева * /

    deleteTree(node->left);

    deleteTree(node->right);

    

    / * затем удалить узел * /

    printf("\n Deleting node: %d", node->data);

    free(node);

  

  

/ * Программа драйвера для проверки функции deleteTree * /    

int main()

{

    struct node *root = newNode(1); 

    root->left            = newNode(2);

    root->right          = newNode(3);

    root->left->left     = newNode(4);

    root->left->right   = newNode(5); 

    

    deleteTree(root);  

    root = NULL;

  

    printf("\n Tree deleted ");

    

    return 0;

}

Джава

// Java программа для удаления дерева

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    / * Эта функция просматривает дерево в почтовом порядке, чтобы

        удалить каждый узел дерева * /

    void deleteTree(Node node) 

    {

        // В Java автоматическая сборка мусора

        // происходит, поэтому мы можем просто сделать root

        // null для удаления дерева

        root = null;

    }

   

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

    public static void main(String[] args) 

    {

        BinaryTree tree = new BinaryTree();

   

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

   

        / * Вывести все корневые пути дерева ввода * /

        tree.deleteTree(tree.root);

        tree.root = null;

        System.out.println("Tree deleted");

   

    }

}

python3

"" "программа для удаления дерева" ""

  
# Вспомогательная функция, которая выделяет новый
# узел с заданными данными и None
# левый и правый пиры

class newNode: 

  

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

    def __init__(self, key): 

        self.data = key

        self.left = None

        self.right = None

  
"" "Эта функция перебирает дерево в почтовом заказе, чтобы

    удалить каждый узел дерева "" "

def deleteTree( node) :

  

    if (node == None):

        return

  

    "" "сначала удалите оба поддерева" ""

    deleteTree(node.left) 

    deleteTree(node.right) 

      

    "" "затем удалите узел" ""

    print(" Deleting node:", node.data) 

  

  
Код водителя

if __name__ == '__main__':

    root = newNode(1

    root.left = newNode(2

    root.right = newNode(3

    root.left.left = newNode(4)

    root.left.right = newNode(5)

    deleteTree(root) 

    root = None

  

    print("Tree deleted ")

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C #

using System;

  
// C # программа для удаления дерева

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

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree

{

    public Node root;

  

    / * Эта функция просматривает дерево в почтовом порядке, чтобы

        удалить каждый узел дерева * /

    public virtual void deleteTree(Node node)

    {

        // В Java автоматическая сборка мусора

        // происходит, поэтому мы можем просто сделать root

        // null для удаления дерева

        root = null;

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

  

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

  

        / * Вывести все корневые пути дерева ввода * /

        tree.deleteTree(tree.root);

        tree.root = null;

        Console.WriteLine("Tree deleted");

  

    }

}

  

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


Выход:

 Deleting node: 4
 Deleting node: 5
 Deleting node: 2
 Deleting node: 3
 Deleting node: 1
 Tree deleted 

Вышеупомянутая функция deleteTree () удаляет дерево, но не меняет root на NULL, что может вызвать проблемы, если пользователь deleteTree () не меняет root на NULL и устает получать доступ к значениям с помощью корневого указателя. Мы можем изменить функцию deleteTree () так, чтобы она ссылалась на корневой узел, чтобы эта проблема не возникала. Смотрите следующий код.

C ++

// Программа CPP для удаления дерева
#include <bits/stdc++.h>

using namespace std;

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка
и указатель на правого ребенка * /

class node 

    public:

    int data; 

    node* left; 

    node* right; 

}; 

  
/ * Вспомогательная функция, которая выделяет новый узел с
данные даны и NULL левый и правый указатели. * /

node* newNode(int data) 

    node* Node = new node();

  

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

    return(Node); 

  
/ * Эта функция такая же, как deleteTree ()
в предыдущей программе * /

void _deleteTree(node* node) 

    if (node == NULL) return

  

    / * сначала удалите оба поддерева * /

    _deleteTree(node->left); 

    _deleteTree(node->right); 

  

    / * затем удалить узел * /

    cout << "Deleting node: " << node->data << endl; 

    free(node); 

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

void deleteTree(node** node_ref) 

    _deleteTree(*node_ref); 

    *node_ref = NULL; 

  
/ * Код водителя * /

int main() 

    node *root = newNode(1); 

    root->left     = newNode(2); 

    root->right     = newNode(3); 

    root->left->left = newNode(4); 

    root->left->right = newNode(5); 

  

    // Обратите внимание, что мы передаем адрес root здесь

    deleteTree(&root); 

    cout << "Tree deleted "

    return 0; 

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

С

// C программа для удаления дерева
#include<stdio.h>
#include<stdlib.h>

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

  
/ * Вспомогательная функция, которая выделяет новый узел с

   данные даны и NULL левый и правый указатели. * /

struct node* newNode(int data)

{

    struct node* node = (struct node*)

                           malloc(sizeof(struct node));

  

    node->data = data;

    node->left = NULL;

    node->right = NULL;

    return(node);

}

  
/ * Эта функция такая же, как deleteTree () в предыдущей программе * /

void _deleteTree(struct node* node)

{

    if (node == NULL) return;

  

    / * сначала удалите оба поддерева * /

    _deleteTree(node->left);

    _deleteTree(node->right);

  

    / * затем удалить узел * /

    printf("\n Deleting node: %d", node->data);

    free(node);

}

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

void deleteTree(struct node** node_ref)

{

  _deleteTree(*node_ref);

  *node_ref = NULL;

}

  
/ * Программа драйвера для проверки функции deleteTree * /

int main()

{

    struct node *root = newNode(1);

    root->left            = newNode(2);

    root->right          = newNode(3);

    root->left->left     = newNode(4);

    root->left->right   = newNode(5);

  

    // Обратите внимание, что мы передаем адрес root здесь

    deleteTree(&root);

    printf("\n Tree deleted ");

  

    getchar();

    return 0;

}

Джава

// Java программа для удаления дерева

   
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

class Node 

{

    int data;

    Node left, right;

   

    Node(int d) 

    {

        data = d;

        left = right = null;

    }

}

   

class BinaryTree

{

   

    static Node root;

   

    / * Эта функция такая же, как deleteTree () в предыдущей программе * /

    void deleteTree(Node node)

    {

        // В Java автоматическая сборка мусора

        // происходит, поэтому мы можем просто сделать root

        // null для удаления дерева

        root = null;

    }

      

    / * Функция Wrapper, которая удаляет дерево и

       устанавливает корневой узел как ноль * /

    void deleteTreeRef(Node nodeRef)

    {

        deleteTree(nodeRef);

        nodeRef=null;

    }

   

    / * Программа драйвера для проверки функции deleteTree * /

    public static void main(String[] args)

    {

   

        BinaryTree tree = new BinaryTree();

   

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

   

        / * Обратите внимание, что мы передаем здесь корневой узел * /

        tree.deleteTreeRef(root);

        System.out.println("Tree deleted");

   

    }

}

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

python3

# Python3 программа для подсчета всех узлов
# наличие k листьев в поддереве с их корнями

  
# Узел двоичного дерева содержит данные, указатель на
# левый ребенок и указатель на правый ребенок
# Вспомогательная функция, которая выделяет новый узел
# с заданными данными и ни один не осталось и
# правильные указатели

class newNode:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
'' 'Эта функция такая же, как deleteTree ()
в предыдущей программе

def _deleteTree(node):

    if (node == None):

        return

  

    # сначала удалите оба поддерева * /

    _deleteTree(node.left)

    _deleteTree(node.right)

  

    # затем удалите узел * /

    print("Deleting node: ",

                  node.data)

    node = None

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

def deleteTree(node_ref):

    _deleteTree(node_ref[0])

    node_ref[0] = None

  
# Код драйвера

root = [0]

root[0] = newNode(1

root[0].left = newNode(2

root[0].right = newNode(3

root[0].left.left = newNode(4

root[0].left.right = newNode(5

  
# Обратите внимание, что мы передаем адрес
# корень здесь
deleteTree(root) 

print("Tree deleted "

  
# Этот код предоставлен SHUBHAMSINGH10

C #

using System;

  
// C # программа для удаления дерева

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

public class BinaryTree

{

  

    public static Node root;

  

    / * Эта функция такая же, как deleteTree () в предыдущей программе * /

    public virtual void deleteTree(Node node)

    {

        // В Java автоматическая сборка мусора

        // происходит, поэтому мы можем просто сделать root

        // null для удаления дерева

        root = null;

    }

  

    / * Функция Wrapper, которая удаляет дерево и

       устанавливает корневой узел как ноль * /

    public virtual void deleteTreeRef(Node nodeRef)

    {

        deleteTree(nodeRef);

        nodeRef = null;

    }

  

    / * Программа драйвера для проверки функции deleteTree * /

    public static void Main(string[] args)

    {

  

        BinaryTree tree = new BinaryTree();

  

        BinaryTree.root = new Node(1);

        BinaryTree.root.left = new Node(2);

        BinaryTree.root.right = new Node(3);

        BinaryTree.root.left.left = new Node(4);

        BinaryTree.root.left.right = new Node(5);

  

        / * Обратите внимание, что мы передаем здесь корневой узел * /

        tree.deleteTreeRef(root);

        Console.WriteLine("Tree deleted");

  

    }

}

  

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


Выход:

 Deleting node: 4
 Deleting node: 5
 Deleting node: 2
 Deleting node: 3
 Deleting node: 1
 Tree deleted 

Сложность времени: O (n)
Сложность пространства: если мы не учитываем размер стека для вызовов функций, то O (1) в противном случае O (n)

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

Напишите программу для удаления дерева

0.00 (0%) 0 votes