Compruebe si los dos árboles de búsqueda binarios son idénticos o no

Posted on by Rudeus Greyrat

Dados los Nodes raíz de los dos árboles de búsqueda binarios. La tarea es imprimir «Ambos BST son idénticos» si los dos árboles de búsqueda binarios son idénticos; de lo contrario, imprimir «Ambos BST son idénticos». Dos árboles son idénticos si son estructuralmente idénticos y los Nodes tienen los mismos valores.
 

  Árbol1 –                                         

         5                                               
        / \
      3 8
     / \   
    2 4

   árbol2-

       5
      / \
     3 8
    / \   
   2 4

Aquí, en ambos árboles, la estructura es la misma y los Nodes tienen el mismo valor, por lo que podemos decir que ambos BST son idénticos.

Para identificar si dos árboles son idénticos, necesitamos atravesar ambos árboles simultáneamente, y mientras lo hacemos, necesitamos comparar los datos y los hijos de los árboles.
A continuación se muestra el algoritmo paso a paso para verificar si dos BST son idénticos: 
 

  1. Si ambos árboles están vacíos, devuelve 1.
  2. De lo contrario, si ambos árboles no están vacíos 
    • Verifique los datos de los Nodes raíz (tree1->data == tree2->data)
    • Verifique los subárboles izquierdos recursivamente, es decir, llame a sameTree (tree1->left_subtree, tree2->left_subtree)
    • Verifique los subárboles correctos recursivamente, es decir, llame a sameTree (tree1->right_subtree, tree2->right_subtree)
    • Si los valores devueltos en los tres pasos anteriores son verdaderos, devuelva 1.
  3. De lo contrario, devuelve 0 (uno está vacío y el otro no).

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to check if two BSTs
// are identical
 
#include <iostream>
using namespace std;
 
// BST node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
 
// Utility function to create a new Node
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;
}
 
// Function to perform inorder traversal
void inorder(Node* root)
{
    if (root == NULL)
        return;
 
    inorder(root->left);
 
    cout << root->data << " ";
 
    inorder(root->right);
}
 
// Function to check if two BSTs
// are identical
int isIdentical(Node* root1, Node* root2)
{
    // Check if both the trees are empty
    if (root1 == NULL && root2 == NULL)
        return 1;
    // If any one of the tree is non-empty
    // and other is empty, return false
    else if (root1 == NULL || root2 == NULL)
        return 0;
    else { // Check if current data of both trees equal
        // and recursively check for left and right subtrees
        if (root1->data == root2->data && isIdentical(root1->left, root2->left)
            && isIdentical(root1->right, root2->right))
            return 1;
        else
            return 0;
    }
}
 
// Driver code
int main()
{
    struct Node* root1 = newNode(5);
    struct Node* root2 = newNode(5);
    root1->left = newNode(3);
    root1->right = newNode(8);
    root1->left->left = newNode(2);
    root1->left->right = newNode(4);
 
    root2->left = newNode(3);
    root2->right = newNode(8);
    root2->left->left = newNode(2);
    root2->left->right = newNode(4);
 
    if (isIdentical(root1, root2))
        cout << "Both BSTs are identical";
    else
        cout << "BSTs are not identical";
 
    return 0;
}

C

// C program to check if two BSTs
// are identical
 
#include <stdio.h>
#include <stdlib.h>
 
 
// BST node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
 
// Utility function to create a new Node
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;
}
 
// Function to perform inorder traversal
void inorder(struct Node* root)
{
    if (root == NULL)
        return;
 
    inorder(root->left);
 
    printf("%d " ,root->data);
 
    inorder(root->right);
}
 
// Function to check if two BSTs
// are identical
int isIdentical(struct Node* root1,struct Node* root2)
{
    // Check if both the trees are empty
    if (root1 == NULL && root2 == NULL)
        return 1;
    // If any one of the tree is non-empty
    // and other is empty, return false
    else if (root1 == NULL || root2 == NULL)
        return 0;
    else { // Check if current data of both trees equal
        // and recursively check for left and right subtrees
        if (root1->data == root2->data && isIdentical(root1->left, root2->left)
            && isIdentical(root1->right, root2->right))
            return 1;
        else
            return 0;
    }
}
 
// Driver code
int main()
{
    struct Node* root1 = newNode(5);
    struct Node* root2 = newNode(5);
    root1->left = newNode(3);
    root1->right = newNode(8);
    root1->left->left = newNode(2);
    root1->left->right = newNode(4);
 
    root2->left = newNode(3);
    root2->right = newNode(8);
    root2->left->left = newNode(2);
    root2->left->right = newNode(4);
 
    if (isIdentical(root1, root2))
        printf( "Both BSTs are identical");
    else
        printf("BSTs are not identical") ;
 
    return 0;
}
 
// This code is contributed by sanskar84.

Java

// Java program to check if two BSTs
// are identical
class GFG
{
 
// BST node
static class Node
{
    int data;
    Node left;
    Node right;
};
 
// Utility function to create a new Node
static Node newNode(int data)
{
    Node node = new Node();
    node.data = data;
    node.left = null;
    node.right = null;
 
    return node;
}
 
// Function to perform inorder traversal
static void inorder(Node root)
{
    if (root == null)
        return;
 
    inorder(root.left);
 
    System.out.print(root.data + " ");
 
    inorder(root.right);
}
 
// Function to check if two BSTs
// are identical
static int isIdentical(Node root1,
                       Node root2)
{
    // Check if both the trees are empty
    if (root1 == null && root2 == null)
        return 1;
         
    // If any one of the tree is non-empty
    // and other is empty, return false
    else if (root1 != null &&
             root2 == null)
        return 0;
    else if (root1 == null &&
             root2 != null)
        return 0;
    else
    {
        // Check if current data of both trees equal
        // and recursively check for left and right subtrees
        if (root1.data == root2.data &&
            isIdentical(root1.left, root2.left) == 1 &&
            isIdentical(root1.right, root2.right) == 1)
            return 1;
        else
            return 0;
    }
}
 
// Driver code
public static void main(String[] args)
{
    Node root1 = newNode(5);
    Node root2 = newNode(5);
    root1.left = newNode(3);
    root1.right = newNode(8);
    root1.left.left = newNode(2);
    root1.left.right = newNode(4);
 
    root2.left = newNode(3);
    root2.right = newNode(8);
    root2.left.left = newNode(2);
    root2.left.right = newNode(4);
 
    if (isIdentical(root1, root2)==1)
        System.out.print("Both BSTs are identical");
    else
        System.out.print("BSTs are not identical");
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to construct all unique
# BSTs for keys from 1 to n
 
# Binary Tree Node
""" A utility function to create a
new BST node """
class newNode:
 
    # Construct to create a newNode
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Function to perform inorder traversal
def inorder(root) :
 
    if (root == None):
        return
 
    inorder(root.left)
 
    print(root.data, end = " ")
 
    inorder(root.right)
 
# Function to check if two BSTs
# are identical
def isIdentical(root1, root2) :
 
    # Check if both the trees are empty
    if (root1 == None and root2 == None) :
        return 1
         
    # If any one of the tree is non-empty
    # and other is empty, return false
    elif (root1 != None and root2 == None) :
        return 0
    elif (root1 == None and root2 != None) :
        return 0
    else: # Check if current data of both trees
          # equal and recursively check for left
          # and right subtrees
        if (root1.data == root2.data and
            isIdentical(root1.left, root2.left)
            and isIdentical(root1.right, root2.right)) :
            return 1
        else:
            return 0
     
# Driver Code
if __name__ == '__main__':
 
    root1 = newNode(5)
    root2 = newNode(5)
    root1.left = newNode(3)
    root1.right = newNode(8)
    root1.left.left = newNode(2)
    root1.left.right = newNode(4)
 
    root2.left = newNode(3)
    root2.right = newNode(8)
    root2.left.left = newNode(2)
    root2.left.right = newNode(4)
 
    if (isIdentical(root1, root2)):
        print("Both BSTs are identical")
    else:
        print("BSTs are not identical")
 
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

C#

// C# program to check if two BSTs
// are identical
using System;
 
class GFG
{
 
// BST node
class Node
{
    public int data;
    public Node left;
    public Node right;
};
 
// Utility function to create a new Node
static Node newNode(int data)
{
    Node node = new Node();
    node.data = data;
    node.left = null;
    node.right = null;
 
    return node;
}
 
// Function to perform inorder traversal
static void inorder(Node root)
{
    if (root == null)
        return;
 
    inorder(root.left);
 
    Console.Write(root.data + " ");
 
    inorder(root.right);
}
 
// Function to check if two BSTs
// are identical
static int isIdentical(Node root1,
                       Node root2)
{
    // Check if both the trees are empty
    if (root1 == null && root2 == null)
        return 1;
         
    // If any one of the tree is non-empty
    // and other is empty, return false
    else if (root1 != null &&
             root2 == null)
        return 0;
    else if (root1 == null &&
             root2 != null)
        return 0;
    else
    {
        // Check if current data of both trees equal
        // and recursively check for left and right subtrees
        if (root1.data == root2.data &&
            isIdentical(root1.left, root2.left) == 1 &&
            isIdentical(root1.right, root2.right) == 1)
            return 1;
        else
            return 0;
    }
}
 
// Driver code
public static void Main(String[] args)
{
    Node root1 = newNode(5);
    Node root2 = newNode(5);
    root1.left = newNode(3);
    root1.right = newNode(8);
    root1.left.left = newNode(2);
    root1.left.right = newNode(4);
 
    root2.left = newNode(3);
    root2.right = newNode(8);
    root2.left.left = newNode(2);
    root2.left.right = newNode(4);
 
    if (isIdentical(root1, root2) == 1)
        Console.Write("Both BSTs are identical");
    else
        Console.Write("BSTs are not identical");
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// Javascript program to check if two BSTs
// are identical
 
// BST node
class Node
{
    // Utility function to create a new Node
    constructor(data)
    {
        this.data = data;
        this.left = this.right = null;
    }
}
 
// Function to perform inorder traversal
function inorder(root)
{
    if (root == null)
        return;
  
    inorder(root.left);
  
    document.write(root.data + " ");
  
    inorder(root.right);
}
 
// Function to check if two BSTs
// are identical
function isIdentical(root1,root2)
{
    // Check if both the trees are empty
    if (root1 == null && root2 == null)
        return 1;
          
    // If any one of the tree is non-empty
    // and other is empty, return false
    else if (root1 != null &&
             root2 == null)
        return 0;
    else if (root1 == null &&
             root2 != null)
        return 0;
    else
    {
        // Check if current data of both trees equal
        // and recursively check for left and right subtrees
        if (root1.data == root2.data &&
            isIdentical(root1.left, root2.left) == 1 &&
            isIdentical(root1.right, root2.right) == 1)
            return 1;
        else
            return 0;
    }
}
 
// Driver code
let root1 = new Node(5);
    let root2 = new Node(5);
    root1.left = new Node(3);
    root1.right = new Node(8);
    root1.left.left = new Node(2);
    root1.left.right = new Node(4);
  
    root2.left = new Node(3);
    root2.right = new Node(8);
    root2.left.left = new Node(2);
    root2.left.right = new Node(4);
  
    if (isIdentical(root1, root2)==1)
        document.write("Both BSTs are identical");
    else
        document.write("BSTs are not identical");
 
// This code is contributed by avanitrachhadiya2155
</script>
Producción: 

Both BSTs are identical

 

Complejidad temporal: O(N)
Espacio auxiliar: O(N) 

Publicación traducida automáticamente

Artículo escrito por rajneshmeena y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *