Java来确定两棵树是否相同
在此程序中，我们需要检查两个树是否相同。要使两棵树相同，它们必须满足两个条件:
两棵树的结构应该相同。
在一棵树中存在的节点应该在另一棵树中存在。
上图包含三棵树，即A，B和C。树A和B相同，因为它们在结构上相同，并且所有节点的值都相同。但是，树A和C在结构上是相同的，但并不相同，因为两个树中的节点都是不同的。
算法
定义Node类，它具有三个属性，即: 左和右数据。在这里，左代表节点的左子节点，右代表节点的右子节点。
创建节点后，数据将传递到该节点的data属性，并且左右都将设置为null。
定义另一个具有属性根的类。 Root表示树的根节点，并将其初始化为null。
areIdenticalTrees()将检查两棵树是否相同: 如果两棵树的根节点均为空，则它们是相同的。 如果只有一棵树的根节点为空，则树不相同，则返回false。 如果没有树的根节点为空，则检查两个节点的数据是否相等，然后递归检查一棵树的左子树和右子树是否与另一棵树相同。
程序:
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
