打印二叉树 - 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是不够的。

注：我没有足够的时间来调试代码，并使其完美的，但我希望它会帮助你找到自己的解决方案。