Ошибки алгоритма поиска двоичного дерева - PullRequest
Новая
       11

Ошибки алгоритма поиска двоичного дерева

0 голосов
/ 05 декабря 2009

У меня есть двоичное дерево, которое мне нужно найти. Я не ищу один конкретный узел дерева, а скорее по каждому узлу дерева, чтобы получить информацию о них. Прямо сейчас у меня есть простой рекурсивный поиск, но каждый раз, когда он запускается, я получаю ошибку переполнения стека. Это полное двоичное дерево глубиной 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 соответствует корневому узлу, поэтому мне нужно убедиться, что он не родитель. В поиске узлов нужно убедиться, что я не ищу один и тот же узел дважды. Есть идеи, как это сделать?

edit: вот весь метод поиска

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

Назначение массива visibleNodeLocs состоит в том, что у меня на доске много муравьев, выполняющих поиск по разным узлам, и лучше искать через узел, который не был найден ранее, чем тот, который был ранее. Я не могу просто выполнить один большой поиск, а затем выполнить, потому что мои запросы на следующие узлы должны возвращать ноль после 13 запросов от одного муравья (все это от муравьиного AI, который я программирую для игры)

Ответы [ 3 ]

2 голосов
/ 05 декабря 2009

Ваша структура данных наиболее своеобразна. Похоже, вы сплющили дерево в массив узлов. Это делает ваш алгоритм действительно сложным для понимания и почти наверняка плохой идеей.

Сказав это, я подозреваю, что проблема связана с тем фактом, что при каждом рекурсивном вызове deepSearch выделяется новый массив искомых узлов. Как я уже сказал, ваш алгоритм ... сложен для понимания.

Я предлагаю вам представить ваше бинарное дерево обычным способом, причем каждый узел имеет указатель «влево» и «вправо». Затем осуществите обход, как описано в статье в Википедии. Более того, взгляните на инфраструктуру Java Collections и посмотрите, выполняет ли одна из существующих реализаций List / Set / Map то, что вы пытаетесь сделать.

0 голосов
/ 05 декабря 2009

Вам нужен обход, а не поиск.

например, некоторый код псевдо 

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 узлов, поэтому для его обхода не требуется много памяти или времени. Вы всегда можете улучшить его позже, если нужно, но, по крайней мере, сначала запустите его.

0 голосов
/ 05 декабря 2009

Вы можете использовать технику обхода дерева, чтобы получить информацию обо всех узлах. Проверьте здесь http://en.wikipedia.org/wiki/Pre-order_traversal.

...