如何垂直打印二叉樹搜索類？

我一直在學習如何在C++中使用鏈表來編程二叉樹搜索。一切正常，我知道二叉樹是如何工作的，但是我希望能夠在頂部的頭部和所有節點打印樹下面的波紋管，因爲我試圖證明這裏：如何垂直打印二叉樹搜索類？

         [root or head] 
          [left]     [right] 

         [left]  [right]  [left]  [right]

我使用控制檯打印樹，因此可以隨意使用'cout'或'printf'。我相信我需要設置控制檯的寬度，但我不知道如何啓動。

感謝，Y_Y

來源

2010-10-10 Y_Y

Y：抽象類標籤與你的問題有什麼關係？ :) – 2010-10-10 08:51:35

如果您想以這種對稱方式進行操作，您需要知道在advance_中打印_index所需的數據的深度和長度，以便正確對齊父節點。使用左對齊輸出可能會更容易。 – sbi 2010-10-10 08:52:09

由於SBI提到，使得左對齊版本比中心對齊一個更容易。但是，選擇基本算法的方法應該是：

橫向樹寬度優先。通過使用隊列以下算法，這樣做：

聲明一個隊列
根節點添加到隊列
雖然隊列包含多個節點，做4 - 6：
出隊節點
打印節點。在每次打印比第2次冪次（從1開始）小1之後，也打印換行符。
排隊節點的孩子

（見http://www.cs.bu.edu/teaching/c/tree/breadth-first/）

爲了打印中心對齊的樹，也請執行下列操作（如果樹是完整的纔有效。如果它不完整，做最簡單的辦法就是讓一個完整的副本，每一個應該有一個節點處獲得某種空節點的）：

除了打印到屏幕上，「打印」每一行到字符串字符串數組。
隨着時間的推移，記錄您打印的最長元素的字符長度。我們稱之爲maxElemLen 。
無論何時打印元素，在它之前打印一個製表符，並在其後面打印一個製表符。
最後回去，並在陣列中的每一行，用2 ^（nLines - lineNum）製表符替換的每個製表符。
然後展開每個選項卡或換行符來 maxElemLen + 1個空間後自帶選項卡，擴大別的後到來每個標籤（即，印刷ELEM後）至（maxElemLen + 1 - （所述自最後一個標籤以來經過的字符數））空格。
最後，按順序打印您的數組的每一行。

來源

2010-10-10 09:16:54 AlcubierreDrive

請注意，「在每次打印之後，第二次打印的第二次（從0開始）之後，還會打印換行符。」只有在樹完整時纔是正確的。如果沒有完成，你需要一種不同的方式來跟蹤你什麼時候完成一個關卡。 – AlcubierreDrive 2010-10-10 09:21:13

@Jon：我猜這個問題的重要部分是什麼？ – 2010-10-10 09:23:43

@阿門：這不是在第一句話中處理的。 – sbi 2010-10-10 09:26:18

這是打印二叉樹的代碼 - 下面代碼打印二叉樹從左至右時尚

private void printTree(Node nNode,int pos){ 
    if (nNode==null) { 
     for(int i=0;i<pos;i++) System.out.print("\t"); 
     System.out.println("*"); 
     return; 
    } 
    printTree(nNode.right,pos+1); 
    for(int i=0;i<pos;i++) System.out.print("\t"); 
    System.out.println(nNode.data); 
    printTree(nNode.left,pos+1); 
}

下面是上述方法的輸出

enter image description here

「* '在上面的輸出中表示空

來源

2013-10-13 07:05:29 IsAs

因此，我們傾斜頭部以獲得預期的輸出？ – Thomas 2013-10-13 07:07:32

是的，很容易看到小樹。 – IsAs 2013-10-13 07:36:44

非常好的解決方案！ – BajaBob 2014-03-20 22:10:04

@ IsAs的解決方案。 C++ 90度CCW旋轉樹。我建議將它用於不大於2^4的樹上。

print(root); 
void BinarySearchTree::print(BinaryNode* n, int pos = 0){ 
    if (n==NULL) { 
     for(int i = 0; i < pos; ++i) 
      cout << "\t"; 
     cout << 'X' << endl; 
     return; 
    } 
    print(n->right,pos+1); 
    for(int i = 0; i < pos; i++) 
     cout << "\t"; 
    cout << n->key << endl; 
    print(n->left,pos+1); 
}

來源

2014-03-20 22:13:20 BajaBob

如何垂直打印二叉樹搜索類？

回答

相關問題