假设树的节点的data类型为int型,请实现两棵树是否相等的比较?
注:A,B两棵树相等且当rootA->data==rootB->data,而且A和B的左右子树相等或者左右互换后相等。
(1)给出树节点的结构定义
(2)写出实现思路,以及复杂度估计
(3)用你习惯的语言或者伪代码实现该算法
public class Test { private static boolean flag = true; public static void main(String [] args){ //根据输入参数构建树 //comparePre(root1, root2); System.out.println(flag); } public static void comparePre(Node root1, Node root2){ if(root1.data != root2.data){ flag = false; return; } compare(root1, root2); } public static void compare(Node n1, Node n2){ if(!flag) return; if(nodeEqual(n1.left, n2.left) &&nodeEqual(n1.right, n2.right)){ if(n1.left != null) compare(n1.left, n2.left); if(n1.right != null) compare(n1.right, n2.right); } else if(nodeEqual(n1.left, n2.right) && nodeEqual(n1.right, n2.left)){ if(n1.left != null) compare(n1.left, n2.right); if(n1.right != null) compare(n1.right, n2.left); } else { flag = false; } } public static boolean nodeEqual(Node n1, Node n2){ if(n1 == n2) return true; if(n1 != null && n2 != null){ if(n1.equals(n2)){ return true; } else { return false; } } else { return false; } } } class Node{ int data; Node left; Node right; public Node(int data){ this.data = data; } @Override public boolean equals(Object node){ if(node == null) return false; Node nodeTemp = (Node) node; if(nodeTemp.data != data) return false; return true; } }
typedef struct TreeNode{
int c;
TreeNode *leftchild;
TreeNode *rightchild;
{
if(tree1 == NULL && tree2 == NULL)
return 1;
if(tree1 != NULL && tree2 != NULL)
{
if(tree1->c == tree2->c)
{
if(CompTree(tree1->leftchild, tree2->leftchild) &&
CompTree(tree1->rightchild, tree2->rightchild) ||
CompTree(tree1->rightchild, tree2->leftchild) &&
CompTree(tree1->leftchild, tree2->rightchild))
{
return 1;
}
}
}
return 0;