Función iterativa para verificar si dos árboles son idénticos

Dos árboles son idénticos cuando tienen los mismos datos y la disposición de los datos también es la misma. 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. 
Ejemplos: 
 

Input : Roots of below trees
    10           10
  /   \         /
 5     6       5 
Output : false

Input : Roots of below trees
    10            10
  /   \         /   \
 5     6       5     6
Output : true

C++

/* Iterative C++ program to check if two */
#include <bits/stdc++.h>
using namespace std;
  
// A Binary Tree Node
struct Node
{
    int data;
    struct Node *left, *right;
};
  
// Iterative method to find height of Binary Tree
bool areIdentical(Node *root1, Node *root2)
{
    // Return true if both trees are empty
    if (root1==NULL  && root2==NULL) return true;
  
    // Return false if one is empty and other is not
    if (root1 == NULL) return false;
    if (root2 == NULL) return false;
      
    // Create an empty queues for simultaneous traversals 
    queue<Node *> q1, q2;
  
    // Enqueue Roots of trees in respective queues
    q1.push(root1);
    q2.push(root2);
  
    while (!q1.empty() && !q2.empty())
    {
        // Get front nodes and compare them
        Node *n1 = q1.front();
        Node *n2 = q2.front();
  
        if (n1->data != n2->data)
           return false;
  
        // Remove front nodes from queues
        q1.pop(), q2.pop();
  
        /* Enqueue left children of both nodes */
        if (n1->left && n2->left)
        {
            q1.push(n1->left);
            q2.push(n2->left);
        }
  
        // If one left child is empty and other is not
        else if (n1->left || n2->left)
            return false;
  
        // Right child code (Similar to left child code)
        if (n1->right && n2->right)
        {
            q1.push(n1->right);
            q2.push(n2->right);
        }
        else if (n1->right || n2->right)
            return false;
    }
  
    return true;
}
  
// Utility function to create a new tree node
Node* newNode(int data)
{
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
  
// Driver program to test above functions
int main()
{
    Node *root1 = newNode(1);
    root1->left = newNode(2);
    root1->right = newNode(3);
    root1->left->left = newNode(4);
    root1->left->right = newNode(5);
  
    Node *root2 = newNode(1);
    root2->left = newNode(2);
    root2->right = newNode(3);
    root2->left->left = newNode(4);
    root2->left->right = newNode(5);
  
    areIdentical(root1, root2)? cout << "Yes"
                              : cout << "No";
    return 0;
}

Java

/* Iterative Java program to check if two */
import java.util.*;
class GfG {
  
// A Binary Tree Node 
static class Node 
{ 
    int data; 
    Node left, right; 
}
  
// Iterative method to find height of Binary Tree 
static boolean areIdentical(Node root1, Node root2) 
{ 
    // Return true if both trees are empty 
    if (root1 == null && root2 == null)  return true; 
  
    // Return false if one is empty and other is not 
    if (root1 == null || root2 == null) return false; 
  
    // Create an empty queues for simultaneous traversals 
    Queue<Node > q1 = new LinkedList<Node> ();
    Queue<Node>  q2 = new LinkedList<Node> (); 
  
    // Enqueue Roots of trees in respective queues 
    q1.add(root1); 
    q2.add(root2); 
  
    while (!q1.isEmpty() && !q2.isEmpty()) 
    { 
        // Get front nodes and compare them 
        Node n1 = q1.peek(); 
        Node n2 = q2.peek(); 
  
        if (n1.data != n2.data) 
        return false; 
  
        // Remove front nodes from queues 
        q1.remove();
        q2.remove(); 
  
        /* Enqueue left children of both nodes */
        if (n1.left != null && n2.left != null) 
        { 
            q1.add(n1.left); 
            q2.add(n2.left); 
        } 
  
        // If one left child is empty and other is not 
        else if (n1.left != null || n2.left != null) 
            return false; 
  
        // Right child code (Similar to left child code) 
        if (n1.right != null && n2.right != null) 
        { 
            q1.add(n1.right); 
            q2.add(n2.right); 
        } 
        else if (n1.right != null || n2.right != null) 
            return false; 
    } 
  
    return true; 
} 
  
// Utility function to create a new tree node 
static Node newNode(int data) 
{ 
    Node temp = new Node(); 
    temp.data = data; 
    temp.left = null;
    temp.right = null; 
    return temp; 
} 
  
// Driver program to test above functions 
public static void main(String[] args) 
{ 
    Node root1 = newNode(1); 
    root1.left = newNode(2); 
    root1.right = newNode(3); 
    root1.left.left = newNode(4); 
    root1.left.right = newNode(5); 
  
    Node root2 = newNode(1); 
    root2.left = newNode(2); 
    root2.right = newNode(3); 
    root2.left.left = newNode(4); 
    root2.left.right = newNode(5); 
  
    if(areIdentical(root1, root2) == true)
    System.out.println("Yes");
    else
    System.out.println("No");
}
} 

Python3

# Iterative Python3 program to check 
# if two trees are identical
from queue import Queue 
  
# Utility function to create a 
# new tree node 
class newNode:
    def __init__(self, data):
        self.data = data 
        self.left = self.right = None
  
# Iterative method to find height of 
# Binary Tree 
def areIdentical(root1, root2):
      
    # Return true if both trees are empty 
    if (root1 and root2):
        return True
  
    # Return false if one is empty and
    # other is not 
    if (root1 or root2):
        return False
  
    # Create an empty queues for 
    # simultaneous traversals 
    q1 = Queue()
    q2 = Queue()
  
    # Enqueue Roots of trees in 
    # respective queues 
    q1.put(root1) 
    q2.put(root2) 
  
    while (not q1.empty() and not q2.empty()):
          
        # Get front nodes and compare them 
        n1 = q1.queue[0]
        n2 = q2.queue[0]
  
        if (n1.data != n2.data): 
            return False
  
        # Remove front nodes from queues 
        q1.get()
        q2.get() 
  
        # Enqueue left children of both nodes 
        if (n1.left and n2.left):
            q1.put(n1.left) 
            q2.put(n2.left)
  
        # If one left child is empty and
        # other is not 
        elif (n1.left or n2.left): 
            return False
  
        # Right child code (Similar to 
        # left child code) 
        if (n1.right and n2.right):
            q1.put(n1.right) 
            q2.put(n2.right)
        elif (n1.right or n2.right): 
            return False
  
    return True
  
# Driver Code
if __name__ == '__main__':
    root1 = newNode(1) 
    root1.left = newNode(2) 
    root1.right = newNode(3) 
    root1.left.left = newNode(4) 
    root1.left.right = newNode(5) 
  
    root2 = newNode(1) 
    root2.left = newNode(2) 
    root2.right = newNode(3) 
    root2.left.left = newNode(4) 
    root2.left.right = newNode(5) 
  
    if areIdentical(root1, root2):
        print("Yes")
    else:
        print("No")
          
# This code is contributed by PranchalK

C#

/* Iterative C# program to check if two */
using System;
using System.Collections.Generic;
  
class GfG 
{ 
  
// A Binary Tree Node 
class Node 
{ 
    public int data; 
    public Node left, right; 
} 
  
// Iterative method to find height of Binary Tree 
static bool areIdentical(Node root1, Node root2) 
{ 
    // Return true if both trees are empty 
    if (root1 == null && root2 == null) 
        return true; 
  
    // Return false if one is empty and other is not 
    if (root1 == null || root2 == null) 
        return false; 
  
    // Create an empty queues for 
    // simultaneous traversals 
    Queue<Node> q1 = new Queue<Node> (); 
    Queue<Node> q2 = new Queue<Node> (); 
  
    // Enqueue Roots of trees in respective queues 
    q1.Enqueue(root1); 
    q2.Enqueue(root2); 
  
    while (q1.Count != 0 && q2.Count != 0) 
    { 
        // Get front nodes and compare them 
        Node n1 = q1.Peek(); 
        Node n2 = q2.Peek(); 
  
        if (n1.data != n2.data) 
        return false; 
  
        // Remove front nodes from queues 
        q1.Dequeue(); 
        q2.Dequeue(); 
  
        /* Enqueue left children of both nodes */
        if (n1.left != null && n2.left != null) 
        { 
            q1.Enqueue(n1.left); 
            q2.Enqueue(n2.left); 
        } 
  
        // If one left child is empty and other is not 
        else if (n1.left != null || n2.left != null) 
            return false; 
  
        // Right child code (Similar to left child code) 
        if (n1.right != null && n2.right != null) 
        { 
            q1.Enqueue(n1.right); 
            q2.Enqueue(n2.right); 
        } 
        else if (n1.right != null || n2.right != null) 
            return false; 
    } 
  
    return true; 
} 
  
// Utility function to create a new tree node 
static Node newNode(int data) 
{ 
    Node temp = new Node(); 
    temp.data = data; 
    temp.left = null; 
    temp.right = null; 
    return temp; 
} 
  
// Driver code 
public static void Main(String[] args) 
{ 
    Node root1 = newNode(1); 
    root1.left = newNode(2); 
    root1.right = newNode(3); 
    root1.left.left = newNode(4); 
    root1.left.right = newNode(5); 
  
    Node root2 = newNode(1); 
    root2.left = newNode(2); 
    root2.right = newNode(3); 
    root2.left.left = newNode(4); 
    root2.left.right = newNode(5); 
  
    if(areIdentical(root1, root2) == true) 
    Console.WriteLine("Yes"); 
    else
    Console.WriteLine("No"); 
} 
} 
  
// This code is contributed by PrinciRaj1992

Javascript

<script>
   
/* Iterative Javascript program to check if two */
  
// A Binary Tree Node 
class Node 
{ 
  constructor()
  {
    this.data = 0;
    this.left = null;
    this.right = null;
  }
} 
  
// Iterative method to find height of Binary Tree 
function areIdentical(root1, root2) 
{ 
    // Return true if both trees are empty 
    if (root1 == null && root2 == null) 
        return true; 
  
    // Return false if one is empty and other is not 
    if (root1 == null || root2 == null) 
        return false; 
  
    // Create an empty queues for 
    // simultaneous traversals 
    var q1 = []; 
    var q2 = []; 
  
    // push Roots of trees in respective queues 
    q1.push(root1); 
    q2.push(root2); 
  
    while (q1.length != 0 && q2.length != 0) 
    { 
        // Get front nodes and compare them 
        var n1 = q1[0]; 
        var n2 = q2[0]; 
  
        if (n1.data != n2.data) 
        return false; 
  
        // Remove front nodes from queues 
        q1.shift(); 
        q2.shift(); 
  
        /* push left children of both nodes */
        if (n1.left != null && n2.left != null) 
        { 
            q1.push(n1.left); 
            q2.push(n2.left); 
        } 
  
        // If one left child is empty and other is not 
        else if (n1.left != null || n2.left != null) 
            return false; 
  
        // Right child code (Similar to left child code) 
        if (n1.right != null && n2.right != null) 
        { 
            q1.push(n1.right); 
            q2.push(n2.right); 
        } 
        else if (n1.right != null || n2.right != null) 
            return false; 
    } 
  
    return true; 
} 
  
// Utility function to create a new tree node 
function newNode(data) 
{ 
    var temp = new Node(); 
    temp.data = data; 
    temp.left = null; 
    temp.right = null; 
    return temp; 
} 
  
// Driver code 
var root1 = newNode(1); 
root1.left = newNode(2); 
root1.right = newNode(3); 
root1.left.left = newNode(4); 
root1.left.right = newNode(5); 
var root2 = newNode(1); 
root2.left = newNode(2); 
root2.right = newNode(3); 
root2.left.left = newNode(4); 
root2.left.right = newNode(5); 
if(areIdentical(root1, root2) == true) 
  document.write("Yes"); 
else
  document.write("No"); 
  
</script>

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

Deja una respuesta

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