java - 在两个不同的二叉搜索树之间查找具有键的公共(public)节点

Question

我目前正在尝试编写方法来检查两个不同的二叉搜索树中的所有节点，并查找两棵树之间具有公共(public)键的节点。 (即尝试从树 1 中查找包含相同键的节点和从树 2 中查找节点。如果找到公共(public)节点，该方法返回 true，否则返回 false。第二棵树存储在与树不同的对象中1、称为GraphicalObject。关键是坐标形式，大小比较是按列顺序进行的。

我编写了以下代码，但想知道它是否有什么问题或者是否有任何可以改进的地方？

1) 一种使用递归调用检查树 1 中的节点是否与树 2 中的每个节点相同的方法。 compareTo 方法在其他地方定义。

public boolean findPixel(BinaryNode node1, BinaryNode node2, GraphicalObject gobj) {
    //Creating the final coordinate key by altering the original key in nodes of tree 2.
    int xCor = node2.getData().getLocation().xCoord() + gobj.getOffset().xCoord() - graphicPos.xCoord();
    int yCor = node2.getData().getLocation().yCoord() + gobj.getOffset().yCoord() - graphicPos.yCoord();
    Location newLoc = new Location(xCor, yCor); //Creates the final key to be checked up on
    if(node1.getData().getLocation().compareTo(newLoc) == 0) { //If keys are the same
        return true;
    } else {
        if(node1.getData().getLocation().compareTo(newLoc) == -1) { //if key from node 1 is smaller than key from node 2.
            node2 = node2.getLeft();
            findPixel(node1, node2, gobj);
        } else {
            node2 = node2.getRight();
            findPixel(node1, node2, gobj);
        }
    }
    return false; 
}

2) 使用 findPixel 方法检查树 1 中的每个节点，并使用中序遍历将它们与树 2 中的每个节点进行比较。

private boolean findCommonNode(BinaryNode node1, BinaryNode node2, GraphicalObject gobj) {
    if(node1 != null) {
        findCommonNode(node1.getLeft(), node2, gobj);
        return findPixel(node1, node2, gobj);
        findCommonNode(node1.getRight(), node2, gobj);
    }
}

3) 方法，如果找到两棵树之间的公共(public)节点，则返回 true，否则返回 false。

public boolean intersects(GraphicalObject gobj){
    BinaryNode tempNode = newTree.getRoot();
    BinaryNode tempNode2 = gobj.getTree().getRoot();
    if (findCommonNode(tempNode, tempNode2, gobj) == true) {
        return true;
    } else {
        return false;
    }
}

这段代码有什么问题吗？或者我可以做些什么来让它变得更好或更有效地运行？

Answer 1

您的代码中有几处似乎错误:

在第一个方法中，您对 findPixel 进行递归调用 - 您需要返回该方法的答案。应该是这样的:

} else {
    if(node1.getData().getLocation().compareTo(newLoc) == -1) 
        return findPixel(node1, node2.getLeft(), gobj);
    else
        return findPixel(node1, node2.getRight(), gobj);
}
return false; 

在提取位置之前，您还应该为 node2 添加对 null 的检查。将其添加到 findPixel 函数的第一行:

if (node2 == null)
    return false;

在你的第二种方法中，你在函数内使用 return 语句 -> 因此你不会得到有序遍历，但它会忽略树的右侧。该代码需要如下所示:

if(node1 != null) {
    return (findCommonNode(node1.getLeft(), node2, gobj)) ||  (findPixel(node1, node2, gobj)) || (findCommonNode(node1.getRight(), node2, gobj));
}

这样可以节省一些运行时间(如果答案为真，则无需继续寻找更多相似的节点)。

最后第三个方法可以修改为(可读性):

BinaryNode tempNode = newTree.getRoot();
BinaryNode tempNode2 = gobj.getTree().getRoot();
return (findCommonNode(tempNode, tempNode2, gobj));

这适用于您给定的代码。

但是，更优化的解决方案是遍历一棵树并将该值(在哈希之后)插入到 HashMap 中 - 然后遍历第二棵树并对每个节点:检查他是否存在于 HashMap 中。与您的解决方案的复杂度为 O(n^2) 相比，这将是 O(n) 复杂度。

希望这有帮助!