2015-11-18 249 views
3

我寫了一個紅黑樹實現,內置按順序遍歷(使用嵌套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的建議,該代碼被裁剪到最低限度。

+0

我不完全確定你的問題是什麼。你所做的只是陳述了一些關於你的代碼的事實/意見。你要求我們幫助你什麼? – nonsensickle

+0

我需要在命令提示符下打印圖形二叉樹的(可能是迭代的)算法。我會澄清這個問題。 –

+1

好吧,這是更清晰的,但我仍然認爲你的問題可以改善一點。特別是,大量的代碼需要大量的時間來幫助那些想要幫助的人。將這些代碼減少到最低要求將使它更有可能得到回答。請參閱[如何提問](http://stackoverflow.com/help/how-to-ask)和[MCVE](http://stackoverflow.com/help/mcve)。 PS Dobar ti je Engleski ... – nonsensickle

回答

1

使用迭代算法按順序遍歷的規範方法是維護需要打印的節點的堆棧(或LIFO隊列)。每次循環做兩件事情之一:

  1. 如果你不是在一片葉子,推動當前節點壓入堆棧並移動到最左端的孩子。

  2. 如果你在一片葉子上,打印它,從棧頂彈出頂部節點,將其打印出來,然後移動到最右邊的孩子身上。

你繼續,直到你的堆棧是空的,你在一片葉子。

格式化和節點分支圖形表示的生成顯然取決於您。請記住,它將需要一些額外的狀態變量。

編輯

我的意思「一些額外的狀態變量」是這樣的。

爲了提供漂亮的印刷,你需要不斷的三件事情軌跡:

  1. 什麼樹中的當前節點到打印上(從底部算起)的水平。這告訴你(部分)如何縮進它(或者如果你正在使用2D繪圖庫,則將它從畫布邊緣偏移)。

  2. 您當前的打印節點是左側還是右側。這會告訴你(再次)將它從其兄弟中縮進多遠,以及將它與其父代連接起來的分支的方向。

  3. 遠離節點「中心」的節點數量。這對於與其(非兄弟)鄰居的適當間隔也是有用的。

或許可以用較少的迭代到迭代狀態來做,但這對我很有用。

+0

這聽起來不像圖形打印,但只是線性?如果我錯了,請糾正我(或澄清答案)。另外,按順序迭代已經實現。我已經用指出的方法更新了這個問題。 –

+0

如果你已經完成了你的順序遍歷,那麼你的問題仍然有點混亂。當你對比「圖形」和「線性」打印時,你是什麼意思? –

+0

我不確定你是否看過輸出示例?簡單的'1 2 3 4 5'輸出就是排序數組。此外,檢查[相關問題](http://stackoverflow.com/questions/13484943/print-a-binary-tree-in-a-pretty-way),它的答案。 –