打印二叉樹 - C++

Question

我想只是一個行打印二叉樹更可讀的方式，而不是。我以前的答案this question作爲開始，而是從左至右像這樣的打印數據：

25 
    15 
     10 
     20 
    30 
     35 

我需要它看起來像這樣：

 25 
    15  30 
10 20  35 

這是代碼，我有：

void printTree(AVLNode* root, int indent) 
{ 
    if (root != nullptr) { 
     if (indent) { 
      cout << setw(indent) << ' '; 
     } 
     cout << root->data << endl; 
     if (root->left) printTree(root->left, indent + 4); 
     if (root->right) printTree(root->right, indent + 4); 
    } 
} 

任何想法如何讓它打印我想要的方式？

Answer 1

考慮下面的例子

#include <iostream> 
#include <string> 
#include <iomanip> 
using namespace std; 

// .... your code .... 

void buildTree(AVLNode* root, int scrWidth, int itemWidth) 
// breadth-first traversal with depth limit based on screen width and output field width for one elemet 
{ 
    bool notFinished = false; 
    // check the root 
    if (root) 
    { 
     notFinished = true; 
    } 
    // calculate maximum possible depth 
    int depth = 1; 
    int field = scrWidth; 
    while (field > itemWidth) 
    { 
     depth++; 
     field /= 2; 
    } 
    // check result 
    if (depth < 1) 
    { 
     cout << " -= erroneous output options =-" << endl; 
     return; 
    } 
    AVLNode** pItems = new AVLNode*[1]; 
    *pItems = root; // pointer to item on the first level 
    int itemCnt = 1; 
    int divWidth = 1; 
    // loop for output not more than depth levels until the data is not finished 
    // where level is current depth of tree, and root is on the first level 
    for (int level = 1; level <= depth && notFinished; level++) 
    { 
     itemCnt = (level == 1) ? 1 : (itemCnt * 2); 
     divWidth *= 2; 
     // make list of pointers to refer items on next level 
     AVLNode** list = new AVLNode*[itemCnt * 2]; 
     // output all utems of that level 
     int nextCnt = 0; 
     notFinished = false; 
     for (int i = 0; i < itemCnt; i++, nextCnt += 2) 
     { 
      int curWidth = (scrWidth/divWidth) * ((i > 0) ? 2 : 1); 
      cout << setw((curWidth>=itemWidth) ? curWidth:(itemWidth/(1+(i==0)))); 
      if (pItems[i]) 
      { 
       cout << pItems[i]->data; 
       list[nextCnt] = pItems[i]->left; 
       list[nextCnt + 1] = pItems[i]->right; 
       if (list[nextCnt] || list[nextCnt + 1]) 
        notFinished = true; 
      } 
      else 
      { 
       cout << "."; 
       list[nextCnt] = NULL; 
       list[nextCnt + 1] = NULL; 
      } 
     } 
     cout << endl; 
     // free the memory allocated for list of pointers 
     if (pItems) 
      delete[] pItems; 
     pItems = list; // and shift to new one (for next level) 
    } 
    delete[] pItems; 
} 

int main(int argc, char* argv[]) 
{ 
    // create some structure 
    AVLNode * root = NULL; 
    // code for making tree 
    // .... 
    buildTree(root, 80, 5); 
    // some other code 
    // .... 
    return 0; 
} 

呼叫buildTree(root, 80, 5);打印樹等（其中.裝置NULL代替項）：

         64 
        58          . 
     24     62     .     . 
    0  78   .   .   .   .   .   . 
41 69 . . . . . . . . . . . . . . 

但buildTree(root, 40, 10);對於相同的數據將輸出

   64 
    58     . 
24  62   .   . 

即只有三層，因爲4級有8個項目，如果每個要求10個字符總重量40是不夠的。

注：我沒有足夠的時間來調試代碼，並使其完美的，但我希望它會幫助你找到自己的解決方案。