二叉树搜索算法错误

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对应根结点，所以我需要检查它的 不是父。搜索节点的事情是确保我不搜索相同的节点两次搜索 。任何想法如何做到这一点？

编辑：这里是整个搜索方法

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阵列的目的，是因为我有在执行从不同节点搜索的主板很多蚂蚁，它通过一个是更好地搜索之前没有被搜索过的节点。我不能只做一个大搜索，然后做，因为我的下一个节点的请求应该从一个蚂蚁的13个请求后返回null（这整个事情是从一个蚂蚁AI我正在编程的游戏）

Answer 1

你的数据结构是最奇特的。它看起来像你已经把树变成了一个节点数组。它使你的算法真的很难理解，几乎肯定是一个坏主意。

话虽如此，我怀疑这个问题与每个递归调用depthSearch分配一个新的searchedNodes数组有关。就像我说的，你的算法很难理解。

我建议你用常规方式表示你的二叉树，每个节点有一个'左'和'右'指针。然后按维基百科文章中描述的方式实现遍历。更好的是，看一看Java Collections框架，看看现有的List/Set/Map实现是否能完成你想要做的事情。

Answer 2

您可以使用树遍历技术来获取有关所有节点的信息。点击这里查看 http://en.wikipedia.org/wiki/Pre-order_traversal。

Answer 3

您需要遍历，而不是搜索。

例如，一些伪代码

void PrintTree(TreeNode node){ 
    if(node == null) return; 
    if(node.Left != null) PrintTree(node.Left); 
    if(node.Right != null) PrintTree(node.Right); 
    Console.Printline(node.Value); 
} 

如果要火了此代码为多个蚂蚁的多个副本，让只有一只蚂蚁触摸任何一个节点，你需要多线程和共享数据结构与锁定等。

现在更好地分享一个“地图”数据结构，每个数据结构通过执行一次遍历获得一个引用。毕竟深度7的树只有128个节点，所以它没有太多内存或时间来遍历。如果需要，您可以随时改进，但至少可以先让它工作。