Уровень дерева обхода порядка

Question

Я пытаюсь написать метод, который будет принимать IntTree в качестве параметра и возвращать очередь со значениями IntTree в порядке уровней.Для пояснения: IntTree - это дерево с целочисленным значением в качестве его корня, а IntTree - в качестве левого и правого поддеревьев.Замечание о некоторых методах: value (t) - возвращает целочисленное значение в корне дерева left (t) - возвращает левое поддерево IntTree // right (t) - возвращает правое поддерево

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

public static QueueList levelOrder(IntTree t) {
//returns a QueueList with the values in level order

Object val;
QueueList q = new QueueList(); //temp queueList
QueueList theta = new QueueList();  //the QueueList which will eventually be printed


if (isEmpty(t)) {
  return theta;    //possible problem here
} else {

  IntTree tL = left(t);  //using for possible updating. probably won't work
  IntTree tR = right(t);

  q.enqueue(value(t)); //enqueue the root of the tree

  while (!q.isEmpty()) {
    val = q.dequeue();  //pop off the top element for printing
    theta.enqueue(val); // put the element in the queue to be printed
    if (tL != null) { 
      q.enqueue(value(tL));  //if the left isn't null, enqueue the lefts
      tL = left(tL); //this will only branch left

    }
    if (tR != null) {       //if the right isn't null, enqueue the rights
      q.enqueue(value(tR));
      tR = right(tR);  //this will only branch right
    }
  }
}
return theta; //returns a queue with values in order

}

Я написал переменные tL и tR, потому что если бы я написал что-то вроде "if(left (t)! = null) ", я бы закончил бесконечной рекурсией, поскольку 't' никогда не обновлялось.Проблема этого кода в том, что «tL» будет только ветвиться влево, а «tR» будет только ветвь вправо.Поэтому после одного уровня ниже корня некоторые значения никогда не будут сохранены.Я надеюсь, что это было ясно, и любая помощь очень ценится.Спасибо.

Answer 1

Вместо того, чтобы реализовывать границу как очередь значений, реализуйте ее как очередь IntTrees (узлов). Это значительно упростит вашу логику.

  while (!q.isEmpty()) {
    IntTree node = q.dequeue();  //pop off the top element
    theta.enqueue(value(node)); // put the element in the queue to be printed

    //enqueue the children
    IntTree left = left(node);
    if ( left != null ) {
        q.enqueue(left);
    }
    //...similar for right
  }

Если у вас есть это, вам не нужно поддерживать указатели tL и tR параллельно, что, я думаю, в любом случае является некорректным подходом.

Ссылки

• Обход в ширину (Википедия)