问：判断两棵树是否相同的程序。

2025年3月17日 | 阅读 7 分钟

说明

在此程序中，我们需要检查两棵树是否相同。要使两棵树相同，它们必须满足两个条件：

两棵树的结构必须相同。
一棵树中的节点也必须存在于另一棵树中。

Program to determine whether two trees are identical

上图包含三棵树，分别是 A、B 和 C。树 A 和树 B 是相同的，因为它们的结构相同且所有节点的值都相同。然而，树 A 和树 C 的结构相同，但并不相同，因为两棵树中的节点是不同的。

算法

定义 Node 类，它有三个属性：data、left 和 right。其中，left 表示节点的左子节点，right 表示节点的右子节点。
创建节点时，将数据传递给节点的 data 属性，并将 left 和 right 都设置为 null。
定义另一个类，该类有一个 root 属性。
1. Root 表示树的根节点，并将其初始化为 null。
areIdenticalTrees() 函数将检查两棵树是否相同。
1. 如果两棵树的根节点都为空，则它们相同。
2. 如果只有一棵树的根节点为空，则两棵树不相同，返回 false。
3. 如果两棵树的根节点都不为空，则检查两个节点的数值是否相等，然后递归地检查一棵树的左子树和右子树是否与另一棵树相同。

解决方案

Python

#Represent a node of binary tree
class Node:
    def __init__(self,data):
        #Assign data to the new node, set left and right children to None
        self.data = data;
        self.left = None;
        self.right = None;
 
class IdenticalTrees:
    def __init__(self):
        #Represent the root of binary tree
        self.root = None;
        
    #areIdenticalTrees() finds whether two trees are identical or not
    @staticmethod
    def areIdenticalTrees(root1, root2):
        #Checks if both the trees are empty
        if(root1 == None and root2 == None):
            return True;
        #Trees are not identical if root of only one tree is null thus, return false
        if(root1 == None and root2 == None):
            return True;
        #If both trees are not empty, check whether the data of the nodes is equal
        #Repeat the steps for left subtree and right subtree
        if(root1 != None  and root2 != None):
            return ((root1.data == root2.data) and 
            (IdenticalTrees.areIdenticalTrees(root1.left, root2.left)) and 
            (IdenticalTrees.areIdenticalTrees(root1.right, root2.right)));
        return False;
        
#Adding nodes to the first binary tree
bt1 = IdenticalTrees();
bt1.root = Node(1);
bt1.root.left = Node(2);
bt1.root.right = Node(3);
bt1.root.left.left = Node(4);
bt1.root.right.left = Node(5);
bt1.root.right.right = Node(6);
 
#Adding nodes to the second binary tree
bt2 = IdenticalTrees();
bt2.root = Node(1);
bt2.root.left = Node(2);
bt2.root.right = Node(3);
bt2.root.left.left = Node(4);
bt2.root.right.left = Node(5);
bt2.root.right.right = Node(6);  
 
#Displays whether both the trees are identical or not
if(IdenticalTrees.areIdenticalTrees(bt1.root, bt2.root)):
    print("Both the binary trees are identical");
else:
    print("Both the binary trees are not identical");

输出

Both the binary trees are identical

C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
//Represent a node of binary tree
struct node{
    int data;
    struct node *left;
    struct node *right;
};
 
//Represent the root node of first binary tree
struct node *rootTree1 = NULL;
//Represent the root node of second binary tree
struct node *rootTree2 = NULL;
    
//createNode() will create a new node
struct node* createNode(int data){
    //Create a new node
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    //Assign data to newNode, set left and right children to NULL
    newNode->data= data;
    newNode->left = NULL;
    newNode->right = NULL;
    
    return newNode;
}
 
//areIdenticalTrees() finds whether two trees are identical or not
bool areIdenticalTrees(struct node *root1, struct node *root2) {
      
    //Checks if both the trees are empty
    if(root1 == NULL && root2 == NULL)
          return true;
    
    //Trees are not identical if root of only one tree is null thus, return false
    if(root1 == NULL && root2 == NULL)
          return true;
    
    //If both trees are not empty, check whether the data of the nodes is equal
    //Repeat the steps for left subtree and right subtree
    if(root1 != NULL  && root2 != NULL) {
          
          return ((root1->data == root2->data) &&
                  (areIdenticalTrees(root1->left, root2->left)) &&
                  (areIdenticalTrees(root1->right, root2->right)));
    }
    return false;
}
      
 
int main()
{
    //Adding nodes to the first binary tree
    rootTree1 = createNode(1);
    rootTree1->left = createNode(2);
    rootTree1->right = createNode(3);
    rootTree1->left->left = createNode(4);
    rootTree1->right->left = createNode(5);
    rootTree1->right->right = createNode(6);
    
    //Adding nodes to the second binary tree
    rootTree2 = createNode(1);
    rootTree2->left = createNode(2);
    rootTree2->right = createNode(3);
    rootTree2->left->left = createNode(4);
    rootTree2->right->left = createNode(5);
    rootTree2->right->right = createNode(6);  
    
    //Displays whether both the trees are identical or not
    if(areIdenticalTrees(rootTree1, rootTree2))
        printf("Both the binary trees are identical");
    else
        printf("Both the binary trees are not identical");
 
    return 0;
}

输出

Both the binary trees are identical

JAVA

public class IdenticalTrees {
    
      //Represent the node of the binary tree
      public static class Node{
        int data;
        Node left;
        Node right;
        
        //Assign data to the new node, set left and right children to null
        public Node(int data){
          this.data = data;
          this.left = null;
          this.right = null;
        }
      }
      
      //Represent the root of the binary tree
      public Node root;
      
      public IdenticalTrees(){
        root = null;
      }
      
      //areIdenticalTrees() finds whether two trees are identical or not
      public static boolean areIdenticalTrees(Node root1, Node root2) {
          
          //Checks if both the trees are empty
          if(root1 == null && root2 == null)
              return true;
          
          //Trees are not identical if root of only one tree is null thus, return false
          if(root1 == null && root2 == null)
              return true;
          
          //If both trees are not empty, check whether the data of the nodes is equal
          //Repeat the steps for left subtree and right subtree
          if(root1 != null  && root2 != null) {
              
              return ((root1.data == root2.data) &&
                      (areIdenticalTrees(root1.left, root2.left)) &&
                      (areIdenticalTrees(root1.right, root2.right)));
          }
          return false;
      }
      
      
      public static void main(String[] args) {
        
        //Adding nodes to the first binary tree
        IdenticalTrees bt1 = new IdenticalTrees();
        bt1.root = new Node(1);
        bt1.root.left = new Node(2);
        bt1.root.right = new Node(3);
        bt1.root.left.left = new Node(4);
        bt1.root.right.left = new Node(5);
        bt1.root.right.right = new Node(6);
        
        //Adding nodes to the second binary tree
          IdenticalTrees bt2 = new IdenticalTrees();
          bt2.root = new Node(1);
          bt2.root.left = new Node(2);
          bt2.root.right = new Node(3);
          bt2.root.left.left = new Node(4);
          bt2.root.right.left = new Node(5);
          bt2.root.right.right = new Node(6);  
          
          //Displays whether both the trees are identical or not
           if(areIdenticalTrees(bt1.root, bt2.root))
             System.out.println("Both the binary trees are identical");
         else
             System.out.println("Both the binary trees are not identical");
        }
}

输出

Both the binary trees are identical

C#

using System;
namespace Tree 
{                     
    public class Program
    {
        //Represent a node of binary tree
        public class Node<T>{
            public T data;
            public Node<T> left;
            public Node<T> right;
            
            public Node(T data) {
                //Assign data to the new node, set left and right children to null
                this.data = data;
                this.left = null;
                this.right = null;
            }
        }
        
        public class IdenticalTrees<T>{
            //Represent the root of binary tree
            public Node<T> root;
            
            public IdenticalTrees(){
                root = null;
            }
            
        //areIdenticalTrees() finds whether two trees are identical or not
        public static Boolean areIdenticalTrees(Node<T> root1, Node<T> root2) {
          
          //Checks if both the trees are empty
          if(root1 == null && root2 == null)
              return true;
          
          //Trees are not identical if root of only one tree is null thus, return false
          if(root1 == null && root2 == null)
              return true;
          
          //If both trees are not empty, check whether the data of the nodes is equal
          //Repeat the steps for left subtree and right subtree
          if(root1 != null  && root2 != null) {
              
              return ((root1.data.Equals(root2.data)) &&
                      (areIdenticalTrees(root1.left, root2.left)) &&
                      (areIdenticalTrees(root1.right, root2.right)));
          }
          return false;
        }
    }
        
        public static void Main()
        {
            //Adding nodes to the first binary tree
            IdenticalTrees<int> bt1 = new IdenticalTrees<int>();
            bt1.root = new Node<int>(1);
            bt1.root.left = new Node<int>(2);
            bt1.root.right = new Node<int>(3);
            bt1.root.left.left = new Node<int>(4);
            bt1.root.right.left = new Node<int>(5);
            bt1.root.right.right = new Node<int>(6);
            
            //Adding nodes to the second binary tree
              IdenticalTrees<int> bt2 = new IdenticalTrees<int>();
              bt2.root = new Node<int>(1);
              bt2.root.left = new Node<int>(2);
              bt2.root.right = new Node<int>(3);
              bt2.root.left.left = new Node<int>(4);
              bt2.root.right.left = new Node<int>(5);
              bt2.root.right.right = new Node<int>(6);  
              
              //Displays whether both the trees are identical or not
               if(IdenticalTrees<int>.areIdenticalTrees(bt1.root, bt2.root))
                 Console.WriteLine("Both the binary trees are identical");
             else
                 Console.WriteLine("Both the binary trees are not identical");                
        }    
    }
}

输出

Both the binary trees are identical

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
    public $data;
    public $left;
    public $right;
    
    function __construct($data){
        //Assign data to the new node, set left and right children to NULL
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class IdenticalTrees{
    //Represent the root of binary tree
    public $root;
    function __construct(){
        $this->root = NULL;
    }
    
    //areIdenticalTrees() finds whether two trees are identical or not
    static function areIdenticalTrees($root1, $root2) {
        
        //Checks if both the trees are empty
        if($root1 == NULL && $root2 == NULL)
            return true;
          
          //Trees are not identical if root of only one tree is null thus, return false
          if($root1 == NULL && $root2 == NULL)
              return true;
          
          //If both trees are not empty, check whether the data of the nodes is equal
          //Repeat the steps for left subtree and right subtree
          if($root1 != NULL  && $root2 != NULL) {
              
              return (($root1->data == $root2->data) &&
                      (IdenticalTrees::areIdenticalTrees($root1->left, $root2->left)) &&
                      (IdenticalTrees::areIdenticalTrees($root1->right, $root2->right)));
          }
          return false;
      }    
}
//Adding nodes to the first binary tree
$bt1 = new IdenticalTrees();
$bt1->root = new Node(1);
$bt1->root->left = new Node(2);
$bt1->root->right = new Node(3);
$bt1->root->left->left = new Node(4);
$bt1->root->right->left = new Node(5);
$bt1->root->right->right = new Node(6);
 
//Adding nodes to the second binary tree
$bt2 = new IdenticalTrees();
$bt2->root = new Node(1);
$bt2->root->left = new Node(2);
$bt2->root->right = new Node(3);
$bt2->root->left->left = new Node(4);
$bt2->root->right->left = new Node(5);
$bt2->root->right->right = new Node(6);  
          
//Displays whether both the trees are identical or not
if(IdenticalTrees::areIdenticalTrees($bt1->root, $bt2->root))
    print("Both the binary trees are identical");
else
    print("Both the binary trees are not identical");      
?>
</body>
</html>

输出

Both the binary trees are identical

下一个主题程序列表

问：判断两棵树是否相同的程序。

说明

算法

解决方案

Python

C

JAVA

C#

PHP

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

程序

问：判断两棵树是否相同的程序。

说明

算法

解决方案

Python

C

JAVA

C#

PHP

相关帖子

对循环链表元素进行排序的程序

打印数组所有元素之和的程序

打印数字图案 9 的程序

数组元素左移的程序

打印数字图案 5 的程序

打印 1 到 100 之间的所有丰数的程序

编写计算等腰三角形面积的程序

不使用模运算符打印数字之和的程序

对单链表元素进行排序的程序

在双向链表中搜索元素的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器