Рубрики

Проверить, является ли двоичное дерево поддеревом другого двоичного дерева | Комплект 1

Учитывая два двоичных дерева, проверьте, является ли первое дерево поддеревом второго. Поддерево дерева T — это дерево S, состоящее из узла в T и всех его потомков в T. Поддерево, соответствующее корневому узлу, — это все дерево; поддерево, соответствующее любому другому узлу, называется правильным поддеревом.

Например, в следующем случае дерево S является поддеревом дерева T.

        Tree 2
          10  
        /    \ 
      4       6
       \
        30


        Tree 1
              26
            /   \
          10     3
        /    \     \
      4       6      3
       \
        30

Решение: Пройдите по дереву T в порядке предварительного заказа. Для каждого посещенного узла в обходе, посмотрите, совпадает ли поддерево с этим узлом в корне.

Ниже приводится реализация для этого.

C ++

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

using namespace std;

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

class node 

    public:

    int data; 

    node* left; 

    node* right; 

}; 

  
/ * Утилита для проверки
ли деревья с корнями как root1 и
root2 идентичны или нет * /

bool areIdentical(node * root1, node *root2) 

    / * базовые случаи * /

    if (root1 == NULL && root2 == NULL) 

        return true

  

    if (root1 == NULL || root2 == NULL) 

        return false

  

    / * Проверьте, являются ли данные обоих корней

    так же и данные слева и справа

    поддеревья также одинаковы * /

    return (root1->data == root2->data && 

            areIdentical(root1->left, root2->left) && 

            areIdentical(root1->right, root2->right) ); 

  

  
/ * Эта функция возвращает true, если S
является поддеревом T, иначе false * /

bool isSubtree(node *T, node *S) 

    / * базовые случаи * /

    if (S == NULL) 

        return true

  

    if (T == NULL) 

        return false

  

    / * Проверить дерево с корнем в качестве текущего узла * /

    if (areIdentical(T, S)) 

        return true

  

    / * Если дерево с корнем в качестве текущего

    узел не совпадает, попробуйте влево

    и правильные поддеревья по одному * /

    return isSubtree(T->left, S) || 

        isSubtree(T->right, S); 

  

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

node* newNode(int data) 

    node* Node = new node(); 

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

    return(Node); 

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

int main() 

    // ДЕРЕВО 1

    / * Построить следующее дерево

            26

            / /

        10 3

        ///

    4 6 3

    /

        30

    * /

    node *T = newNode(26); 

    T->right         = newNode(3); 

    T->right->right = newNode(3); 

    T->left         = newNode(10); 

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

    T->left->left->right = newNode(30); 

    T->left->right     = newNode(6); 

  

    // ДЕРЕВО 2

    / * Построить следующее дерево

        10

        / /

    4 6

    /

        30

    * /

    node *S = newNode(10); 

    S->right     = newNode(6); 

    S->left     = newNode(4); 

    S->left->right = newNode(30); 

  

  

    if (isSubtree(T, S)) 

        cout << "Tree 2 is subtree of Tree 1"

    else

        cout << "Tree 2 is not a subtree of Tree 1"

  

    return 0; 

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

С

#include <stdio.h>
#include <stdlib.h>

  
/ * Узел двоичного дерева имеет данные, левый и правый дочерние элементы * /

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

  
/ * Утилита для проверки наличия деревьев с корнями в качестве root1 и

   root2 идентичны или нет * /

bool areIdentical(struct node * root1, struct node *root2)

{

    / * базовые случаи * /

    if (root1 == NULL && root2 == NULL)

        return true;

  

    if (root1 == NULL || root2 == NULL)

        return false;

  

    / * Проверьте, совпадают ли данные обоих корней и данные левого и правого

       поддеревья также одинаковы * /

    return (root1->data == root2->data   &&

            areIdentical(root1->left, root2->left) &&

            areIdentical(root1->right, root2->right) );

}

  

  
/ * Эта функция возвращает true, если S является поддеревом T, в противном случае false * /

bool isSubtree(struct node *T, struct node *S)

{

    / * базовые случаи * /

    if (S == NULL)

        return true;

  

    if (T == NULL)

        return false;

  

    / * Проверить дерево с корнем в качестве текущего узла * /

    if (areIdentical(T, S))

        return true;

  

    / * Если дерево с корнем в качестве текущего узла не совпадает, то

       попробуйте левое и правое поддеревья по одному * /

    return isSubtree(T->left, S) ||

           isSubtree(T->right, S);

}

  

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

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

}

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

int main()

{

    // ДЕРЕВО 1

    / * Построить следующее дерево

              26

            / /

          10 3

        ///

      4 6 3

       /

        30

    * /

    struct node *T        = newNode(26);

    T->right              = newNode(3);

    T->right->right       = newNode(3);

    T->left               = newNode(10);

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

    T->left->left->right  = newNode(30);

    T->left->right        = newNode(6);

  

    // ДЕРЕВО 2

    / * Построить следующее дерево

          10

        / /

      4 6

       /

        30

    * /

    struct node *S    = newNode(10);

    S->right          = newNode(6);

    S->left           = newNode(4);

    S->left->right    = newNode(30);

  

  

    if (isSubtree(T, S))

        printf("Tree 2 is subtree of Tree 1");

    else

        printf("Tree 2 is not a subtree of Tree 1");

  

    getchar();

    return 0;

}

Джава

// Java-программа для проверки, является ли двоичное дерево поддеревом другого двоичного дерева

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

class Node 

{

    int data;

    Node left, right, nextRight;

   

    Node(int item) 

    {

        data = item;

        left = right = nextRight = null;

    }

}

   

class BinaryTree 

{

    Node root1,root2;

   

    / * Утилита для проверки наличия деревьев с корнями в качестве root1 и

       root2 идентичны или нет * /

    boolean areIdentical(Node root1, Node root2) 

    {

   

        / * базовые случаи * /

        if (root1 == null && root2 == null)

            return true;

   

        if (root1 == null || root2 == null)

            return false;

   

        / * Проверьте, совпадают ли данные обоих корней и данные левого и правого

           поддеревья также одинаковы * /

        return (root1.data == root2.data

                && areIdentical(root1.left, root2.left)

                && areIdentical(root1.right, root2.right));

    }

   

    / * Эта функция возвращает true, если S является поддеревом T, в противном случае false * /

    boolean isSubtree(Node T, Node S) 

    {

        / * базовые случаи * /

        if (S == null

            return true;

   

        if (T == null)

            return false;

   

        / * Проверить дерево с корнем в качестве текущего узла * /

        if (areIdentical(T, S)) 

            return true;

   

        / * Если дерево с корнем в качестве текущего узла не совпадает, то

           попробуйте левое и правое поддеревья по одному * /

        return isSubtree(T.left, S)

                || isSubtree(T.right, S);

    }

   

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

           

        // ДЕРЕВО 1

        / * Построить следующее дерево

              26

             / /

            10 3

           ///

          4 6 3

           /

            30 *

            

        tree.root1 = new Node(26);

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

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

        tree.root1.left = new Node(10);

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

        tree.root1.left.left.right = new Node(30);

        tree.root1.left.right = new Node(6);

   

        // ДЕРЕВО 2

        / * Построить следующее дерево

           10

         / /

         4 6

          /

          30 *

            

        tree.root2 = new Node(10);

        tree.root2.right = new Node(6);

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

        tree.root2.left.right = new Node(30);

   

        if (tree.isSubtree(tree.root1, tree.root2))

            System.out.println("Tree 2 is subtree of Tree 1 ");

        else

            System.out.println("Tree 2 is not a subtree of Tree 1");

    }

}

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

питон

# Программа Python для проверки двоичного дерева является поддеревом
# другое дерево

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

class Node:

  

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

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
# Полезная функция для проверки наличия деревьев с корнями
# поскольку root 1 и root2 неопределенны или нет

def areIdentical(root1, root2):

      

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

    if root1 is None and root2 is None:

        return True

    if root1 is None or root2 is None:

        return False

  

    # Проверьте, совпадают ли данные обоих корней и данные

    # левое и правое поддеревья также одинаковы

    return (root1.data == root2.data and 

            areIdentical(root1.left , root2.left)and

            areIdentical(root1.right, root2.right)

            

  
# Эта функция возвращает True, если S является поддеревом T,
# иначе Ложь

def isSubtree(T, S):

      

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

    if S is None:

        return True

  

    if T is None:

        return False

  

    # Проверить дерево с корнем в качестве текущего узла

    if (areIdentical(T, S)):

        return True

  

    # ЕСЛИ дерево с корнем в качестве текущего узла не совпадает

    # затем попробуйте левое и правое поддерево один за другим

    return isSubtree(T.left, S) or isSubtree(T.right, S)

  

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

  
"" "ДЕРЕВО 1

     Построить следующее дерево

              26

            / /

          10 3

        ///

      4 6 3

       /

        30

    «»»

  

T = Node(26)

T.right = Node(3)

T.right.right  = Node(3)

T.left = Node(10)

T.left.left = Node(4)

T.left.left.right = Node(30)

T.left.right = Node(6)

  
"" "ДЕРЕВО 2

     Построить следующее дерево

          10

        / /

      4 6

       /

        30

    «»»

S = Node(10)

S.right = Node(6)

S.left = Node(4)

S.left.right = Node(30)

  

if isSubtree(T, S):

    print "Tree 2 is subtree of Tree 1"

else :

    print "Tree 2 is not a subtree of Tree 1"

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

C #

// C # программа для проверки бинарного дерева
// является поддеревом другого двоичного дерева

using System;

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

class Node 

    public int data; 

    public Node left, right, nextRight; 

  

    public Node(int item) 

    

        data = item; 

        left = right = nextRight = null

    

  

public class BinaryTree 

    Node root1,root2; 

  

    / * Полезная функция для проверки

        деревья с корнями в качестве root1 и

        root2 идентичны или нет * /

    bool areIdentical(Node root1, Node root2) 

    

  

        / * базовые случаи * /

        if (root1 == null && root2 == null

            return true

  

        if (root1 == null || root2 == null

            return false

  

        / * Проверьте, являются ли данные обоих корней

        так же и данные слева и справа

        поддеревья также одинаковы * /

        return (root1.data == root2.data 

                && areIdentical(root1.left, root2.left) 

                && areIdentical(root1.right, root2.right)); 

    

  

    / * Эта функция возвращает true, если S

    поддерево T, иначе ложь * /

    bool isSubtree(Node T, Node S) 

    

        / * базовые случаи * /

        if (S == null

            return true

  

        if (T == null

            return false

  

        / * Проверить дерево с корнем в качестве текущего узла * /

        if (areIdentical(T, S)) 

            return true

  

        / * Если дерево с корнем в качестве текущего

          узел не совпадает, попробуйте влево

          и правильные поддеревья по одному * /

        return isSubtree(T.left, S) 

                || isSubtree(T.right, S); 

    

  

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

    public static void Main() 

    

        BinaryTree tree = new BinaryTree(); 

          

        // ДЕРЕВО 1

        / * Построить следующее дерево

            26

            / /

            10 3

        ///

        4 6 3

        /

            30 *

              

        tree.root1 = new Node(26); 

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

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

        tree.root1.left = new Node(10); 

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

        tree.root1.left.left.right = new Node(30); 

        tree.root1.left.right = new Node(6); 

  

        // ДЕРЕВО 2

        / * Построить следующее дерево

        10

        / /

        4 6

        /

        30 *

              

        tree.root2 = new Node(10); 

        tree.root2.right = new Node(6); 

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

        tree.root2.left.right = new Node(30); 

  

        if (tree.isSubtree(tree.root1, tree.root2)) 

            Console.WriteLine("Tree 2 is subtree of Tree 1 "); 

        else

            Console.WriteLine("Tree 2 is not a subtree of Tree 1"); 

    

  
/ * Этот код предоставлен Rajput-Ji * /


Выход:

Tree 2 is subtree of Tree 1 

Сложность по времени: сложность по наихудшему случаю по времени вышеупомянутого решения составляет O (mn), где m и n — количество узлов в данных двух деревьях.

Мы можем решить вышеупомянутую проблему за O (n) время. Пожалуйста, обратитесь Проверьте, является ли двоичное дерево поддеревом другого двоичного дерева | Установите 2 для решения.

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

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

Проверить, является ли двоичное дерево поддеревом другого двоичного дерева | Комплект 1

0.00 (0%) 0 votes