Рубрики

Двойное поддерево в двоичном дереве | SET 2

Для заданного двоичного дерева задача состоит в том, чтобы проверить, содержит ли двоичное дерево дублированное поддерево размера два или более.

Input:
               A
             /   \ 
           B       C
         /   \       \    
        D     E       B     
                     /  \    
                    D    E
Output: Yes
    B     
  /   \    
 D     E
is the duplicate sub-tree.

Input:
               A
             /   \ 
           B       C
         /   \
        D     E
Output: No

Подход: подход, основанный на DFS, обсуждался здесь . Очередь может использоваться для обхода дерева способом BFS . Обходя узлы, нажмите на узел вместе с его левым и правым дочерними элементами на карте, и если в какой-либо точке карта содержит дубликаты, то дерево содержит дубликаты поддеревьев. Например, если узлом является A, а его дочерние элементы — B и C, то ABC будет перемещен на карту. Если в какой-то момент ABC нужно нажать снова, тогда дерево содержит дубликаты поддеревьев.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Структура для узла двоичного дерева

struct Node {

    char key;

    Node *left, *right;

};

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

Node* newNode(char key)

{

    Node* node = new Node;

    node->key = key;

    node->left = node->right = NULL;

    return node;

}

  
unordered_set<string> subtrees;

  
// Функция, которая возвращает true, если
// дерево содержит дублированное поддерево
// размером 2 или больше

bool dupSubUtil(Node* root)

{

  

    // Для хранения поддеревьев

    set<string> subtrees;

  

    // Используется для обхода дерева

    queue<Node*> bfs;

    bfs.push(root);

  

    while (!bfs.empty()) {

        Node* n = bfs.front();

        bfs.pop();

  

        // Для хранения слева и справа

        // потомки текущего узла

        char l = ' ', r = ' ';

  

        // Если у узла есть левый потомок

        if (n->left != NULL) {

            l = n->left->key;

  

            // Push данные левого узла

            bfs.push(n->left);

        }

  

        // Если у узла есть правильный потомок

        if (n->right != NULL) {

            r = n->right->key;

  

            // Подтолкнуть данные правого узла

            bfs.push(n->right);

        }

  

        string subt;

        subt += n->key;

        subt += l;

        subt += r;

  

        if (l != ' ' || r != ' ') {

  

            // Если это количество поддеревьев больше 0

            // это означает, что дубликат существует

            if (!subtrees.insert(subt).second) {

                return true;

            }

        }

    }

    return false;

}

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

int main()

{

    Node* root = newNode('A');

    root->left = newNode('B');

    root->right = newNode('C');

    root->left->left = newNode('D');

    root->left->right = newNode('E');

    root->right->right = newNode('B');

    root->right->right->right = newNode('E');

    root->right->right->left = newNode('D');

  

    cout << (dupSubUtil(root) ? "Yes" : "No");

  

    return 0;

}

Джава

// Java реализация подхода

import java.util.*;

class GFG

{

  
// Структура для узла двоичного дерева

static class Node 

{

    char key;

    Node left, right;

};

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

static Node newNode(char key)

{

    Node node = new Node();

    node.key = key;

    node.left = node.right = null;

    return node;

}

  

static HashSet<String> subtrees = new HashSet<String>();

  
// Функция, которая возвращает true, если
// дерево содержит дублированное поддерево
// размером 2 или больше

static boolean dupSubUtil(Node root)

{

  

    // Для хранения поддеревьев

    // HashSet <String> subtrees;

  

    // Используется для обхода дерева

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

    bfs.add(root);

  

    while (!bfs.isEmpty())

    {

        Node n = bfs.peek();

        bfs.remove();

  

        // Для хранения слева и справа

        // потомки текущего узла

        char l = ' ', r = ' ';

  

        // Если у узла есть левый потомок

        if (n.left != null

        {

            l = n.left.key;

  

            // Push данные левого узла

            bfs.add(n.left);

        }

  

        // Если у узла есть правильный потомок

        if (n.right != null

        {

            r = n.right.key;

  

            // Подтолкнуть данные правого узла

            bfs.add(n.right);

        }

  

        String subt = "";

        subt += n.key;

        subt += l;

        subt += r;

  

        if (l != ' ' || r != ' ')

        {

  

            // Если это количество поддеревьев больше 0

            // это означает, что дубликат существует

            if (!subtrees.contains(subt))

            {

                return true;

            }

        }

    }

    return false;

}

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

public static void main(String[] args) 

{

    Node root = newNode('A');

    root.left = newNode('B');

    root.right = newNode('C');

    root.left.left = newNode('D');

    root.left.right = newNode('E');

    root.right.right = newNode('B');

    root.right.right.right = newNode('E');

    root.right.right.left = newNode('D');

    if (dupSubUtil(root))

        System.out.println("Yes");

    else

        System.out.println("No"); 

}

  
// Этот код предоставлен Принчи Сингхом

C #

// C # реализация подхода

using System;

using System.Collections.Generic;

  

class GFG

{

  
// Структура для узла двоичного дерева

public class Node 

{

    public char key;

    public Node left, right;

};

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

static Node newNode(char key)

{

    Node node = new Node();

    node.key = key;

    node.left = node.right = null;

    return node;

}

  

static HashSet<String> subtrees = new HashSet<String>();

  
// Функция, которая возвращает true, если
// дерево содержит дублированное поддерево
// размером 2 или больше

static bool dupSubUtil(Node root)

{

  

    // Для хранения поддеревьев

    // HashSet <String> subtrees;

  

    // Используется для обхода дерева

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

    bfs.Enqueue(root);

  

    while (bfs.Count != 0)

    {

        Node n = bfs.Peek();

        bfs.Dequeue();

  

        // Для хранения слева и справа

        // потомки текущего узла

        char l = ' ', r = ' ';

  

        // Если у узла есть левый потомок

        if (n.left != null

        {

            l = n.left.key;

  

            // Push данные левого узла

            bfs.Enqueue(n.left);

        }

  

        // Если у узла есть правильный потомок

        if (n.right != null

        {

            r = n.right.key;

  

            // Подтолкнуть данные правого узла

            bfs.Enqueue(n.right);

        }

  

        String subt = "";

        subt += n.key;

        subt += l;

        subt += r;

  

        if (l != ' ' || r != ' ')

        {

  

            // Если это количество поддеревьев больше 0

            // это означает, что дубликат существует

            if (!subtrees.Contains(subt))

            {

                return true;

            }

        }

    }

    return false;

}

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

public static void Main(String[] args) 

{

    Node root = newNode('A');

    root.left = newNode('B');

    root.right = newNode('C');

    root.left.left = newNode('D');

    root.left.right = newNode('E');

    root.right.right = newNode('B');

    root.right.right.right = newNode('E');

    root.right.right.left = newNode('D');

    if (dupSubUtil(root))

        Console.WriteLine("Yes");

    else

        Console.WriteLine("No"); 

}
}

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

Выход:

Yes

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

Двойное поддерево в двоичном дереве | SET 2

0.00 (0%) 0 votes