C++ 以漂亮的方式打印二叉树

Print a binary tree in a pretty way

提问by user1840555

Just wondering if I can get some tips on printing a pretty binary tree in the form of:

只是想知道我是否可以获得一些有关以以下形式打印漂亮二叉树的提示：

5
     10
          11
          7
               6
     3
          4
          2

Right now what it prints is:

现在它打印的是：

   2
    4
    3 
    6
    7
    11
    10
    5

I know that my example is upside down from what I'm currently printing, which it doesn't matter if I print from the root down as it currently prints. Any tips are very appreciated towards my full question:

我知道我的示例与我当前正在打印的内容是颠倒的，如果我从当前打印的根部向下打印并不重要。对于我的完整问题，任何提示都非常感谢：

How do I modify my prints to make the tree look like a tree?

如何修改我的印刷品以使这棵树看起来像一棵树？

    //Binary Search Tree Program

#include <iostream>
#include <cstdlib>
#include <queue>
using namespace std;

int i = 0;

class BinarySearchTree
{
   private:
   struct tree_node
   {
      tree_node* left;
      tree_node* right;
      int data;
   };
   tree_node* root;

   public:
   BinarySearchTree()
   {
      root = NULL;
   }

   bool isEmpty() const { return root==NULL; }
   void print_inorder();
   void inorder(tree_node*);
   void print_preorder();
   void preorder(tree_node*);
   void print_postorder();
   void postorder(tree_node*);
   void insert(int);
   void remove(int);
};

// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)
{
   tree_node* t = new tree_node;
   tree_node* parent;
   t->data = d;
   t->left = NULL;
   t->right = NULL;
   parent = NULL;

   // is this a new tree?
   if(isEmpty()) root = t;
   else
   {
      //Note: ALL insertions are as leaf nodes
      tree_node* curr;
      curr = root;
      // Find the Node's parent
      while(curr)
      {
         parent = curr;
         if(t->data > curr->data) curr = curr->right;
         else curr = curr->left;
      }

      if(t->data < parent->data)
      {
         parent->left = t;
      }
      else
      {
      parent->right = t;
      }
    }
}

void BinarySearchTree::remove(int d)
{
   //Locate the element
   bool found = false;
   if(isEmpty())
   {
      cout<<" This Tree is empty! "<<endl;
      return;
   }

   tree_node* curr;
   tree_node* parent;
   curr = root;

   while(curr != NULL)
   {
      if(curr->data == d)
      {
         found = true;
         break;
      }
      else
      {
         parent = curr;
         if(d>curr->data) curr = curr->right;
         else curr = curr->left;
      }
    }
    if(!found)
    {
      cout<<" Data not found! "<<endl;
      return;
    }


    // 3 cases :
    // 1. We're removing a leaf node
    // 2. We're removing a node with a single child
    // 3. we're removing a node with 2 children

    // Node with single child
    if((curr->left == NULL && curr->right != NULL) || (curr->left != NULL && curr->right == NULL))
    {
      if(curr->left == NULL && curr->right != NULL)
      {
         if(parent->left == curr)
         {
            parent->left = curr->right;
            delete curr;
         }
         else
         {
            parent->right = curr->left;
            delete curr;
         }
       }
       return;
    }

    //We're looking at a leaf node
    if( curr->left == NULL && curr->right == NULL)
    {
      if(parent->left == curr)
      {
         parent->left = NULL;
      }
      else
      {
         parent->right = NULL;
      }
      delete curr;
      return;
    }


    //Node with 2 children
    // replace node with smallest value in right subtree
    if (curr->left != NULL && curr->right != NULL)
    {
       tree_node* chkr;
       chkr = curr->right;
       if((chkr->left == NULL) && (chkr->right == NULL))
       {
         curr = chkr;
         delete chkr;
         curr->right = NULL;
       }
       else // right child has children
       {
         //if the node's right child has a left child
         // Move all the way down left to locate smallest element

         if((curr->right)->left != NULL)
         {
            tree_node* lcurr;
            tree_node* lcurrp;
            lcurrp = curr->right;
            lcurr = (curr->right)->left;
            while(lcurr->left != NULL)
            {
               lcurrp = lcurr;
               lcurr = lcurr->left;
            }
            curr->data = lcurr->data;
            delete lcurr;
            lcurrp->left = NULL;
         }
         else
         {
            tree_node* tmp;
            tmp = curr->right;
            curr->data = tmp->data;
            curr->right = tmp->right;
            delete tmp;
         }

      }
      return;
   }

}
void BinarySearchTree::print_postorder()
{
   postorder(root);
}

void BinarySearchTree::postorder(tree_node* p)
{
   if(p != NULL)
   {
      if(p->left) postorder(p->left);
      if(p->right) postorder(p->right);
      cout<<"     "<<p->data<<"\n ";
   }
   else return;
}

int main()
{
    BinarySearchTree b;
    int ch,tmp,tmp1;
    while(1)
    {
       cout<<endl<<endl;
       cout<<" Binary Search Tree Operations "<<endl;
       cout<<" ----------------------------- "<<endl;
       cout<<" 1. Insertion/Creation "<<endl;
       cout<<" 2. Printing "<<endl;
       cout<<" 3. Removal "<<endl;
       cout<<" 4. Exit "<<endl;
       cout<<" Enter your choice : ";
       cin>>ch;
       switch(ch)
       {
           case 1 : cout<<" Enter Number to be inserted : ";
                    cin>>tmp;
                    b.insert(tmp);
                    i++;
                    break;
           case 2 : cout<<endl;
                    cout<<" Printing "<<endl;
                    cout<<" --------------------"<<endl;
                    b.print_postorder();
                    break;
           case 3 : cout<<" Enter data to be deleted : ";
                    cin>>tmp1;
                    b.remove(tmp1);
                    break;
           case 4:
                    return 0;

       }
    }
}

采纳答案by dasblinkenlight

In order to pretty-print a tree recursively, you need to pass two arguments to your printing function:

为了递归地漂亮打印树，您需要将两个参数传递给打印函数：

• The tree node to be printed, and
• The indentation level

• 要打印的树节点，以及
• 缩进级别

For example, you can do this:

例如，您可以这样做：

void BinarySearchTree::postorder(tree_node* p, int indent=0)
{
    if(p != NULL) {
        if(p->left) postorder(p->left, indent+4);
        if(p->right) postorder(p->right, indent+4);
        if (indent) {
            std::cout << std::setw(indent) << ' ';
        }
        cout<< p->data << "\n ";
    }
}

The initial call should be postorder(root);

最初的电话应该是 postorder(root);

If you would like to print the tree with the root at the top, move coutto the top of the if.

如果你想在顶部根打印树，移动cout到的顶部if。

回答by Kolt

void btree::postorder(node* p, int indent)
{
    if(p != NULL) {
        if(p->right) {
            postorder(p->right, indent+4);
        }
        if (indent) {
            std::cout << std::setw(indent) << ' ';
        }
        if (p->right) std::cout<<" /\n" << std::setw(indent) << ' ';
        std::cout<< p->key_value << "\n ";
        if(p->left) {
            std::cout << std::setw(indent) << ' ' <<" \\n";
            postorder(p->left, indent+4);
        }
    }
}

With this tree:

有了这棵树：

btree *mytree = new btree();
mytree->insert(2);
mytree->insert(1);
mytree->insert(3);
mytree->insert(7);
mytree->insert(10);
mytree->insert(2);
mytree->insert(5);
mytree->insert(8);
mytree->insert(6);
mytree->insert(4);
mytree->postorder(mytree->root);

Would lead to this result:

会导致这样的结果：

回答by Grayskin

It's never going to be pretty enough, unless one does some backtracking to re-calibrate the display output. But one can emit pretty enough binary trees efficiently using heuristics: Given the height of a tree, one can guess what the expected width and setw of nodes at different depths. There are a few pieces needed to do this, so let's start with the higher level functions first to provide context.

它永远不会足够漂亮，除非您进行一些回溯以重新校准显示输出。但是可以使用启发式有效地发出足够漂亮的二叉树：给定树的高度，人们可以猜测不同深度的节点的预期宽度和 setw。有几个部分需要做到这一点，所以让我们首先从更高级别的函数开始，以提供上下文。

The pretty print function:

漂亮的打印功能：

   // create a pretty vertical tree
   void postorder(Node *p)
   {
      int height = getHeight(p) * 2;
      for (int i = 0 ; i < height; i ++) {
         printRow(p, height, i);
      }
   }

The above code is easy. The main logic is in the printRow function. Let's delve into that.

上面的代码很简单。主要逻辑在 printRow 函数中。让我们深入研究一下。

void printRow(const Node *p, const int height, int depth)
{
        vector<int> vec;
        getLine(p, depth, vec);
        cout << setw((height - depth)*2); // scale setw with depth
        bool toggle = true; // start with left
        if (vec.size() > 1) {
                for (int v : vec) {
                        if (v != placeholder) {
                                if (toggle)
                                        cout << "/" << "   ";
                                else
                                        cout << "\" << "   ";
                        }
                        toggle = !toggle;
                }
                cout << endl;
                cout << setw((height - depth)*2);
        }
        for (int v : vec) {
                if (v != placeholder)
                        cout << v << "   ";
        }
        cout << endl;
}

getLine() does what you'd expect: it stores all nodes with a given equal depth into vec. Here's the code for that:

getLine() 做你所期望的：它将所有具有给定深度的节点存储到 vec 中。这是代码：

void getLine(const Node *root, int depth, vector<int>& vals)
{
        if (depth <= 0 && root != nullptr) {
                vals.push_back(root->val);
                return;
        }
        if (root->left != nullptr)
                getLine(root->left, depth-1, vals);
        else if (depth-1 <= 0)
                vals.push_back(placeholder);
        if (root->right != nullptr)
                getLine(root->right, depth-1, vals);
        else if (depth-1 <= 0)
                vals.push_back(placeholder);
}

Now back to printRow(). For each line, we set the stream width based on how deep we are in the binary tree. This formatting will be nice because, typically, the deeper you go, the more width is needed. I say typically because in degenerate trees, this wouldn't look as pretty. As long as the tree is roughly balanced and smallish (< 20 items), it should turn out fine. A placeholder is needed to align the '/' and '\' characters properly. So when a row is obtained via getLine(), we insert the placeholder if there isn't any node present at the specified depth. The placeholder can be set to anything like (1<<31)for example. Obviously, this isn't robust because the placeholder could be a valid node value. If a coder's got spunk and is only dealing with decimals, one could modify the code to emit decimal-converted strings via getLine() and use a placeholder like "_". (Unfortunately, I'm not such a coder :P)

现在回到printRow()。对于每一行，我们根据我们在二叉树中的深度设置流宽度。这种格式会很好，因为通常情况下，你走得越深，需要的宽度就越大。我说通常是因为在退化的树中，这看起来不那么漂亮。只要树大致平衡且较小（< 20 项），结果应该没问题。需要一个占位符来正确对齐 '/' 和 '\' 字符。因此，当通过 getLine() 获取一行时，如果指定深度处不存在任何节点，我们将插入占位符。占位符可以设置为任何类似(1<<31)例如。显然，这并不可靠，因为占位符可能是一个有效的节点值。如果编码人员有勇气并且只处理小数，则可以修改代码以通过 getLine() 发出十进制转换的字符串并使用像“_”这样的占位符。（不幸的是，我不是这样的编码员：P）

The result for the following items inserted in order: 8, 12, 4, 2, 5, 15 is

按顺序插入以下项目的结果：8, 12, 4, 2, 5, 15 是

       8   
     /   \   
     4   12   
   /   \   \   
   2   5   15   

getHeight() is left to the reader as an exercise. :) One could even get prettier results by retroactively updating the setw of shallow nodes based on the number of items in deeper nodes. That too is left to the reader as an exercise.

getHeight() 留给读者作为练习。:) 甚至可以通过根据更深节点中的项目数量追溯更新浅节点的 setw 来获得更漂亮的结果。这也留给读者作为练习。

回答by Jangul Aslam

    //Binary tree (pretty print):
    //                        ________________________50______________________                        
    //            ____________30                                  ____________70__________            
    //      ______20____                                          60                ______90          
    //      10          15                                                          80                


    // prettyPrint
    public static void prettyPrint(BTNode node) {
        // get height first
        int height = heightRecursive(node);

        // perform  level order traversal
        Queue<BTNode> queue = new LinkedList<BTNode>();

        int level = 0;
        final int SPACE = 6;
        int nodePrintLocation = 0;

        // special node for pushing when a node has no left or right child (assumption, say this node is a node with value Integer.MIN_VALUE)
        BTNode special = new BTNode(Integer.MIN_VALUE);

        queue.add(node);
        queue.add(null);    // end of level 0
        while(! queue.isEmpty()) {
            node = queue.remove();

            if (node == null) {
                if (!queue.isEmpty()) {
                    queue.add(null);
                }

                // start of new level
                System.out.println();
                level++;
            } else {
                nodePrintLocation = ((int) Math.pow(2, height - level)) * SPACE;

                System.out.print(getPrintLine(node, nodePrintLocation));

                if (level < height) {
                    // only go till last level
                    queue.add((node.left != null) ? node.left : special);
                    queue.add((node.right != null) ? node.right : special);
                }
            }
        }       
    }
    public void prettyPrint() {
        System.out.println("\nBinary tree (pretty print):");
        prettyPrint(root);
    }
    private static String getPrintLine(BTNode node, int spaces) {
        StringBuilder sb = new StringBuilder();

        if (node.data == Integer.MIN_VALUE) {
            // for child nodes, print spaces
            for (int i = 0; i < 2 * spaces; i++) {
                sb.append(" ");
            }

            return sb.toString();
        }

        int i = 0;
        int to = spaces/2;

        for (; i < to; i++) {
            sb.append(' ');
        }
        to += spaces/2;
        char ch = ' ';
        if (node.left != null) {
            ch = '_';
        }
        for (; i < to; i++) {
            sb.append(ch);
        }

        String value = Integer.toString(node.data);
        sb.append(value);

        to += spaces/2;
        ch = ' ';
        if (node.right != null) {
            ch = '_';
        }
        for (i += value.length(); i < to; i++) {
            sb.append(ch);
        }

        to += spaces/2;
        for (; i < to; i++) {
            sb.append(' ');
        }

        return sb.toString();
    }

    private static int heightRecursive(BTNode  node) {
        if (node == null) {
            // empty tree
            return -1;
        }

        if (node.left == null && node.right == null) {
            // leaf node
            return 0;
        }

        return 1 + Math.max(heightRecursive(node.left), heightRecursive(node.right));
    }

回答by Sarthak Manna

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    struct Node *left,*right;
    int val;
} *root=NULL;

int rec[1000006];
void addNode(int,struct Node*);
void printTree(struct Node* curr,int depth)
{
    int i;
    if(curr==NULL)return;
    printf("\t");
    for(i=0;i<depth;i++)
        if(i==depth-1)
            printf("%s\u2014\u2014\u2014",rec[depth-1]?"\u0371":"\u221F");
        else
            printf("%s   ",rec[i]?"\u23B8":"  ");
    printf("%d\n",curr->val);
    rec[depth]=1;
    printTree(curr->left,depth+1);
    rec[depth]=0;
    printTree(curr->right,depth+1);
}
int main()
{
    root=(struct Node*)malloc(sizeof(struct Node));
    root->val=50;
    //addNode(50,root);
    addNode(75,root);    addNode(25,root);
    addNode(15,root);    addNode(30,root);
    addNode(100,root);    addNode(60,root);
    addNode(27,root);    addNode(31,root);
    addNode(101,root);    addNode(99,root);
    addNode(5,root);    addNode(61,root);
    addNode(55,root);    addNode(20,root);
    addNode(0,root);    addNode(21,root);
    //deleteNode(5,root);

    printTree(root,0);
    return 0;
}

void addNode(int v,struct Node* traveller)
{
    struct Node *newEle=(struct Node*)malloc(sizeof(struct Node));
    newEle->val=v;
    for(;;)
    {
        if(v<traveller->val)
        {
            if(traveller->left==NULL){traveller->left=newEle;return;}
            traveller=traveller->left;
        }
        else if(v>traveller->val)
        {
            if(traveller->right==NULL){traveller->right=newEle;return;}
            traveller=traveller->right;
        }
        else
        {
            printf("%d Input Value is already present in the Tree !!!\n",v);
            return;
        }
    }
}

Hope, you find it pretty...

希望，你觉得它很漂亮...

Output:

输出：

50
?———25
?   ?———15
?   ?   ?———5
?   ?   ?   ?———0
?   ?   ∟———20
?   ?        ∟———21
?   ∟———30
?        ?———27
?        ∟———31
∟———75
     ?———60
     ?   ?———55
     ?   ∟———61
     ∟———100
          ?———99
          ∟———101

回答by Karthik T

If your only need is to visualize your tree, a better method would be to output it into a dot format and draw it with grapviz.

如果您只需要可视化您的树，更好的方法是将其输出为点格式并使用 Grapviz 绘制。

You can look at dot guidefor more information abt syntax etc

您可以查看dot guide以获取更多信息 abt 语法等

回答by valiano

Here's yet another C++98 implementation, with treelike output.

这是另一个 C++98 实现，具有tree类似的输出。

Sample output:

示例输出：

PHP
└── is
    ├── minor
    │   └── perpetrated
    │       └── whereas
    │           └── skilled
    │               └── perverted
    │                   └── professionals.
    └── a
        ├── evil
        │   ├── incompetent
        │   │   ├── insidious
        │   │   └── great
        │   └── and
        │       ├── created
        │       │   └── by
        │       │       └── but
        │       └── amateurs
        └── Perl

The code:

编码：

void printTree(Node* root)
{
        if (root == NULL)
        {
                return;
        }

        cout << root->val << endl;
        printSubtree(root, "");
        cout << endl;
}

void printSubtree(Node* root, const string& prefix)
{
        if (root == NULL)
        {
                return;
        }

        bool hasLeft = (root->left != NULL);
        bool hasRight = (root->right != NULL);

        if (!hasLeft && !hasRight)
        {
                return;
        }

        cout << prefix;
        cout << ((hasLeft  && hasRight) ? "├── " : "");
        cout << ((!hasLeft && hasRight) ? "└── " : "");

        if (hasRight)
        {
                bool printStrand = (hasLeft && hasRight && (root->right->right != NULL || root->right->left != NULL));
                string newPrefix = prefix + (printStrand ? "│   " : "    ");
                cout << root->right->val << endl;
                printSubtree(root->right, newPrefix);
        }

        if (hasLeft)
        {
                cout << (hasRight ? prefix : "") << "└── " << root->left->val << endl;
                printSubtree(root->left, prefix + "    ");
        }
}

回答by MegaJiXiang

Here's a little example for printing out an array based heap in tree form. It would need a little adjusting to the algorithm for bigger numbers. I just made a grid on paper and figured out what space index each node would be to look nice, then noticed there was a pattern to how many spaces each node needed based on its parent's number of spaces and the level of recursion as well as how tall the tree is. This solution goes a bit beyond just printing in level order and satisfies the "beauty" requirement.

这是一个以树形式打印基于数组的堆的小示例。对于更大的数字，它需要对算法进行一些调整。我只是在纸上制作了一个网格并找出每个节点看起来不错的空间索引，然后注意到每个节点需要多少空间基于其父节点的空间数量和递归级别以及如何这棵树很高。这个解决方案不仅仅是按水平顺序打印，还满足了“美观”的要求。

#include <iostream>
#include <vector>

static const int g_TerminationNodeValue = -999;

class HeapJ
{
public:
HeapJ(int* pHeapArray, int numElements)
{
    m_pHeapPointer = pHeapArray;
    m_numElements = numElements;

    m_treeHeight = GetTreeHeight(1);
}

void Print()
{
    m_printVec.clear();

    int initialIndex = 0;
    for(int i=1; i<m_treeHeight; ++i)
    {
        int powerOfTwo = 1;
        for(int j=0; j<i; ++j)
        {
            powerOfTwo *= 2;
        }

        initialIndex += powerOfTwo - (i-1);
    }

    DoPrintHeap(1,0,initialIndex);

    for(size_t i=0; i<m_printVec.size(); ++i)
    {
        std::cout << m_printVec[i] << '\n' << '\n';
    }
}

private:
int* m_pHeapPointer;
int m_numElements;
int m_treeHeight;
std::vector<std::string> m_printVec;

int GetTreeHeight(int index)
{
    const int value = m_pHeapPointer[index-1];

    if(value == g_TerminationNodeValue)
    {
        return -1;
    }

    const int childIndexLeft = 2*index;
    const int childIndexRight = childIndexLeft+1;

    int valLeft = 0;
    int valRight = 0;

    if(childIndexLeft <= m_numElements)
    {
        valLeft = GetTreeHeight(childIndexLeft);
    }

    if(childIndexRight <= m_numElements)
    {
        valRight = GetTreeHeight(childIndexRight);
    }

    return std::max(valLeft,valRight)+1;
}

void DoPrintHeap(int index, size_t recursionLevel, int numIndents)
{
    const int value = m_pHeapPointer[index-1];

    if(value == g_TerminationNodeValue)
    {
        return;
    }

    if(m_printVec.size() == recursionLevel)
    {
        m_printVec.push_back(std::string(""));
    }

    const int numLoops = numIndents - (int)m_printVec[recursionLevel].size();
    for(int i=0; i<numLoops; ++i)
    {
        m_printVec[recursionLevel].append(" ");
    }

    m_printVec[recursionLevel].append(std::to_string(value));

    const int childIndexLeft = 2*index;
    const int childIndexRight = childIndexLeft+1;

    const int exponent = m_treeHeight-(recursionLevel+1);
    int twoToPower = 1;
    for(int i=0; i<exponent; ++i)
    {
        twoToPower *= 2;
    }
    const int recursionAdjust = twoToPower-(exponent-1);

    if(childIndexLeft <= m_numElements)
    {
        DoPrintHeap(childIndexLeft, recursionLevel+1, numIndents-recursionAdjust);
    }

    if(childIndexRight <= m_numElements)
    {
        DoPrintHeap(childIndexRight, recursionLevel+1, numIndents+recursionAdjust);
    }
}
};

const int g_heapArraySample_Size = 14;
int g_heapArraySample[g_heapArraySample_Size] = {16,14,10,8,7,9,3,2,4,1,g_TerminationNodeValue,g_TerminationNodeValue,g_TerminationNodeValue,0};

int main()
{
    HeapJ myHeap(g_heapArraySample,g_heapArraySample_Size);
    myHeap.Print();

    return 0;
}

/* output looks like this:

           16

     14          10

  8     7     9     3

2   4 1           0

*/

回答by Redacted

Foreword

前言

Late late answer and its in Java, but I'd like to add mine to the record because I found out how to do this relatively easily and the way I did it is more important. The trick is to recognize that what you really want is for none of your sub-trees to be printed directly under your root/subroot nodes (in the same column). Why you might ask? Because it Guarenteesthat there are no spacing problems, no overlap, no possibility of the left subtree and right subtree ever colliding, even with superlong numbers. It auto adjusts to the size of your node data. The basic idea is to have the left subtree be printed totally to the left of your root and your right subtree is printed totally to the right of your root.

迟到的答案及其在 Java 中的答案，但我想将我的答案添加到记录中，因为我发现了如何相对容易地做到这一点，而且我的做法更为重要。诀窍是认识到您真正想要的是不要将任何子树直接打印在根/子根节点下（在同一列中）。你为什么会问？因为它Guarentees不存在间距的问题，没有重叠，没有左子树和右子树的可能性不断碰撞，即使有超长的数字。它会自动调整到您的节点数据的大小。基本思想是将左子树完全打印在根的左侧，将右子树完全打印在根的右侧。

An anaology of how I though about this problem

我对这个问题的看法的类比

A good way to think about it is with Umbrellas, Imagine first that you are outside with a large umbrella, you represent the rootand your Umbrella and everything under it is the whole tree. think of your left subtreeas a short man (shorter than you anyway) with a smaller umbrella who is on your left under your large umbrella. Your right subtreeis represented by a similar man with a similarly smaller umbrella on your right side. Imagine that if the umbrellas of the short men ever touch, they get angry and hit each other (bad overlap). You are the rootand the men beside you are your subtrees. You must be exactly in the middle of their umbrellas (subtrees) to break up the two men and ensure they never bump umbrellas. The trick is to then imagine this recursively, where each of the two men each have their own two smaller people under their umbrella (children nodes) with ever smaller umbrellas (sub-subtrees and so-on) that they need to keep apart under their umbrella (subtree), They act as sub-roots. Fundamentally, thats what needs to happen to 'solve' the general problem when printing binary trees, subtree overlap. To do this, you simply need to think about how you would 'print' or 'represent' the men in my anaolgy.

一个很好的思考方式是用伞，首先想象你在外面拿着一把大伞，你代表根和你的伞，它下面的一切都是整棵树。把你的左子树想象成一个矮个子（反正比你矮），拿着一把小伞，在你的大伞下。你的右子树由一个相似的人代表，你的右侧有一把同样较小的伞。想象一下，如果矮个子男人的雨伞碰到过，他们就会生气并互相撞击（糟糕的重叠）。你是根，你身边的人是你的子树. 您必须正好在他们的雨伞（子树）中间才能将两个人分开并确保他们永远不会碰到雨伞。诀窍是递归地想象这一点，两个人中的每个人在他们的保护伞下（子节点）都有自己的两个较小的人，他们需要在他们的保护伞下分开更小的保护伞（子子树等）。伞（子树），它们充当子根。从根本上说，这就是在打印二叉树、子树重叠时“解决”一般问题需要发生的事情。要做到这一点，你只需要考虑如何“打印”或“代表”我的比喻中的男人。

My implementation, its limitations and its potential

我的实现、它的局限性和它的潜力

Firstly the only reason my code implementation takes in more parameters than should be needed (currentNode to be printed and node level) is because I can't easily move a line up in console when printing, so I have to map my lines first and print them in reverse. To do this I made a lineLevelMap that mapped each line of the tree to it's output (this might be useful for the future as a way to easily gather every line of the tree and also print it out at the same time).

首先，我的代码实现接受的参数比需要的更多（要打印的 currentNode 和节点级别）的唯一原因是因为打印时我无法轻松地在控制台中向上移动一行，所以我必须先映射我的行并打印他们反过来。为此，我制作了一个 lineLevelMap，将树的每一行映射到它的输出（这可能对未来有用，因为它可以轻松收集树的每一行并同时打印出来）。

//finds the height of the tree beforehand recursively, left to reader as exercise
int height = TreeHeight(root);
//the map that uses the height of the tree to detemrine how many entries it needs
//each entry maps a line number to the String of the actual line
HashMap<Integer,String> lineLevelMap = new HashMap<>();
//initialize lineLevelMap to have the proper number of lines for our tree 
//printout by starting each line as the empty string
for (int i = 0; i < height + 1; i++) {
    lineLevelMap.put(i,"");
} 

If I could get ANSI escape codes working in the java console (windows ugh) I could simply print one line upwards and I would cut my parameter count by two because I wouldn't need to map lines or know the depth of the tree beforehand. Regardless here is my code that recurses in an in-order traversal of the tree:

如果我可以在 java 控制台（windows ugh）中使用 ANSI 转义码，我可以简单地向上打印一行，然后将参数计数减少 2，因为我不需要预先映射行或知道树的深度。不管这里是我的代码，它在树的有序遍历中递归：

public int InOrderPrint(CalcTreeNode currentNode, HashMap<Integer,String> 
    lineLevelMap, int level, int currentIndent){
        //traverse left case
        if(currentNode.getLeftChild() != null){
            //go down one line
            level--;
            currentIndent = 
           InOrderPrint(currentNode.getLeftChild(),lineLevelMap,level,currentIndent);
            //go up one line
            level++;

    }
    //find the string length that already exists for this line
    int previousIndent = lineLevelMap.get(level).length();
    //create currentIndent - previousIndent spaces here
    char[] indent = new char[currentIndent-previousIndent];
    Arrays.fill(indent,' ');
    //actually append the nodeData and the proper indent to add on to the line 
    //correctly
    lineLevelMap.put(level,lineLevelMap.get(level).concat(new String(indent) + 
    currentNode.getData()));
    //update the currentIndent for all lines
    currentIndent += currentNode.getData().length();

    //traverse right case
    if (currentNode.getRightChild() != null){
        //go down one line
        level--;
        currentIndent = 
        InOrderPrint(currentNode.getRightChild(),lineLevelMap,level,currentIndent);
        //go up one line
        level++;
    }
    return currentIndent;
}

To actually print this Tree to console in java, just use the LineMap that we generated. This way we can print the lines right side up

要在 Java 中实际将此树打印到控制台，只需使用我们生成的 LineMap。这样我们就可以正面朝上打印线条

for (int i = height; i > -1; i--) {
    System.out.println(lineLevelMap.get(i));
}

How it all really works

这一切是如何运作的

The InorderPrint sub function does all the 'work' and can recursively print out any Node and it's subtrees properly. Even better, it spaces them evenly and you can easily modify it to space out all nodes equally (just make the Nodedata equal or make the algorithim think it is). The reason it works so well is because it uses the Node's data length to determine where the next indent should be. This assures that the left subtree is always printed BEFORE the root and the right subtree, thus if you ensure this recursively, no left node is printed under it's root nor its roots root and so-on with the same thing true for any right node. Instead the root and all subroots are directly in the middle of their subtrees and no space is wasted.

InorderPrint 子函数完成所有“工作”，并且可以递归打印出任何节点及其子树。更好的是，它均匀地间隔它们，您可以轻松地修改它以均匀地间隔所有节点（只需使 Nodedata 相等或使算法认为它是）。它运行良好的原因是它使用节点的数据长度来确定下一个缩进应该在哪里。这确保了左子树总是在根和右子树之前打印，因此如果您以递归方式确保这一点，则不会在其根下打印左节点，也不会在其根根下打印左节点等等，对于任何右节点也是如此。相反，根和所有子根直接位于其子树的中间，不会浪费任何空间。

An example output with an input of 3 + 2 looks like in console is:

输入为 3 + 2 的示例输出在控制台中如下所示：

And an example of 3 + 4 * 5 + 6 is:

3 + 4 * 5 + 6 的例子是：

And finally an example of ( 3 + 4 ) * ( 5 + 6 ) note the parenthesis is:

最后是 ( 3 + 4 ) * ( 5 + 6 ) 的一个例子，注意括号是：

Ok but why Inorder?

好的，但为什么是中序？

The reason an Inorder traversal works so well is because it Alwaysprints the leftmost stuff first, then the root, then the rightmost stuff. Exactly how we want our subtrees to be: everything to the left of the root is printed to the left of the root, everything to the right is printed to the right. Inorder traversal naturally allows for this relationship, and since we print lines and make indents based on nodeData, we don't need to worry about the length of our data. The node could be 20 characters long and it wouldn't affect the algorithm (although you might start to run out of actual screen space). The algorithm doesn't create any spacing between nodes but that can be easily implemented, the important thing is that they don't overlap.

中序遍历之所以如此有效是因为它总是先打印最左边的东西，然后是根，然后是最右边的东西。正是我们希望子树的样子：根左侧的所有内容都打印在根的左侧，右侧的所有内容都打印在右侧。中序遍历自然允许这种关系，并且由于我们基于 nodeData 打印行并进行缩进，因此我们无需担心数据的长度。该节点可能有 20 个字符长，并且不会影响算法（尽管您可能会开始用完实际屏幕空间）。该算法不会在节点之间创建任何间距，但可以轻松实现，重要的是它们不重叠。

Just to prove it for you (don't take my word for this stuff) here is an example with some quite long characters

只是为了向您证明这一点（不要相信我的话）这里有一个带有一些很长字符的示例

As you can see, it simply adjusts based on the size of the data, No overlap! As long as your screen is big enough. If anyone ever figures out an easy way to print one line up in the java console (I'm all ears) This will become much much simpler, easy enough for almost anyone with basic knowledge of trees to understand and use, and the best part is there is no risk of bad overlapping errors.

如您所见，它只是根据数据的大小进行调整，没有重叠！只要你的屏幕够大。如果有人想出一种简单的方法在 java 控制台中打印一行（我全神贯注）这将变得更加简单，对于几乎任何具有基本树知识的人来说都可以理解和使用，并且是最好的部分是否没有出现严重重叠错误的风险。

回答by mcm

For an Array I find this much more concise. Merely pass in the array. Could be improved to handle very large numbers(long digit lengths). Copy and paste for c++ :)

对于数组，我发现这更简洁。只需传入数组即可。可以改进以处理非常大的数字（长数字长度）。复制和粘贴 C++ :)

#include <math.h>
using namespace std;   
void printSpace(int count){
    for (int x = 0; x<count; x++) {
        cout<<"-";
    }
}
void printHeap(int heap[], int size){
    cout<<endl;
    int height = ceil(log(size)+1); //+1 handle the last leaves
    int width = pow(2, height)*height;
    int index = 0;
    for (int x = 0; x <= height; x++) { //for each level of the tree
        for (int z = 0; z < pow(2, x); z++) { // for each node on that tree level
            int digitWidth = 1;
            if(heap[index] != 0) digitWidth = floor(log10(abs(heap[index]))) + 1;
            printSpace(width/(pow(2,x))-digitWidth);
            if(index<size)cout<<heap[index++];
            else cout<<"-";
            printSpace(width/(pow(2,x)));
        }
        cout<<endl;
    }
}