Обход дерева порядка уровней для общего дерева с отображением уровня дерева за уровнем

нужно только отслеживать текущий уровень и следующий уровень.

static void displayBFS(NaryTreeNode root) {
    int curlevel = 1;
    int nextlevel = 0;

    LinkedList<NaryTreeNode> queue = new LinkedList<NaryTreeNode>();
    queue.add(root);

    while(!queue.isEmpty()) { 
        NaryTreeNode node = queue.remove(0);

        if (curlevel == 0) {
            System.out.println();
            curlevel = nextlevel;
            nextlevel = 0;
        }

        for(NaryTreeNode n : node.nary_list) {
            queue.addLast(n);
            nextlevel++;
        }

        curlevel--;
        System.out.print(node.data + " ");
    } 
}

когда вы переключаете уровни, замените следующий уровень на текущий уровень и сбросьте следующий уровень. я предпочитаю простоту этого, а не создание отдельной очереди.

У меня был этот вопрос для интервью Microsoft на прошлой неделе... по телефону мне не очень понравилось. молодец, что изучил.

Самое простое решение этой проблемы, которое я знаю, — использовать дозорный. Очередь инициализируется корневым узлом, за которым следует дозорный, а затем вы выполняете цикл по очереди:

1. снять передний элемент
2. if it is the sentinel:
   • we're at the end of a level, so we can end the output line
   • если очередь не пуста, поместите часовой обратно в очередь в конце.
3. if it is not the sentinel:
   • print it out
   • поместите все его дочерние элементы в очередь.

Я не занимаюсь Java, но у меня есть код C++ для BFS с поддержкой глубины, который я урезал, чтобы выполнить эту задачу печати:

void show_tree_by_levels(std::ostream& os, Node* tree) {
  Node* sentinel = new Node;
  std::deque<Node*> queue{tree, sentinel};
  while (true) {
    Node* here = queue.front();
    queue.pop_front();
    if (here == sentinel) {
      os << std::endl;
      if (queue.empty())
        break;
      else
        queue.push_back(sentinel);
    } else {
      for (Node* child = here->child; child; child = child->sibling)
        queue.push_back(child);
      os << here->value << ' ';
    }
  }
}

Обратите внимание, что я предпочитаю использовать решение с двумя указателями (first_child/next_sibling), поскольку оно обычно оказывается проще, чем встроенные списки. YMMV.

Используйте другую очередь, чтобы указать глубину. Приведенный ниже код не тестировался, но он должен дать вам представление (переменная sep введена, чтобы избежать пробелов в конце):

void displayBFS(NaryTreeNode n) {
  Queue<NaryTreeNode> q  = new LinkedList<NaryTreeNode>();
  Queue<Integer> depth  = new LinkedList<Integer>();
  q.add(n);
  depth.add(0);

  String sep = "";
  int oldDepth = 0

  while(!q.isEmpty()) {
    NaryTreeNode currN = q.poll();
    int currDepth = depth.poll();
    if (currDepth > oldDepth) {
      System.out.println();
      oldDepth = currDepth;
      sep = "";
    }
    System.out.print(sep + currN.data);
    sep = " ";

    for(NaryTreeNode x : currN.nary_list) {
      q.add(x);
      depth.add(currDepth + 1);
    }
  }
}

На мой вкус, этот подход более понятен по сравнению с другими способами, которыми можно было бы это сделать.

Думаю, нам нужны еще три переменные. numInCurrentLevel для отслеживания количества элементов на текущем уровне, indexInCurrentLevel для подсчета при обходе на текущем уровне и numInNextLevel для отслеживания количество элементов следующего уровня. Код ниже:

static void displayBFS(NaryTreeNode root) {

    Queue<NaryTreeNode> q  = new LinkedList<NaryTreeNode>();;
    q.add(root);
    int numInCurrentLevel = 1;
    int numInNextLevel = 0;
    int indexInCurrentLevel=0;

    while(!q.isEmpty()) { 
        NaryTreeNode node = q.poll();
        System.out.print(node.data + " ");
        indexInCurrentLevel++;

        for(NaryTreeNode n : node.nary_list) {
            q.add(n);
            numInNextLevel++;
        }

        //finish traversal in current level
        if(indexInCurrentLevel==numInCurrentLevel) {
            System.out.println();
            numInCurrentLevel=numInNextLevel;
            numInNextLevel=0;           
            indexInCurrentLevel=0;
        }
  } 
}

Надеюсь, это поможет, я не так хорошо знаком с программированием на Java.