java - 二叉树搜索算法错误

Question

我有一个需要搜索的二叉树。我不是在搜索树的一个特定节点，而是在树的每个节点上搜索以获取有关它们的信息。我现在有一个简单的递归搜索，但每次运行时都会出现堆栈溢出错误。这是一个深度为 7 的完整二叉树...

if (curDepth < 6 && !searchedNodes[curID * 2]) 
 depthSearch(curNode.getRight());
if (curDepth < 6 && !searchedNodes[curID * 2 + 1]) 
        depthSearch(curNode.getLeft());
if (curID != 1 && !searchedNodes[(int) (curID / 2)]) 
 depthSearch(curNode.getParent());

curID == 1 对应于根节点，所以我需要检查它是否是不是 parent 。 searchedNodes 的目的是确保我不搜索同一个节点两次。关于如何做到这一点有什么想法吗？

编辑:这是整个搜索方法

public void depthSearch(AntTree curNode) {
        boolean[] searchedNodes = new boolean[128];
        if (curNode == null)
            return;
        int curID = curNode.getID();
        searchedNodes[curID] = true;
        if (curNode.getFood() > 0) {
            AntScript.foodLocs[curID] = 1;
        } else {
            Ant6Script.foodLocs[curID] = 0;
        }
        Ant[] ants = curNode.getAnts();
        boolean containsWorker = false, containsSoldier = false;
        if (ants != null) {
            for (int i = 0; i < ants.length; i++) {
                if (ants[i].type().equals("Worker")
                && ants[i].teamID() != AntScript.myTeamID) {
                    containsWorker = true;
                } else if (ants[i].type().equals("Soldier")
                && ants[i].teamID() != AntScript.myTeamID) {
                    containsSoldier = true;
                } else if (ants[i].type().equals("Queen")
                && ants[i].teamID() != AntScript.myTeamID) {
                    AntScript.enemyQueenLoc = curID;
                }
            }
        }
        if (containsWorker)
            AntScript.enemyWorkerLocs[curID] = 1;
        else
            AntScript.enemyWorkerLocs[curID] = 0;
        if (containsSoldier)
            AntScript.enemySoldierLocs[curID] = 1;
        else
            AntScript.enemySoldierLocs[curID] = 0;
        AntScript.viewedNodeLocs[curID] = 1;
        int curDepth = (int) (Math.log(curID) / Math.log(2));
        if (AntScript.viewedNodeLocs[(int) (curID / 2)] == 0
        || (curDepth < 6 && AntScript.viewedNodeLocs[curID * 2 + 1] == 0)
        || (curDepth < 6 && AntScript.viewedNodeLocs[curID * 2] == 0)) {
            if (curDepth < 6
            && AntScript.viewedNodeLocs[curID * 2] == 0
            && !searchedNodes[curID * 2]) {
                depthSearch(curNode.getLeft());
            }
            if (curDepth < 6
            && AntScript.viewedNodeLocs[curID * 2 + 1] == 0
            && !searchedNodes[curID * 2 + 1]) {
                depthSearch(curNode.getRight());
            }
            if (curID != 1
            && AntScript.viewedNodeLocs[(int) (curID / 2)] == 0
            && !searchedNodes[(int) (curID / 2)]) {
                depthSearch(curNode.getParent());
            }
        } else {
            if (curDepth < 6 && !searchedNodes[curID * 2]) {
                depthSearch(curNode.getRight());
            }
            if (curDepth < 6 && !searchedNodes[curID * 2 + 1]) {
                depthSearch(curNode.getLeft());
            }
            if (curID != 1 && !searchedNodes[(int) (curID / 2)]) {
                depthSearch(curNode.getParent());
            }
        }
    }

viewedNodeLocs 数组的目的是因为板上有很多 Ant 从不同的节点执行搜索，并且搜索之前未搜索过的节点比搜索过的节点更好。我不能只进行一次大型搜索，然后就完成了，因为我对下一个节点的请求应该在来自一只 Ant 的 13 个请求之后返回 null(这整件事来 self 正在为游戏编程的 Ant 人工智能)

Answer 1

你的数据结构是最奇特的。看起来您已将树展平为节点数组。这使得你的算法真的很难理解，而且几乎肯定是一个坏主意。

话虽如此，我怀疑问题与每次递归调用深度搜索都会分配一个新的 searchedNodes 数组有关。就像我说的，你的算法......很难理解。

我建议您以传统方式表示二叉树，每个节点都有一个“左”和“右”指针。然后按照维基百科文章描述的方式实现遍历。更好的是，看一下 Java Collections 框架，看看现有的 List/Set/Map 实现之一是否可以实现您想要做的事情。