搜索一棵二叉树是否是另一棵二叉树的子树

Question

我有一个很严重的问题，就是在一棵树中重复搜索子树。

我试过了，但是。。。

public static boolean containsTree (Node t1, Node t2)
{
    if (t2 == null)
        return true;
    // Empty tree is always a subtree.
    else
        return subTree(t1, t2);
}

public static boolean subTree (Node t1, Node t2)
{
    if (t1 == null)
        return false; // Big tree is over.
    if (t1.getName().equalsIgnoreCase(t2.getName()))
        return matchTree(t1, t2);
    return (subTree(t1.getChild(), t2) || subTree(t1.getBrother(), t2));
}

private static boolean matchTree (Node t1, Node t2)
{
    if (t1 == null && t2 == null)
        return true; // Both trees are empty.
    if (t1 == null || t2 == null)
        return false; // Big tree empty and subtree still not found.
    if (!t1.getName().equalsIgnoreCase(t2.getName()))
        return false;
    return (matchTree(t1.getChild(), t2.getChild()) && matchTree(
            t1.getBrother(), t2.getBrother()));
}

似乎没有正确的形式。containsTree函数在找到与另一个节点不同的节点时停止搜索。

下面是两棵树的例子。

          1                 
         / \                                    3
        /   \                                   /\
       /     \                                 /  \
      2      3                                7    8
      /\     /\
     /  \   /  \
     3   4 5    6
                 \
                  3
                  /\
                 /  \
                 7   8

在这种情况下，当函数比较右边的子树和左边的子树时，当find等于父节点但它有不同的子节点时，它会停止搜索。我需要函数不要停止搜索，而是抛出这一点，搜索所有其他子节点及其子树。

Answer 1

假设我们班是这样的：

class Node{
    node left, right;
    int value;    

    boolean equals(Node n){
        // if one child is null we can skip
        if(this.left == null && this.left != null ||
           this.left != null && this.left == null ){
            return false;
        }
        if(this.right == null && this.right != null ||
           this.right != null && this.right == null ){
            return false;
        }
        // 
        return (this.value == n.value) && 
               ( this.left == null || (this.left.equals(n.left)) ) && 
// if this.left == null, n.left is null too and the || will skip the equals()
               ( this.right == null || (this.right.equals(n.right)) );
// same for right
    }
}

此方法将递归检查一棵树是否与另一棵树相同，因此，让我们检查它是否是子树：

boolean isSubTree(Node other){
    return this.equals(other) || 
         (other.left != null && this.isSubTree(other.left)) || 
// if left is null, this cant be a subtree 
         (other.right != null && this.isSubTree(other.right));
// same for right
}

没有测试，但我认为它可以这样工作。我跳过了构造函数和其他函数。

（位重载返回语句： P）

你应该记住一些事情：树通常用于搜索值，并且大部分被实现为二叉树：led-child

显然，你应该确保你的树不绕圈子