Блог

Главная - Вопросы по программированию - преобразование двоичного дерева в список<Список>

преобразование двоичного дерева в список<Список>

#java #algorithm #tree

#java #алгоритм #дерево

Вопрос:

Верен ли мой алгоритм?

 List<List<Node> > ol = new ArrayList<List<Node>>();
build(root,0)

void build (Node node,int level)
{ 
 if(node==null)
    return;
  List<Node> il;
  if(ol.size() < level){
   il =  new ArrayList<Node>(); 
  }else{
  il= ol.get(level);
  }

il.add(node);
ol.put(level,il);
 build(node.left, level 1);
 build(node.right,level 1);
}

Комментарии:

1. В общем, если вы хотите узнать, верен ли какой-то написанный вами код, напишите тест!!

Ответ №1:

Предполагая, что вам нужен список узлов для каждого уровня, это кажется правильным, за исключением:

  1. ol.put(level,il); У List нет метода put (в этом случае это было бы set ).
  2. Я бы опустил строку выше и добавил ol.add(il) после создания нового списка массивов для уровня.
  3. Я бы также передал внешний список в качестве параметра метода вместо использования переменной-члена (хотя это скорее проблема дизайна)
  4. ; Отсутствует после build(root, 0)

Редактировать: для уточнения № 2:

 if(ol.size() < level) {
  il = new ArrayList<Node>();
  ol.add(il); //add here only, assuming level = ol.size()   1 always is true in this case
}

Комментарии:

1. Нет, при условии, что level = size 1, add(il) было бы достаточно. add(index, il) сместило бы записи вправо (что нарушило бы порядок) и не сработало бы для индекса > size.

2. Нет необходимости править shiff. Нам нужно добавить элемент в список i

3. @dojo Именно поэтому вам не следует использовать add(index, il) , или лучше add(size(),il) то же самое, что add(il) if index == size() (это единственный способ, который не нарушит вашу логику) . 🙂

4. add(il) добавит элемент в конец, мы должны заменить запись (список) в индексе i и не добавлять конец внешнего списка.

5. @dojo 1. Для замены вам понадобится set(...) . 2. Это работает, только если элемент уже инициализирован. Если индекс равен >= size, это не сработает. Из JavaDoc на set() : IndexOutOfBoundsException - if the specified index is out of range (index < 0 || index >= size()).