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.
Algoritmo:
sameTree(tree1, tree2)
1. If both trees are empty then return 1.
2. Else If both trees are non -empty
(a) Check data of the root nodes (tree1->data == tree2->data)
(b) Check left subtrees recursively i.e., call sameTree(
tree1->left_subtree, tree2->left_subtree)
(c) Check right subtrees recursively i.e., call sameTree(
tree1->right_subtree, tree2->right_subtree)
(d) If a,b and c are true then return 1.
3 Else return 0 (one is empty and other is not)
Código:
C++
// C++ program to see if two trees are identical
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node
{
public:
int data;
node* left;
node* right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode(int data)
{
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
/* Given two trees, return true if they are
structurally identical */
int identicalTrees(node* a, node* b)
{
/*1. both empty */
if (a == NULL && b == NULL)
return 1;
/* 2. both non-empty -> compare them */
if (a != NULL && b != NULL)
{
return
(
a->data == b->data &&
identicalTrees(a->left, b->left) &&
identicalTrees(a->right, b->right)
);
}
/* 3. one empty, one not -> false */
return 0;
}
/* Driver code*/
int main()
{
node *root1 = newNode(1);
node *root2 = newNode(1);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(4);
root1->left->right = newNode(5);
root2->left = newNode(2);
root2->right = newNode(3);
root2->left->left = newNode(4);
root2->left->right = newNode(5);
if(identicalTrees(root1, root2))
cout << "Both tree are identical.";
else
cout << "Trees are not identical.";
return 0;
}
// This code is contributed by rathbhupendra
C
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
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);
}
/* Given two trees, return true if they are
structurally identical */
int identicalTrees(struct node* a, struct node* b)
{
/*1. both empty */
if (a==NULL && b==NULL)
return 1;
/* 2. both non-empty -> compare them */
if (a!=NULL && b!=NULL)
{
return
(
a->data == b->data &&
identicalTrees(a->left, b->left) &&
identicalTrees(a->right, b->right)
);
}
/* 3. one empty, one not -> false */
return 0;
}
/* Driver program to test identicalTrees function*/
int main()
{
struct node *root1 = newNode(1);
struct node *root2 = newNode(1);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(4);
root1->left->right = newNode(5);
root2->left = newNode(2);
root2->right = newNode(3);
root2->left->left = newNode(4);
root2->left->right = newNode(5);
if(identicalTrees(root1, root2))
printf("Both tree are identical.");
else
printf("Trees are not identical.");
getchar();
return 0;
}
Java
// Java program to see if two trees are identical
// A binary tree node
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree
{
Node root1, root2;
/* Given two trees, return true if they are
structurally identical */
boolean identicalTrees(Node a, Node b)
{
/*1. both empty */
if (a == null && b == null)
return true;
/* 2. both non-empty -> compare them */
if (a != null && b != null)
return (a.data == b.data
&& identicalTrees(a.left, b.left)
&& identicalTrees(a.right, b.right));
/* 3. one empty, one not -> false */
return false;
}
/* Driver program to test identicalTrees() function */
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root1 = new Node(1);
tree.root1.left = new Node(2);
tree.root1.right = new Node(3);
tree.root1.left.left = new Node(4);
tree.root1.left.right = new Node(5);
tree.root2 = new Node(1);
tree.root2.left = new Node(2);
tree.root2.right = new Node(3);
tree.root2.left.left = new Node(4);
tree.root2.left.right = new Node(5);
if (tree.identicalTrees(tree.root1, tree.root2))
System.out.println("Both trees are identical");
else
System.out.println("Trees are not identical");
}
}
Python3
# Python program to determine if two trees are identical
# A binary tree node has data, pointer to left child
# and a pointer to right child
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Given two trees, return true if they are structurally
# identical
def identicalTrees(a, b):
# 1. Both empty
if a is None and b is None:
return True
# 2. Both non-empty -> Compare them
if a is not None and b is not None:
return ((a.data == b.data) and
identicalTrees(a.left, b.left)and
identicalTrees(a.right, b.right))
# 3. one empty, one not -- false
return False
# Driver program to test identicalTress function
root1 = Node(1)
root2 = Node(1)
root1.left = Node(2)
root1.right = Node(3)
root1.left.left = Node(4)
root1.left.right = Node(5)
root2.left = Node(2)
root2.right = Node(3)
root2.left.left = Node(4)
root2.left.right = Node(5)
if identicalTrees(root1, root2):
print("Both trees are identical")
else:
print ("Trees are not identical")
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
using System;
// C# program to see if two trees are identical
// A binary tree node
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree
{
public Node root1, root2;
/* Given two trees, return true if they are
structurally identical */
public virtual bool identicalTrees(Node a, Node b)
{
/*1. both empty */
if (a == null && b == null)
{
return true;
}
/* 2. both non-empty -> compare them */
if (a != null && b != null)
{
return (a.data == b.data && identicalTrees(a.left, b.left) && identicalTrees(a.right, b.right));
}
/* 3. one empty, one not -> false */
return false;
}
/* Driver program to test identicalTrees() function */
public static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
tree.root1 = new Node(1);
tree.root1.left = new Node(2);
tree.root1.right = new Node(3);
tree.root1.left.left = new Node(4);
tree.root1.left.right = new Node(5);
tree.root2 = new Node(1);
tree.root2.left = new Node(2);
tree.root2.right = new Node(3);
tree.root2.left.left = new Node(4);
tree.root2.left.right = new Node(5);
if (tree.identicalTrees(tree.root1, tree.root2))
{
Console.WriteLine("Both trees are identical");
}
else
{
Console.WriteLine("Trees are not identical");
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// JavaScript program to see if two trees are identical
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
let root1, root2;
/* Given two trees, return true if they are
structurally identical */
function identicalTrees(a, b)
{
/*1. both empty */
if (a == null && b == null)
return true;
/* 2. both non-empty -> compare them */
if (a != null && b != null)
return (a.data == b.data
&& identicalTrees(a.left, b.left)
&& identicalTrees(a.right, b.right));
/* 3. one empty, one not -> false */
return false;
}
root1 = new Node(1);
root1.left = new Node(2);
root1.right = new Node(3);
root1.left.left = new Node(4);
root1.left.right = new Node(5);
root2 = new Node(1);
root2.left = new Node(2);
root2.right = new Node(3);
root2.left.left = new Node(4);
root2.left.right = new Node(5);
if (identicalTrees(root1, root2))
document.write("Both trees are identical");
else
document.write("Trees are not identical");
</script>
Producción
Both tree are identical.
Complejidad de tiempo:
La complejidad del árbol idéntico() será de acuerdo con el árbol con menor número de Nodes. Sea m y n el número de Nodes en dos árboles, entonces la complejidad de sameTree() es O(m) donde m < n.
Enfoque 2: encontrar recorridos
Otro enfoque puede ser pensar que si dos árboles son idénticos, sus recorridos en preorden, en orden y en orden posterior también serán los mismos.
Para esto podemos encontrar un recorrido, digamos en orden, y si es el mismo para ambos árboles, ¿podemos decir que los árboles dados son idénticos? No, porque podemos tener dos árboles con el mismo recorrido en orden, aún así pueden ser no idénticos.
Vea el siguiente ejemplo:
Tree 1: 2 Tree 2: 1
/ \
1 2
Ambos árboles tienen un recorrido en orden como «2 1», pero no son idénticos.
Solución: para abordar estos casos extremos, debemos encontrar todo el recorrido de ambos árboles y ver si son iguales. En caso afirmativo, los árboles dados son idénticos, de lo contrario no.
Código:
Java
/* java code to check if two trees are identical */
import java.io.*;
import java.util.*;
public class GFG {
/* A binary tree node */
static class Node{
int data;
Node left,right;
public Node(int data){this.data = data;}
}
//driver code below
public static void main(String[] args){
Node root1 = new Node(1);
root1.left = new Node(2);
root1.right = new Node(3);
root1.left.left = new Node(4);
root1.left.right = new Node(5);
Node root2 = new Node(1);
root2.left = new Node(2);
root2.right = new Node(3);
root2.left.left = new Node(4);
root2.left.right = new Node(5);
if(isIdentical(root1,root2)){
System.out.println("Both the trees are identical.");
}else{
System.out.println("Given trees are not identical.");
}
}
//function to check if two trees are identical
static boolean isIdentical(Node root1, Node root2)
{
// Code Here
//Create two arraylist to store traversals
ArrayList<Integer> res1 = new ArrayList<Integer>();
ArrayList<Integer> res2 = new ArrayList<Integer>();
//check inOrder
inOrder(root1, res1);
inOrder(root2,res2);
if(!res1.equals(res2)) return false;
//clear previous result to reuse arraylist
res1.clear();
res2.clear();
//check PreOrder
preOrder(root1, res1);
preOrder(root2, res2);
if(!res1.equals(res2)) return false;
//clear previous result to reuse arraylist
res1.clear();
res2.clear();
//check PostOrder
postOrder(root1, res1);
postOrder(root2, res2);
if(!res1.equals(res2)) return false;
return true;
}
//utility function to check inorder traversal
static void inOrder(Node root, ArrayList<Integer> sol){
if(root == null) return;
inOrder(root.left, sol);
sol.add(root.data);
inOrder(root.right,sol);
}
//utility function to check preorder traversal
static void preOrder(Node root, ArrayList<Integer> sol){
if(root == null) return;
sol.add(root.data);
preOrder(root.left, sol);
preOrder(root.right,sol);
}
//utility function to check postorder traversal
static void postOrder(Node root, ArrayList<Integer> sol){
if(root == null) return;
postOrder(root.left, sol);
postOrder(root.right,sol);
sol.add(root.data);
}
}
Producción
Both the trees are identical.
Complejidad temporal: O(n)
Dado que solo estamos llamando funciones para atravesar el árbol, la complejidad de tiempo para el mismo será O (n). Donde n es el número de Nodes del árbol con más Nodes.
Complejidad espacial: O(n)
desde el uso de ArrayList auxiliar y pila de llamadas
Función iterativa para verificar si dos árboles son idénticos.
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