Рубрики

Проверить, является ли двоичное дерево поддеревом другого двоичного дерева | Набор 2

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

Поддерево, соответствующее корневому узлу, является целым деревом; поддерево, соответствующее любому другому узлу, называется правильным поддеревом.

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


        Tree1
          x 
        /    \
      a       b
       \
        c


        Tree2
              z
            /   \
          x      e
        /    \     \
      a       b      k
       \
        c

Мы обсудили O (n 2 ) решение этой проблемы . В этом посте обсуждается решение O (n). Идея основана на том факте, что inorder и preorder / postorder однозначно идентифицируют двоичное дерево . Дерево S является поддеревом T, если как обходы по порядку, так и по предзаказу из S являются подстроками обхода по неупорядочению и предзаказу для T соответственно.

Ниже приведены подробные шаги.

1 ) Найдите обходы порядка и предзаказа T, сохраните их в двух вспомогательных массивах inT [] и preT [].

2 ) Найдите обходы порядка и предзаказа S, сохраните их в двух вспомогательных массивах inS [] и preS [].

3 ) Если inS [] является подмассивом inT [] и preS [] является подмассивом preT [], то S является поддеревом T. Иначе нет.

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

Давайте рассмотрим приведенный выше пример

Inorder and Preorder traversals of the big tree are.
inT[]   =  {a, c, x, b, z, e, k}
preT[]  =  {z, x, a, c, b, e, k}

Inorder and Preorder traversals of small tree are
inS[]  = {a, c, x, b}
preS[] = {x, a, c, b}

We can easily figure out that inS[] is a subarray of
inT[] and preS[] is a subarray of preT[]. 

РЕДАКТИРОВАТЬ

The above algorithm doesn't work for cases where a tree is present
in another tree, but not as a subtree. Consider the following example.

        Tree1
          x 
        /    \
      a       b
     /        
    c         


        Tree2
          x 
        /    \
      a       b
     /         \
    c            d

Inorder and Preorder traversals of the big tree or Tree2 are.

Inorder and Preorder traversals of small tree or Tree1 are

The Tree2 is not a subtree of Tree1, but inS[] and preS[] are
subarrays of inT[] and preT[] respectively.

Вышеприведенный алгоритм может быть расширен для обработки таких случаев, добавляя специальный символ всякий раз, когда мы сталкиваемся с NULL в обходах по порядку и предзаказу. Спасибо Шиваму Гоэлу за предложение об этом расширении.

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

C ++

#include <cstring>
#include <iostream>

using namespace std;

#define MAX 100

  
// Структура узла дерева

struct Node {

    char key;

    struct Node *left, *right;

};

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

Node* newNode(char item)

{

    Node* temp = new Node;

    temp->key = item;

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

    return temp;

}

  
// Полезная функция для хранения обхода дерева по корню
// с корнем в массиве arr []. Обратите внимание, что я передан в качестве ссылки

void storeInorder(Node* root, char arr[], int& i)

{

    if (root == NULL) {

        arr[i++] = '$';

        return;

    }

    storeInorder(root->left, arr, i);

    arr[i++] = root->key;

    storeInorder(root->right, arr, i);

}

  
// Полезная функция для хранения предзаказа обхода дерева с корнем
// с корнем в массиве arr []. Обратите внимание, что я передан в качестве ссылки

void storePreOrder(Node* root, char arr[], int& i)

{

    if (root == NULL) {

        arr[i++] = '$';

        return;

    }

    arr[i++] = root->key;

    storePreOrder(root->left, arr, i);

    storePreOrder(root->right, arr, i);

}

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

bool isSubtree(Node* T, Node* S)

{

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

    if (S == NULL)

        return true;

    if (T == NULL)

        return false;

  

    // Сохраняем обходы порядка в T и S в inT [0..m-1]

    // и inS [0..n-1] соответственно

    int m = 0, n = 0;

    char inT[MAX], inS[MAX];

    storeInorder(T, inT, m);

    storeInorder(S, inS, n);

    inT[m] = '\0', inS[n] = '\0';

  

    // Если inS [] не является подстрокой preS [], вернуть false

    if (strstr(inT, inS) == NULL)

        return false;

  

    // Сохраняем предварительные обходы T и S в inT [0..m-1]

    // и inS [0..n-1] соответственно

    m = 0, n = 0;

    char preT[MAX], preS[MAX];

    storePreOrder(T, preT, m);

    storePreOrder(S, preS, n);

    preT[m] = '\0', preS[n] = '\0';

  

    // Если inS [] не является подстрокой preS [], вернуть false

    // иначе вернем true

    return (strstr(preT, preS) != NULL);

}

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

int main()

{

    Node* T = newNode('a');

    T->left = newNode('b');

    T->right = newNode('d');

    T->left->left = newNode('c');

    T->right->right = newNode('e');

  

    Node* S = newNode('a');

    S->left = newNode('b');

    S->left->left = newNode('c');

    S->right = newNode('d');

  

    if (isSubtree(T, S))

        cout << "Yes: S is a subtree of T";

    else

        cout << "No: S is NOT a subtree of T";

  

    return 0;

}

Джава

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

class Node {

  

    char data;

    Node left, right;

  

    Node(char item)

    {

        data = item;

        left = right = null;

    }

}

  

class Passing {

  

    int i;

    int m = 0;

    int n = 0;

}

  

class BinaryTree {

  

    static Node root;

    Passing p = new Passing();

  

    String strstr(String haystack, String needle)

    {

        if (haystack == null || needle == null) {

            return null;

        }

        int hLength = haystack.length();

        int nLength = needle.length();

        if (hLength < nLength) {

            return null;

        }

        if (nLength == 0) {

            return haystack;

        }

        for (int i = 0; i <= hLength - nLength; i++) {

            if (haystack.charAt(i) == needle.charAt(0)) {

                int j = 0;

                for (; j < nLength; j++) {

                    if (haystack.charAt(i + j) != needle.charAt(j)) {

                        break;

                    }

                }

                if (j == nLength) {

                    return haystack.substring(i);

                }

            }

        }

        return null;

    }

  

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

    // с корнем в массиве arr []. Обратите внимание, что я передан в качестве ссылки

    void storeInorder(Node node, char arr[], Passing i)

    {

        if (node == null) {

            arr[i.i++] = '$';

            return;

        }

        storeInorder(node.left, arr, i);

        arr[i.i++] = node.data;

        storeInorder(node.right, arr, i);

    }

  

    // Полезная функция для хранения предзаказа обхода дерева с корнем

    // с корнем в массиве arr []. Обратите внимание, что я передан в качестве ссылки

    void storePreOrder(Node node, char arr[], Passing i)

    {

        if (node == null) {

            arr[i.i++] = '$';

            return;

        }

        arr[i.i++] = node.data;

        storePreOrder(node.left, arr, i);

        storePreOrder(node.right, arr, i);

    }

  

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

    boolean isSubtree(Node T, Node S)

    {

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

        if (S == null) {

            return true;

        }

        if (T == null) {

            return false;

        }

  

        // Сохраняем обходы порядка в T и S в inT [0..m-1]

        // и inS [0..n-1] соответственно

        char inT[] = new char[100];

        String op1 = String.valueOf(inT);

        char inS[] = new char[100];

        String op2 = String.valueOf(inS);

        storeInorder(T, inT, p);

        storeInorder(S, inS, p);

        inT[p.m] = '\0';

        inS[p.m] = '\0';

  

        // Если inS [] не является подстрокой preS [], вернуть false

        if (strstr(op1, op2) != null) {

            return false;

        }

  

        // Сохраняем предварительные обходы T и S в inT [0..m-1]

        // и inS [0..n-1] соответственно

        p.m = 0;

        p.n = 0;

        char preT[] = new char[100];

        char preS[] = new char[100];

        String op3 = String.valueOf(preT);

        String op4 = String.valueOf(preS);

        storePreOrder(T, preT, p);

        storePreOrder(S, preS, p);

        preT[p.m] = '\0';

        preS[p.n] = '\0';

  

        // Если inS [] не является подстрокой preS [], вернуть false

        // иначе вернем true

        return (strstr(op3, op4) != null);

    }

  

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

    public static void main(String args[])

    {

        BinaryTree tree = new BinaryTree();

        Node T = new Node('a');

        T.left = new Node('b');

        T.right = new Node('d');

        T.left.left = new Node('c');

        T.right.right = new Node('e');

  

        Node S = new Node('a');

        S.left = new Node('b');

        S.right = new Node('d');

        S.left.left = new Node('c');

  

        if (tree.isSubtree(T, S)) {

            System.out.println("Yes, S is a subtree of T");

        }

        else {

            System.out.println("No, S is not a subtree of T");

        }

    }

}

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

C #

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

using System;

  

public class Node {

  

    public char data;

    public Node left, right;

  

    public Node(char item)

    {

        data = item;

        left = right = null;

    }

}

  

public class Passing {

  

    public int i;

    public int m = 0;

    public int n = 0;

}

  

public class BinaryTree {

  

    static Node root;

    Passing p = new Passing();

  

    String strstr(String haystack, String needle)

    {

        if (haystack == null || needle == null) {

            return null;

        }

        int hLength = haystack.Length;

        int nLength = needle.Length;

        if (hLength < nLength) {

            return null;

        }

        if (nLength == 0) {

            return haystack;

        }

        for (int i = 0; i <= hLength - nLength; i++) {

            if (haystack[i] == needle[0]) {

                int j = 0;

                for (; j < nLength; j++) {

                    if (haystack[i + j] != needle[j]) {

                        break;

                    }

                }

                if (j == nLength) {

                    return haystack.Substring(i);

                }

            }

        }

        return null;

    }

  

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

    // обход дерева с корнем в

    // массив arr []. Обратите внимание, что я передан в качестве ссылки

    void storeInorder(Node node, char[] arr, Passing i)

    {

        if (node == null) {

            arr[i.i++] = '$';

            return;

        }

        storeInorder(node.left, arr, i);

        arr[i.i++] = node.data;

        storeInorder(node.right, arr, i);

    }

  

    // Утилита для сохранения предзаказа

    // обход дерева с корнем в

    // массив arr []. Обратите внимание, что я передан в качестве ссылки

    void storePreOrder(Node node, char[] arr, Passing i)

    {

        if (node == null) {

            arr[i.i++] = '$';

            return;

        }

        arr[i.i++] = node.data;

        storePreOrder(node.left, arr, i);

        storePreOrder(node.right, arr, i);

    }

  

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

    является поддеревом T, иначе false * /

    bool isSubtree(Node T, Node S)

    {

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

        if (S == null) {

            return true;

        }

        if (T == null) {

            return false;

        }

  

        // Сохраняем обходы порядка в T и S в inT [0..m-1]

        // и inS [0..n-1] соответственно

        char[] inT = new char[100];

        String op1 = String.Join("", inT);

        char[] inS = new char[100];

        String op2 = String.Join("", inS);

        storeInorder(T, inT, p);

        storeInorder(S, inS, p);

        inT[p.m] = '\0';

        inS[p.m] = '\0';

  

        // Если inS [] не является подстрокой preS [], вернуть false

        if (strstr(op1, op2) != null) {

            return false;

        }

  

        // Сохраняем предварительные обходы T и S в inT [0..m-1]

        // и inS [0..n-1] соответственно

        p.m = 0;

        p.n = 0;

        char[] preT = new char[100];

        char[] preS = new char[100];

        String op3 = String.Join("", preT);

        String op4 = String.Join("", preS);

        storePreOrder(T, preT, p);

        storePreOrder(S, preS, p);

        preT[p.m] = '\0';

        preS[p.n] = '\0';

  

        // Если inS [] не является подстрокой preS [], вернуть false

        // иначе вернем true

        return (strstr(op3, op4) != null);

    }

  

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

    public static void Main(String[] args)

    {

        BinaryTree tree = new BinaryTree();

        Node T = new Node('a');

        T.left = new Node('b');

        T.right = new Node('d');

        T.left.left = new Node('c');

        T.right.right = new Node('e');

  

        Node S = new Node('a');

        S.left = new Node('b');

        S.right = new Node('d');

        S.left.left = new Node('c');

  

        if (tree.isSubtree(T, S)) {

            Console.WriteLine("Yes, S is a subtree of T");

        }

        else {

            Console.WriteLine("No, S is not a subtree of T");

        }

    }

}

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


Выход:

No: S is NOT a subtree of T

Сложность времени: обходы по бинарному дереву по неупорядочению и по предзаказу занимают O (n) времени. Функция strstr () также может быть реализована за O (n) время с использованием алгоритма сопоставления строк KMP .

Вспомогательное пространство: O (n)

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

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

Проверить, является ли двоичное дерево поддеревом другого двоичного дерева | Набор 2

0.00 (0%) 0 votes