Dados dos árboles binarios. La tarea es escribir un programa para verificar si los dos árboles tienen una estructura idéntica.
En la figura anterior, ambos árboles, Tree1 y Tree2, tienen una estructura idéntica. Es decir, tienen la misma estructura.
Nota : este problema es diferente de Verificar si dos árboles son idénticos , ya que aquí necesitamos comparar solo las estructuras de los dos árboles y no los valores en sus Nodes.
La idea es atravesar ambos árboles simultáneamente siguiendo los mismos caminos y seguir comprobando si existe un Node para ambos árboles o no.
Algoritmo :
- Si ambos árboles están vacíos, devuelve 1.
- De lo contrario, si ambos árboles no están vacíos:
- Compruebe los subárboles izquierdos de forma recursiva, es decir, llame a isSameStructure(tree1->left_subtree, tree2->left_subtree)
- Verifique los subárboles correctos recursivamente, es decir, llame a isSameStructure (árbol1-> subárbol_derecho, árbol2-> subárbol_derecho)
- Si el valor devuelto en los dos pasos anteriores es verdadero, devuelva 1.
- De lo contrario, devuelve 0 (uno está vacío y el otro no).
A continuación se muestra la implementación del algoritmo anterior:
C++
// C++ program to check if two trees have
// same structure
#include <iostream>
using namespace std;
// 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.
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
// Function to check if two trees have same
// structure
int isSameStructure(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
(
isSameStructure(a->left, b->left) &&
isSameStructure(a->right, b->right)
);
}
// 3. one empty, one not -> false
return 0;
}
// Driver code
int main()
{
Node *root1 = newNode(10);
Node *root2 = newNode(100);
root1->left = newNode(7);
root1->right = newNode(15);
root1->left->left = newNode(4);
root1->left->right = newNode(9);
root1->right->right = newNode(20);
root2->left = newNode(70);
root2->right = newNode(150);
root2->left->left = newNode(40);
root2->left->right = newNode(90);
root2->right->right = newNode(200);
if (isSameStructure(root1, root2))
printf("Both trees have same structure");
else
printf("Trees do not have same structure");
return 0;
}
// This code is contributed by aditya kumar (adityakumar129)
C
// C++ program to check if two trees have
// same structure
#include <stdio.h>
#include <stdlib.h>
// A binary tree node has data, pointer to left child
// and a pointer to right child
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
// Helper function that allocates a new node with the
// given data and NULL left and right pointers.
Node* newNode(int data)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
// Function to check if two trees have same
// structure
int isSameStructure(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 (isSameStructure(a->left, b->left)
&& isSameStructure(a->right, b->right));
}
// 3. one empty, one not -> false
return 0;
}
// Driver code
int main()
{
Node* root1 = newNode(10);
Node* root2 = newNode(100);
root1->left = newNode(7);
root1->right = newNode(15);
root1->left->left = newNode(4);
root1->left->right = newNode(9);
root1->right->right = newNode(20);
root2->left = newNode(70);
root2->right = newNode(150);
root2->left->left = newNode(40);
root2->left->right = newNode(90);
root2->right->right = newNode(200);
if (isSameStructure(root1, root2))
printf("Both trees have same structure");
else
printf("Trees do not have same structure");
return 0;
}
// This code is contributed by aditya kumar (adityakumar129)
Java
// Java program to check if two trees have
// same structure
class GFG
{
// A binary tree node has data,
// pointer to left child and
// a pointer to right child
static class Node
{
int data;
Node left;
Node right;
};
// Helper function that allocates a new node
// with the given data and null left
// and right pointers.
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return(node);
}
// Function to check if two trees
// have same structure
static boolean isSameStructure(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
(
isSameStructure(a.left, b.left) &&
isSameStructure(a.right, b.right)
);
}
// 3. one empty, one not . false
return false;
}
// Driver code
public static void main(String args[])
{
Node root1 = newNode(10);
Node root2 = newNode(100);
root1.left = newNode(7);
root1.right = newNode(15);
root1.left.left = newNode(4);
root1.left.right = newNode(9);
root1.right.right = newNode(20);
root2.left = newNode(70);
root2.right = newNode(150);
root2.left.left = newNode(40);
root2.left.right = newNode(90);
root2.right.right = newNode(200);
if (isSameStructure(root1, root2))
System.out.printf("Both trees have same structure");
else
System.out.printf("Trees do not have same structure");
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to check if two trees have
# same structure
# A binary tree node has data, pointer to left child
# and a pointer to right child
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Helper function that allocates a new node with the
# given data and None left and right pointers.
def newNode(data):
node = Node(data)
return node
# Function to check if two trees have same
# structure
def isSameStructure(a, b):
# 1. both empty
if (a == None and b == None):
return 1;
# 2. both non-empty . compare them
if (a != None and b != None):
return (
isSameStructure(a.left, b.left) and
isSameStructure(a.right, b.right))
# 3. one empty, one not . false
return 0;
# Driver code
if __name__=='__main__':
root1 = newNode(10);
root2 = newNode(100);
root1.left = newNode(7);
root1.right = newNode(15);
root1.left.left = newNode(4);
root1.left.right = newNode(9);
root1.right.right = newNode(20);
root2.left = newNode(70);
root2.right = newNode(150);
root2.left.left = newNode(40);
root2.left.right = newNode(90);
root2.right.right = newNode(200);
if (isSameStructure(root1, root2)):
print("Both trees have same structure");
else:
print("Trees do not have same structure");
# This code is contributed by rutvik_56
C#
// C# program to check if two trees
// have same structure
using System;
class GFG
{
// A binary tree node has data,
// pointer to left child and
// a pointer to right child
public class Node
{
public int data;
public Node left;
public Node right;
};
// Helper function that allocates a new node
// with the given data and null left
// and right pointers.
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return(node);
}
// Function to check if two trees
// have same structure
static Boolean isSameStructure(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
(
isSameStructure(a.left, b.left) &&
isSameStructure(a.right, b.right)
);
}
// 3. one empty, one not . false
return false;
}
// Driver code
public static void Main(String []args)
{
Node root1 = newNode(10);
Node root2 = newNode(100);
root1.left = newNode(7);
root1.right = newNode(15);
root1.left.left = newNode(4);
root1.left.right = newNode(9);
root1.right.right = newNode(20);
root2.left = newNode(70);
root2.right = newNode(150);
root2.left.left = newNode(40);
root2.left.right = newNode(90);
root2.right.right = newNode(200);
if (isSameStructure(root1, root2))
Console.Write("Both trees have " +
"same structure");
else
Console.Write("Trees do not have" +
" same structure");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to check if two trees
// have same structure
// A binary tree node has data,
// pointer to left child and
// a pointer to right child
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
// Helper function that allocates a new node
// with the given data and null left
// and right pointers.
function newNode(data)
{
var node = new Node();
node.data = data;
node.left = null;
node.right = null;
return node;
}
// Function to check if two trees
// have same structure
function isSameStructure(a, b)
{
// 1. both empty
if (a == null && b == null)
return true;
// 2. both non-empty . compare them
if (a != null && b != null)
{
return isSameStructure(a.left, b.left) &&
isSameStructure(a.right, b.right) ;
}
// 3. one empty, one not . false
return false;
}
// Driver code
var root1 = newNode(10);
var root2 = newNode(100);
root1.left = newNode(7);
root1.right = newNode(15);
root1.left.left = newNode(4);
root1.left.right = newNode(9);
root1.right.right = newNode(20);
root2.left = newNode(70);
root2.right = newNode(150);
root2.left.left = newNode(40);
root2.left.right = newNode(90);
root2.right.right = newNode(200);
if (isSameStructure(root1, root2))
document.write("Both trees have " +
"same structure");
else
document.write("Trees do not have" +
" same structure");
</script>
Producción:
Both trees have same structure
Publicación traducida automáticamente
Artículo escrito por Premdeep Toppo y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA