如何在C++中打印出BST

Question

我的C++程序創建了一個二叉搜索樹。我知道如何在預訂，後期和按序中打印出價值。

但是，我想做一些更難的事情。如果有人在紙上畫樹，我想打印出他們看起來的樣子。它的根部位於頂部的中間位置，它的左邊是左邊的孩子，右邊是右邊的兒童右邊。其餘的節點將相應地繪製。

我該怎麼做？

Answer 1

This article包含的代碼，你需要什麼，似乎：

alt text http://www.cpp-programming.net/wp-content/uploads/2007/12/ascii_tree.jpg

編輯：該網站已脫機

這裏的another one探索一些其他的選擇。

Answer 2

好吧，在終端很難...因爲它可能不適合。但有繪圖庫，可以爲你製作漂亮的照片。有graphvis是最受歡迎的之一。

編輯： 如果你真的只是想打印文本，graphvis有一個標記語言，用戶可以傳遞給graphvis，反過來使得漂亮的圖片。

Answer 3

一種方法是使用graphviz。具體來說，使用它的「點」程序，但輸出看起來完全如您所描述的可能是不可能的。

Answer 4

這是近似的僞代碼。基本思想是逐層走樹，將每一層中的所有節點打印在一行上。每個節點與其下面的節點相隔兩倍的空間。由於樹並非全部具有統一的深度，所以它被人爲地填充虛擬節點以佔據節點不存在的空白空間。

measure the depth of the tree, call that D 
have two queues, called Q1 and Q2 
enque the top node of the tree in Q1 
for (i = D; --i>=0;){ 
    foreach node in Q1 { 

    on first iteration of this inner loop, print 2^i - 1 spaces, 
    else print 2^(i+1) - 1 spaces. 

    if node == null print blank 
    else print node.value 

    if node.left exists enque node.left in Q2 
    else enque null in Q2 

    if node.right exists enque node.right in Q2 
    else enque null in Q2 
    } 
    copy Q2 to Q1 
    clear Q2 
    print end-of-line 
} 

每個打印的空間都是一個數字字段的寬度。假設樹具有深度d = 4。然後印刷是這樣的：

// it looks like this, and the space sequences are 
i = 3: -------n 7 
i = 2: ---n-------n 3 7 
i = 1: -n---n---n---n 1 3 3 3 
i = 0: n-n-n-n-n-n-n-n 0 1 1 1 1 1 1 1 

Answer 5

void print(node *p,int start) 
    { 
     start++; 
     if (p->right != NULL) 
     { 
      print(p->right,start); 
     } 
     for (int i = 0; i <= start; i++) 
     { 
      cout<<" "; 
     } 
     cout << p->value<<endl; 
     if (p->left != NULL) 
     { 
      print(p->left, start); 
     } 
    }