java – How to traverse a binary tree with an iterator?

Question:

Can you please tell me how to traverse a binary tree with an iterator? ( preorder , inorder , postorder ). I have created algorithms for traversing the tree in the correct order for preorder and postorder , but I have very little understanding of how you can work with an iterator using a tree as an example. (I have the right to occupy only a constant value in memory, that is, you cannot use HashSet , ArrayList and other structures with dynamically changing length).

Answer:

Let's clarify right away that references to their parents should be stored in the tree nodes. We will only store a link to the current node in the iterator. The code will be in C ++, but it is not difficult to rewrite it in Java.

Preorder

If the current node has a left child, then go to it. Otherwise, if there is a right child, then go to it. If there are no descendants, then we need to go up the chain of parents until we come across a node for which we have not yet visited the right child, i.e. such a node, which we will come to on the left in the process of lifting. The right child of this node will be the next to be crawled.

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;
    }
  }
}

The first to be traversed will be the root of the tree.

Inorder

If the current node has a right subtree, then the next node will be the leftmost node in that subtree. Otherwise, it is necessary to climb up the chain of parents until we meet the parent, in which we come from the left side. This parent will be the next node.

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;
  }
}

The first node in the traversal will be the left-most node of the tree.

Postorder

The simplest case. We pass to the parent. If we come from the left child and the right child exists, then we go to the leftmost node of the right subtree. Otherwise, we remain in the parent.

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();
  }
}

Again, the left-most node of the tree will be the first in the traversal.

Scroll to Top
AllEscort