标题

[学习经验]C++编写算法判断两棵二叉树是否相等

责任编辑:admin
日期:2012-12-03

题目:请实现两棵树是否相等的比较,相等返回0否则返回其他值。

解析:A、B两棵树相等,当且仅当RootA->c == RootB->c,而且A的左右子树对应相等或者左右互换后相等。

思想是使用分治的方法,先判断当前节点是否相等(需要处理为空、是否都为空、是否相等),如果当前节点不相等,直接返回两棵树不相等;如果当前节点相等,那么就递归的判断他们的左右孩子是否相等。因为这里是普通的二叉树,所以A的左、右子树和B的右、左子树相等也是可以的。

C++代码:

  1. #include <iostream> 
  2. using namespace std; 
  3.  
  4. typedef struct TreeNode{ 
  5.     char c; 
  6.     struct TreeNode * left; 
  7.     struct TreeNode * right; 
  8. }; 
  9.  
  10. /*判断两棵二叉树是否相等,如果相等返回0,如果不相等则返回1*/ 
  11. int compareTree(TreeNode* tree1, TreeNode* tree2){ 
  12.     //用分治的方法做,比较当前根,然后比较左子树和右子树 
  13.     bool tree1IsNull = (tree1==NULL); 
  14.     bool tree2IsNull = (tree2==NULL); 
  15.      
  16.     if(tree1IsNull != tree2IsNull){ 
  17.         return 1; 
  18.     } 
  19.  
  20.     if(tree1IsNull && tree2IsNull){ 
  21.         //如果两个都是NULL,则相等 
  22.         return 0; 
  23.     } 
  24.     //如果根节点不相等,直接返回不相等,否则的话,看看他们孩子相等不相等 
  25.     if(tree1->c != tree2->c){ 
  26.         return 1; 
  27.     } 
  28.     return (compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2->right)) 
  29.             | 
  30.            (compareTree(tree1->left,tree2->right)&compareTree(tree1->right,tree2->left)) 
  31.         ; 

 

阅读:

相关新闻:
评论