判断两个树是否相同的Java程序

1 简介

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

• 两棵树的结构应相同。
• 一棵树中存在的节点应该出现在另一棵树中。

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

2 算法思路

• 定义具有三个属性的Node类，即：左和右数据。在此，左代表节点的左子节点，右代表节点的右子节点。
• 创建节点时，数据将传递到该节点的data属性，并且左右都将设置为null。
• 定义另一个具有属性根的类。
  • 根表示树的根节点，并将其初始化为null。
• areIdenticalTrees（）将检查两棵树是否相同：
  • 如果两个树的根节点都为空，则它们是相同的。
  • 如果仅一棵树的根节点为空，则树不相同，则返回false。
  • 如果没有一棵树的根节点为空，则检查两个节点的数据是否相等，然后递归检查一棵树的左子树和右子树是否与另一棵树相同。

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
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