Двоичное дерево: итеративная ошибка порядка

Question

Я написал реализацию Red-Black Tree со встроенным обходным путем (с использованием вложенных class Iterator).

Я ищу (итеративный, если возможно) алгоритм, который графически печатает двоичное дерево, используя обход в порядке.

ориентации печати не имеет значения, то есть дерево в выходных данных командной строки может быть ориентирована (отформатированные), как это:

2 
/\ 
    1 4 
    /\ 
    3 5 

или как это:

|1 
| 
| 
2 
| |3 
| | 
|4 
    | 
    |5 

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

void Iteraor::first(); // Traverses to the first node. 
void Iterator::next(); // Traverses to the next node. 
void Iterator::last(); // Traverses to the last node. 

так что можно так сделать что-то вроде этого:

RBTree tree; 
/* Tree init. */ 
Iterator from(&tree), until(&tree); 
from.first(); 
until.last(); 
for (Iterator i = from; i != until; i.next()) { 
// PRINTING. 
} 

Это исходный код:

/** A program for Red-Black Tree manipulation: insertion and value retrieval. 
    * All position relations (first, last, previous, next) are in-order. 
    */ 

class RBTree { 
    struct Node { 
     enum class Colour : bool { RED, BLACK }; 
     int value; 
     Node *left, *right, *parent; 
     Colour colour; 
    public: 
     /* ... */ 
    }; 
    class Iterator { 
     class Stack { 
      /* ... */ 
     }; 
     Stack stack; 
     const RBTree* const tree; // Once set, neither the reference nor the referenced object's attributes can be modified. 
     Node* pointer; 
    public: 
     Iterator(const RBTree*); 
     void first(); 
     void next(); 
     void last(); 
     /* ... */ 
     Node* getNode() const; 
     bool operator != (const Iterator&) const; 
    }; 
    Node *root; 
    Iterator iterator; 
public: 
    RBTree() : root(nullptr), iterator(this) {} 
    /* ... */ 
    bool printTree() const; 
    ~RBTree() { deleteTree(); } 
}; 

// TREE // public: // 

/* ... */ 

bool RBTree::printTree() const { 
    if (root != nullptr) { 
     // print ?? 
     return true; 
    } 
    else 
     return false; 

} 

// NODE: Ensures the proper connection. // 

void RBTree::Node::setLeft(Node *p_left) { 
    left = p_left; 
    if (p_left != nullptr) 
     p_left->parent = this; 
} 

void RBTree::Node::setRight(Node *p_right) { 
    right = p_right; 
    if (p_right != nullptr) 
     p_right->parent = this; 
} 

// ITERATOR // 

RBTree::Iterator::Iterator(const RBTree* p_tree) : tree(p_tree), pointer(p_tree->root) {} 

// Traverses to the first node (leftmost). 
void RBTree::Iterator::first() { 
    if (pointer != nullptr) { 
     while (true) { 
      if (pointer != nullptr) { 
       stack.push(pointer); 
       pointer = pointer->left; 
      } 
      else { 
       pointer = stack.peek(); 
       break; 
      } 
     } 
    } 
} 

// Traverses to next node in-order. 
void RBTree::Iterator::next() { 
    if (pointer != nullptr) { 
     if (!stack.isEmpty()) { 
      pointer = stack.pop(); 
      if (pointer->right != nullptr) { 
       pointer = pointer->right; 
       first(); 
      } 
     } 
    } 
} 

// Traverses to the last node (rightmost). 
void RBTree::Iterator::last() { 
    pointer = tree->root; 
    if (pointer != nullptr) 
     while (pointer->right != nullptr) 
      pointer = pointer->right; 
    stack.clear(); 
} 

/* ... */ 

RBTree::Node* RBTree::Iterator::getNode() const { 
    return pointer; 
} 

bool RBTree::Iterator::operator != (const Iterator& p_iterator) const { 
    return pointer != p_iterator.pointer ? true : false; 
} 

Я изучил ответы на similar question, но ни один из алгоритмов не использует ин обход обхода (и большинство из них являются рекурсивными).

EDIT:

Folowing советы @ nonsensickle, в код обрезается до минимума.

Answer 1

Канонический метод обхода в порядке с использованием итеративного алгоритма состоит в том, чтобы поддерживать стек (или очередь LIFO) узлов, которые нужно распечатать. Каждая итерация цикла делает один из двух вещей:

1. Если вы не на листе, нажмите на текущий узел в стек и перейти на его крайнем левом ребенка.

2. Если вы на листе, распечатайте его, выньте верхний узел из стека, распечатайте его и перейдите к его самому правому ребенку.

Вы продолжаете работу до тех пор, пока ваш стек не будет пуст, а вы на листе.

Форматирование и генерация графического представления междоменных ветвей, очевидно, зависит от вас. Имейте в виду, что для этого потребуются дополнительные переменные состояния.

EDIT

Что я имею в виду "некоторые дополнительные переменные состояния" это.

Для обеспечения довольно-печати, вам нужно следить за тремя вещами:

1. Какой уровень дерева текущий узел-печать находится на (считая снизу).Это говорит вам (частично) о том, как далеко отступить от него (или смещать его с края вашего холста, если вы используете 2D-графическую библиотеку).

2. Независимо от того, является ли ваш текущий узел для печати левым или правым. Это говорит вам (еще раз), как далеко отступить от его родного брата, а также ориентация ветки, соединяющей ее с ее родителем.

3. Сколько узлов находится вдали от «центра» вашего узла. Это также будет полезно для правильного интервала между соседними соседями.

Возможно, можно обойтись без итерации итерации, но это работает для меня.