1

如果我有两棵二叉树，我将如何检查所有节点中的元素是否相等。

关于如何解决这个问题的任何想法？

4

9 回答 9

7

您将进行并行树遍历 - 选择您的订单（预购、后购、有序）。如果在任何时候存储在当前节点中的值不同，那么两棵树也是如此。如果一个左节点为空而另一个不是，则树是不同的；同样适用于正确的节点。

于 2009-06-15T02:02:35.953 回答
2

Does node order matters? I'm assuming for this answer that the two following trees :

  1       1
 / \     / \
3   2   2   3

are not equal, because node position and order is taken into account for the comparison.

A few hints

  • Do you agree that two empty trees are equal?
  • Do you agree that two trees that only have a root node, with identical node values, are equal?
  • Can't you generalize this approach?

Being a bit more precise

Consider this generic tree:

       rootnode(value=V)
           /      \
          /        \
      --------    ------- 
     |  left  |  | right |
     | subtree|  |subtree|
      --------    -------

rootnode is a single node. The two children are more generic, and represent binary trees. The children can either be empty, or a single node, or a fully-grown binary tree.

Do you agree that this representation is generic enough to represent any kind of non-empty binary tree? Are you able to decompose, say, this simple tree into my representation?

If you understand this concept, then this decomposition can help you to solve the problem. If you do understand the concept, but can't go any further with the algorithm, please comment here and I'll be a bit more specific :)

于 2009-06-15T02:29:21.833 回答
1

您可以使用Tree Traversal 之类的东西来检查每个值。

于 2009-06-15T02:03:08.603 回答
0

您可以使用指针和递归来检查节点是否相等，然后检查子树。代码可以用Java语言编写如下。

public boolean sameTree(Node root1, Node root2){
//base case :both are empty
if(root1==null && root2==null )
   return true;

if(root1.equals(root2)) {
    //subtrees
    boolean left=sameTree(root1.left,root2.left);
    boolean right=sameTree(root1.right,root2.right);
    return (left && right);
}//end if
else{
    return false;
}//end else

}//结束sameTree()

于 2013-09-07T06:54:49.000 回答
0

如果树是二叉搜索树，那么前序遍历将产生可靠的、可重复的项目排序，则现有答案将起作用。如果它们是任意二叉树，那么您将遇到一个更有趣的问题，并且应该查看哈希表。

于 2009-06-15T02:05:59.907 回答
0

编写 C 代码作为问题中提到的标签。

int is_same(node* T1,node* T2)
{
    if(!T1 && !T2)
    return 1;
    if(!T1 || !T2)
    return 0;

    if(T1->data == T2->data)
    {
        int left = is_same(T1->left,T2->left);
        int right = is_same(T1->right,T2->right);
        return (left && right);
    }
    else
    return 0;
}

兼顾结构和价值观。

于 2013-09-07T07:06:46.127 回答
0

一行代码足以检查两个二叉树节点是否相等（相同的值和相同的结构）。

bool isEqual(BinaryTreeNode *a, BinaryTreeNode *b)  
{  
    return (a && b) ?  (a->m_nValue==b->m_nValue && isEqual(a->m_pLeft,b->m_pLeft) && isEqual(a->m_pRight,b->m_pRight)) :  (a == b);  
}
于 2013-12-17T13:58:36.077 回答
0

我的解决方案是将两棵树展平为 2 个数组（使用级别顺序），然​​后遍历每个项目并进行比较。您知道两个数组的顺序相同。您可以进行简单的预检查，例如如果数组大小不同，那么两棵树就不一样。

级别顺序相当容易实现，关于树遍历的 Wikipedia 文章基本上为您提供了所需的一切，包括代码。如果问题中要求效率，那么最好使用非递归解决方案，并使用 FIFO 列表（C# 用语中的队列 - 我不是 C 程序员）来完成。

于 2009-06-15T14:56:34.417 回答
0

让两棵树通过相同的树遍历逻辑并匹配输出。如果即使单个节点数据不匹配，树也不匹配。

或者您可以创建一个简单的树遍历逻辑并在每次递归时比较节点值。

于 2012-08-16T19:11:45.283 回答