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

01.01.2020Деревья

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

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

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


        Tree1
          x 
        /    \
      a       b
       \
        c


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

Мы обсудили O (n ² ) решение этой проблемы . В этом посте обсуждается решение 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