이진 트리 검색 알고리즘 오류

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은 루트 노드에 해당하는, 그래서 그것을 부모 을 아니라고 확인해야합니다. 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 배열의 목적은

입니다 노드는 이전에 검색되지 않은 노드입니다. 다음 노드에 대한 내 요청이 하나의 개미 (이 모든 것은 게임을 프로그래밍하는 개미 AI의 것임)에서 13 번 요청한 후에 null을 반환해야하기 때문에 큰 검색을 한 번 수행 할 수 없습니다.

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); 
} 

여러 개미에 대한이 코드의 여러 사본을 해고하고 하나의 개미 터치 단일 노드가 여러 개의 스레드가 필요합니다 수 있도록하려는 경우와 공유 데이터 잠금 등의 구조를 가진 구조.

"Map"데이터 구조를 공유하여 탐색을 한 번 실행하여 빌드하는 것에 대한 참조를 얻는 것이 더 좋습니다. 결국 깊이 7의 트리는 어쨌든 128 노드 만 가지므로 많은 메모리 또는 트래버스 할 시간이 아닙니다. 필요한 경우 나중에 언제든지 개선 할 수 있지만 적어도 먼저 작동시켜야합니다.