二叉树：迭代序列打印

Question

我写了一个红黑树实现，内置按顺序遍历（使用嵌套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的答复，但没有的算法，利用在遍历（并且大多数是递归的）。

编辑：

如下因素@ nonsensickle的建议，该代码被裁剪到最低限度。

Answer 1

使用迭代算法按顺序遍历的规范方法是维护需要打印的节点的堆栈（或LIFO队列）。每次循环做两件事情之一：

1. 如果你不是在一片叶子，推动当前节点压入堆栈并移动到最左端的孩子。

2. 如果你在一片叶子上，打印它，从栈顶弹出顶部节点，将其打印出来，然后移动到最右边的孩子身上。

你继续，直到你的堆栈是空的，你在一片叶子。

格式化和节点分支图形表示的生成显然取决于您。请记住，它将需要一些额外的状态变量。

编辑

我的意思“一些额外的状态变量”是这样的。

为了提供漂亮的印刷，你需要不断的三件事情轨迹：

1. 什么树中的当前节点到打印上（从底部算起）的水平。这告诉你（部分）如何缩进它（或者如果你正在使用2D绘图库，则将它从画布边缘偏移）。

2. 您当前的打印节点是左侧还是右侧。这会告诉你（再次）将它从其兄弟中缩进多远，以及将它与其父代连接起来的分支的方向。

3. 远离节点“中心”的节点数量。这对于与其（非兄弟）邻居的适当间隔也是有用的。

或许可以用较少的迭代到迭代状态来做，但这对我很有用。