3

Подскажите, пожалуйста, как пройти бинарное дерево итератором? (preorder, inorder, postorder). Я создала алгоритмы для прохождения дерева в правильном порядке для preorder и postorder, но очень плохо понимаю, как можно работать с итератором на примере дерева. (я имею право занимать в памяти только константную величину, то есть нельзя использовать HashSet, ArrayList и другие структуры с динамически меняющейся длиной).

1 ответ 1

1

Сразу уточним, что в узлах дерева должны храниться ссылки на их родителей. В итераторе будем хранить только ссылку на текущий узел. Код будет на С++, но его несложно переписать на Java.

Preorder

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

void PreorderIterator::Next() {
  if (current_->GetLeft()) {
    current_ = current_->GetLeft();
    return;
  }
  if (current_->GetRight()) {
    current_ = current_->GetRight();
    return;
  }
  while (true) {
    if (!current_->GetParent()) {
      current_ = NULL;
      break;
    }
    bool came_from_left_child = current_->GetParent()->GetLeft() == current_;
    current_ = current_->GetParent();
    if (came_from_left_child && current_->GetRight()) {
      current_ = current_->GetRight();
      break;
    }
  }
}

Первым в обходе будет корень дерева.

Inorder

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

void InorderIterator::Next() {
  if (current_->GetRight()) {
    current_ = current_->GetRight();
    while (current_->GetLeft())
      current_ = current_->GetLeft();
    return;
  }
  while (true) {
    if (!current_->GetParent()) {
      current_ = NULL;
      break;
    }
    bool came_from_left_child = current_->GetParent()->GetLeft() == current_;
    current_ = current_->GetParent();
    if (came_from_left_child)
      break;
  }
}

Первым в обходе будет самый левый узел дерева.

Postorder

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

void PostorderIterator::Next() {
  if (!current_->GetParent()) {
    current_ = NULL;
    return;
  }
  bool came_from_left_child = current_->GetParent()->GetLeft() == current_;
  current_ = current_->GetParent();
  if (came_from_left_child && current_->GetRight()) {
    current_ = current_->GetRight();
    while (current_->GetLeft())
      current_ = current_->GetLeft();
  }
}

Опять же, первым в обходе будет самый левый узел дерева.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.