печать дерева с использованием BFS. требуется быстрое исправление - PullRequest
Новая
       26

печать дерева с использованием BFS. требуется быстрое исправление

0 голосов
/ 21 ноября 2011

Итак, я печатаю b-дерево по уровням.Узел имеет не более 3 ключей и не более 4 дочерних элементов, это ваше типичное дерево 2-3-4.Код работает нормально для большинства вещей, за исключением случаев, когда я добавляю «2 5 8 1 3 6 9 7 11 12 10 4».В частности, проблема заключается в том, что push (2 5) и (11) в моей очереди подсчитывают (2 5) детей.После этого я иду, чтобы вытолкнуть его детей, но (11) мешает и облажается.

void BFS(TwoThreeFourTree tree, Node start)
{
    ArrayList<String> level = new ArrayList<String>();
    int levCount = 0;

    LinkedList<Node> queue = new LinkedList<Node>();
    queue.add(start);
    level.add("(" + keys(start) + ")");
    while (!queue.isEmpty())
    {
        Node vertix = queue.remove();
        for (Node child : vertix.child)
        {
            if (child == null) break;
            queue.add(child);
            levCount++;
        }

        String allChild = "";
        Node temp[] = new Node[levCount];
        while (levCount > 0)
        {
            temp[levCount - 1] = queue.remove();
            allChild = allChild.concat("(" + keys(temp[levCount - 1]) + ")");
            levCount--;
        }
        for (Node child : temp)
            queue.addFirst(child);
        if (levCount == 0 && allChild != "")
            level.add(allChild);
    }
    for (String stuff : level)
    {
        System.out.println(stuff);
    }
    System.out.println("----------------------");
}

1 Ответ

0 голосов
/ 21 ноября 2011

Да, проблема в том, что ваш алгоритм неверен. Когда вы запускаете итерацию цикла, и ваша очередь не пуста, вы добавляете узлы 'levCount' в конец очереди, но затем вы извлекаете узлы 'levCount' с самого начала (queue.remove ()), и они имеют ничего общего с узлами, которые вы добавили в конец. Это не обычный / подлинный поиск BFS, а ошибочная версия. Обычный поиск BFS следует этому псевдокоду: 

while (queue is not empty)
   node = remove first from queue
   <process / print node>
   for each child of node
      push child to queue

Если вы хотите обработать каждый уровень в режиме BFS, вам нужен другой алгоритм.

...