判断两棵二叉树是否相等（Java实现）

以你之姓@ 2024-04-19 16:23 49阅读 0赞

判断树是否相等，就是判断树中的每一个节点是否相等，根节点和根节点做比较，根节点的左子节点和左子节点作比较，右子节点和右子节点作比较，直到没有节点比较为止，中间只要一个节点不相等，就返回false，只有都相等才返回true。

这里是树结构，遍历的话只能通过递归调用遍历每一个节点以及它的左右子节点。考虑使用递归的思想。但是递归需要判断终止条件，这里终止条件就是节点为空，它的父节点已经是叶子节点了。

使用Java实现代码如下：

package com.xxx.algorithm.tree;
    
    public class Tree {
    	
    	public TreeNode root;
    	public void insert(int data){
    		TreeNode node = new TreeNode(data);
    		if(root==null){
    			root = node;
    		}else{
    			TreeNode cur = root;
    			TreeNode parent = null;
    			while(true){
    				parent = cur;
    				if(data<cur.data){			
    					cur = cur.left;
    					if(cur==null){
    						parent.left = node;
    						break;
    					}
    				}else{
    					cur = cur.right;
    					if(cur==null){
    						parent.right = node;
    						break;
    					}
    				}
    			}
    		}
    	}
    	
    	public void preOrder(TreeNode node){
    		if(node!=null){
    			System.out.print(node.data+" ");
    			preOrder(node.left);
    			preOrder(node.right);
    		}
    	}
    
    	public void inOrder(TreeNode node){
    		if(node!=null){
    			inOrder(node.left);
    			System.out.print(node.data+" ");
    			inOrder(node.right);
    		}
    	}
    	
    	public static boolean equals(TreeNode n1,TreeNode n2){
    		if(n1==null && n2==null)
    			return true;
    		else if(n1!=null && n2!=null){
    			if(n1.data==n2.data)
    				return equals(n1.left, n2.left) && equals(n1.right, n2.right);
    		}
    		return false;
    	}
    	
    	public static void main(String[] args) {
    		Tree tree = new Tree();
    		tree.insert(10);
    		tree.insert(5);
    		tree.insert(12);
    		tree.insert(3);
    		tree.insert(7);
    		
    		Tree tree2 = new Tree();
    		tree2.insert(10);
    		tree2.insert(5);
    		tree2.insert(12);
    		tree2.insert(3);
    		tree2.insert(7);
    		
    		tree.preOrder(tree.root);
    		System.out.println();
    		tree.preOrder(tree2.root);
    		System.out.println();
    		
    		System.out.println(equals(tree.root, tree2.root));
    	}
    
    }
    
    class TreeNode{
    	public int data;
    	public TreeNode left;
    	public TreeNode right;
    	public TreeNode(int data){
    		this.data = data;
    		this.left = null;
    		this.right = null;
    	}
    }

这里模拟节点五个节点的树，当每个节点都相同的时候，他们是相同的，运行程序，打印信息如下：

10 5 3 7 12 
    10 5 3 7 12 
    true

这两棵树是相等的，如果少一个节点，或者某一个节点的数据不一样，那么也会导致判断的时候返回false，即两棵树不相等。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70][]

10 5 3 7 12 
    10 5 3 8 12 
    false

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/3206e882a74849c38cfab28f608a307c.png