Dados dos árboles binarios, compruebe si el primer árbol es un subárbol del segundo. Un subárbol de un árbol T es un árbol S que consta de un Node en T y todos sus descendientes en T.
El subárbol correspondiente al Node raíz es el árbol completo; el subárbol correspondiente a cualquier otro Node se denomina subárbol propio.
Por ejemplo, en el siguiente caso, Tree1 es un subárbol de Tree2.
Tree1
x
/ \
a b
\
c
Tree2
z
/ \
x e
/ \ \
a b k
\
c
Hemos discutido una solución O(n 2 ) para este problema . En esta publicación, se analiza la solución O(n). La idea se basa en el hecho de que inorder y preorder/postorder identifican de forma única un árbol binario . El árbol S es un subárbol de T si tanto los recorridos en orden como en preorden de S son substrings de recorridos en orden y en preorden de T respectivamente.
Los siguientes son pasos detallados.
1 ) Encuentre recorridos en orden y preorden de T, y almacénelos en dos arreglos auxiliares inT[] y preT[].
2 ) Encuentre recorridos en orden y preorden de S, y almacénelos en dos arreglos auxiliares en S[] y preS[].
3 ) Si inS[] es un subarreglo de inT[] y preS[] es un subarreglo preT[], entonces S es un subárbol de T. De lo contrario, no.
También podemos usar el recorrido posterior al orden en lugar del preorden en el algoritmo anterior.
Consideremos el ejemplo anterior
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[].
EDITAR
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.
inT[] = {c, a, x, b, d}
preT[] = {x, a, c, b, d}
Inorder and Preorder traversals of small tree or Tree1 are-
inS[] = {c, a, x, b}
preS[] = {x, a, c, b}
The Tree2 is not a subtree of Tree1, but inS[] and preS[] are
subarrays of inT[] and preT[] respectively.
El algoritmo anterior se puede extender para manejar tales casos agregando un carácter especial siempre que encontremos NULL en recorridos en orden y en orden previo. Gracias a Shivam Goel por sugerir esta extensión.
A continuación se muestra la implementación del algoritmo anterior.
C++
#include <cstring>
#include <iostream>
using namespace std;
#define MAX 100
// Structure of a tree node
struct Node {
char key;
struct Node *left, *right;
};
// A utility function to create a new BST node
Node* newNode(char item)
{
Node* temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to store inorder traversal of tree rooted
// with root in an array arr[]. Note that i is passed as reference
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);
}
// A utility function to store preorder traversal of tree rooted
// with root in an array arr[]. Note that i is passed as reference
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);
}
/* This function returns true if S is a subtree of T, otherwise false */
bool isSubtree(Node* T, Node* S)
{
/* base cases */
if (S == NULL)
return true;
if (T == NULL)
return false;
// Store Inorder traversals of T and S in inT[0..m-1]
// and inS[0..n-1] respectively
int m = 0, n = 0;
char inT[MAX], inS[MAX];
storeInorder(T, inT, m);
storeInorder(S, inS, n);
inT[m] = '\0', inS[n] = '\0';
// If inS[] is not a substring of inT[], return false
if (strstr(inT, inS) == NULL)
return false;
// Store Preorder traversals of T and S in preT[0..m-1]
// and preS[0..n-1] respectively
m = 0, n = 0;
char preT[MAX], preS[MAX];
storePreOrder(T, preT, m);
storePreOrder(S, preS, n);
preT[m] = '\0', preS[n] = '\0';
// If preS[] is not a substring of preT[], return false
// Else return true
return (strstr(preT, preS) != NULL);
}
// Driver program to test above function
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
// Java program to check if binary tree
// is subtree of another binary tree
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;
}
// A utility function to store inorder traversal of tree rooted
// with root in an array arr[]. Note that i is passed as reference
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);
}
// A utility function to store preorder traversal of tree rooted
// with root in an array arr[]. Note that i is passed as reference
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);
}
/* This function returns true if S is a subtree of T, otherwise false */
boolean isSubtree(Node T, Node S)
{
/* base cases */
if (S == null) {
return true;
}
if (T == null) {
return false;
}
// Store Inorder traversals of T and S in inT[0..m-1]
// and inS[0..n-1] respectively
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';
// If inS[] is not a substring of preS[], return false
if (strstr(op1, op2) == null) {
return false;
}
// Store Preorder traversals of T and S in inT[0..m-1]
// and inS[0..n-1] respectively
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';
// If inS[] is not a substring of preS[], return false
// Else return true
return (strstr(op3, op4) != null);
}
// Driver program to test above functions
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");
}
}
}
// This code is contributed by Mayank Jaiswal
Python3
MAX = 100
# class for a tree node
class Node:
def __init__(self):
self.key = ' '
self.left = None
self.right = None
# A utility function to create a new BST node
def newNode(item):
temp = Node()
temp.key = item
return temp
# A utility function to store inorder traversal of tree rooted
# with root in an array arr[]. Note that i is passed as reference
def storeInorder(root, i):
if (root == None):
return '$'
res = storeInorder(root.left, i)
res += root.key
res += storeInorder(root.right, i)
return res
# A utility function to store preorder traversal of tree rooted
# with root in an array arr[]. Note that i is passed as reference
def storePreOrder(root, i):
if (root == None):
return '$'
res = root.key
res += storePreOrder(root.left, i)
res += storePreOrder(root.right, i)
return res
# This function returns true if S is a subtree of T, otherwise false
def isSubtree(T, S):
# base cases
if (S == None):
return True
if (T == None):
return False
# Store Inorder traversals of T and S in inT[0..m-1]
# and inS[0..n-1] respectively
m = 0
n = 0
inT = storeInorder(T, m)
inS = storeInorder(S, n)
# If inS[] is not a substring of inT[], return false
res = True
if inS in inT:
res = True
else:
res = False
if(res == False):
return res
# Store Preorder traversals of T and S in preT[0..m-1]
# and preS[0..n-1] respectively
m = 0
n = 0
preT = storePreOrder(T, m)
preS = storePreOrder(S, n)
# If preS[] is not a substring of preT[], return false
# Else return true
if preS in preT:
return True
else:
return False
# Driver program to test above function
T = newNode('a')
T.left = newNode('b')
T.right = newNode('d')
T.left.left = newNode('c')
T.right.right = newNode('e')
S = newNode('a')
S.left = newNode('b')
S.left.left = newNode('c')
S.right = newNode('d')
if (isSubtree(T, S)):
print("Yes: S is a subtree of T")
else:
print("No: S is NOT a subtree of T")
# This code is contributed by rj13to.
C#
// C# program to check if binary tree is
// subtree of another binary tree
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;
}
// A utility function to store inorder
// traversal of tree rooted with root in
// an array arr[]. Note that i is passed as reference
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);
}
// A utility function to store preorder
// traversal of tree rooted with root in
// an array arr[]. Note that i is passed as reference
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);
}
/* This function returns true if S
is a subtree of T, otherwise false */
bool isSubtree(Node T, Node S)
{
/* base cases */
if (S == null) {
return true;
}
if (T == null) {
return false;
}
// Store Inorder traversals of T and S in inT[0..m-1]
// and inS[0..n-1] respectively
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';
// If inS[] is not a substring of preS[], return false
if (strstr(op1, op2) != null) {
return false;
}
// Store Preorder traversals of T and S in inT[0..m-1]
// and inS[0..n-1] respectively
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';
// If inS[] is not a substring of preS[], return false
// Else return true
return (strstr(op3, op4) != null);
}
// Driver program to test above functions
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");
}
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
const MAX = 100
// class for a tree node
class Node{
constructor(){
this.key = ' '
this.left = null
this.right = null
}
}
// A utility function to create a new BST node
function newNode(item){
temp = new Node()
temp.key = item
return temp
}
// A utility function to store inorder traversal of tree rooted
// with root in an array arr[]. Note that i is passed as reference
function storeInorder(root, i){
if (root == null)
return '$'
res = storeInorder(root.left, i)
res += root.key
res += storeInorder(root.right, i)
return res
}
// A utility function to store preorder traversal of tree rooted
// with root in an array arr[]. Note that i is passed as reference
function storePreOrder(root, i){
if (root == null)
return '$'
res = root.key
res += storePreOrder(root.left, i)
res += storePreOrder(root.right, i)
return res
}
// This function returns true if S is a subtree of T, otherwise false
function isSubtree(T, S){
// base cases
if (S == null)
return true
if (T == null)
return false
// Store Inorder traversals of T and S in inT[0..m-1]
// and inS[0..n-1] respectively
let m = 0
let n = 0
let inT = storeInorder(T, m)
let inS = storeInorder(S, n)
// If inS[] is not a substring of inT[], return false
res = true
if(inT.indexOf(inT) !== -1)
res = true
else
res = false
if(res == false)
return res
// Store Preorder traversals of T and S in preT[0..m-1]
// and preS[0..n-1] respectively
m = 0
n = 0
let preT = storePreOrder(T, m)
let preS = storePreOrder(S, n)
// If preS[] is not a substring of preT[], return false
// Else return true
if(preT.indexOf(preS) !== -1)
return true
else
return false
}
// Driver program to test above function
let T = new newNode('a')
T.left = new newNode('b')
T.right = new newNode('d')
T.left.left = new newNode('c')
T.right.right = new newNode('e')
let S = new newNode('a')
S.left = new newNode('b')
S.left.left = new newNode('c')
S.right = new newNode('d')
if (isSubtree(T, S))
document.write("Yes: S is a subtree of T","</br>")
else
document.write("No: S is NOT a subtree of T","</br>")
// This code is contributed by shinjanpatra
</script>
Producción:
No: S is NOT a subtree of T
Complejidad de tiempo: los recorridos en orden y en orden previo del árbol binario toman O (n) tiempo. La función strstr() también se puede implementar en tiempo O(n) utilizando el algoritmo de coincidencia de strings KMP .
Espacio auxiliar: O(n)
Gracias a Ashwini Singh por sugerir este método. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA