四步打印二叉树

效果图：

0
├──1
│  ├──3
│  │  └──7
│  │     ├──8
│  │     └──9
│  └──4
└──2
   ├──5
   └──6

step 1

void printTree(Tree* root, string prefix){
    if(root == nullptr){
        return;
    }
    std::cout<<prefix<<root->data<<endl;

    printTree(root->left, prefix+"│ ");
    printTree(root->right, prefix+"│ ");
}

res

0
│ 1
│ │ 3
│ │ │ 7
│ │ │ │ 8
│ │ │ │ 9
│ │ 4
│ 2
│ │ 5
│ │ 6

结果只是树的遍历，能显示每层树的深度，但没有节点指向。下面我们给子节点加上└──和├──。

step 2

void printTree(Tree* root, string prefix, string endPoint){
    if(root == nullptr){
        return;
    }
    std::cout<<prefix<<endPoint<<root->data<<endl;

    // 只有一个节点 或 最后一个子节点 的前缀是 └──
    if(root->right==nullptr){
        endPoint = "└──";
    }else{
        endPoint = "├──";
    }

    printTree(root->left, prefix+"│  ", endPoint);
    printTree(root->right, prefix+"│  ", "└──");
}

res

0
│  ├──1
│  │  ├──3
│  │  │  └──7
│  │  │  │  ├──8
│  │  │  │  └──9
│  │  └──4
│  └──2
│  │  ├──5
│  │  └──6

这步的秘诀就在于，└──的使用时机：

• 最后一个节点必定是
• 只有一个节点也是

到这步已经差不多了，但是root层多了一层，怎么回事？将│的个数想象成深度，我们需要的是从零开始计数，而不是从一开始计数。

step 3

void printTreeNodes(Tree* root, string prefix, string endPoint){
    if(root == nullptr){
        return;
    }
    std::cout<<prefix<<endPoint<<root->data<<endl;

    // 只有一个节点 或 最后一个子节点 的前缀是 └──
    if(root->right==nullptr){
        endPoint = "└──";
    }else{
        endPoint = "├──";
    }

    printTreeNodes(root->left, prefix+"│  ", endPoint);
    printTreeNodes(root->right, prefix+"│  ", "└──");
}

void printTree(Tree* root){
    if(root == nullptr){
        return;
    }
    std::cout<<root->data<<endl;

    // 只有一个节点 或 最后一个子节点 的前缀是 └──
    string endPoint = "";
    if(root->right==nullptr){
        endPoint = "└──";
    }else{
        endPoint = "├──";
    }

    // 从零开始计数
    printTreeNodes(root->left, "", endPoint);
    printTreeNodes(root->right, "", "└──");
}

res

0
├──1
│  ├──3
│  │  └──7
│  │  │  ├──8
│  │  │  └──9
│  └──4
└──2
│  ├──5
│  └──6

很好，已经非常接近了。我们仔细观察2的打印，2已经没有相邻的兄弟节点了，但是前缀仍然添加了│ ，这很不妙。下一步就是去除它，可是节点5和6的prefix是2传下来的，说明在2（父节点）的时候就应该调整前缀了。怎么调整？

如何知道没有相邻节点了？不就是我的endPoint为└──的场景吗？

step 4

void printTreeNodes(Tree* root, string prefix, string endPoint){
    if(root == nullptr){
        return;
    }
    std::cout<<prefix<<endPoint<<root->data<<endl;

    string lastPrefix = "";
    if(endPoint == "└──"){
        lastPrefix = "   ";
    }else{
        lastPrefix = "│  ";
    }

    // 只有一个节点 或 最后一个子节点 的前缀是 └──
    if(root->right==nullptr){
        endPoint = "└──";
    }else{
        endPoint = "├──";
    }

    printTreeNodes(root->left, prefix+lastPrefix, endPoint);
    printTreeNodes(root->right, prefix+lastPrefix, "└──");
}

void printTree(Tree* root){
    if(root == nullptr){
        return;
    }
    std::cout<<root->data<<endl;

    // 只有一个节点 或 最后一个子节点 的前缀是 └──
    string endPoint = "";
    if(root->right==nullptr){
        endPoint = "└──";
    }else{
        endPoint = "├──";
    }

    // 从零开始计数
    printTreeNodes(root->left, "", endPoint);
    printTreeNodes(root->right, "", "└──");
}

res

0
├──1
│  ├──3
│  │  └──7
│  │     ├──8
│  │     └──9
│  └──4
└──2
   ├──5
   └──6

完整代码

#include <iostream>
#include <string>

using namespace std;

struct Tree{
    int data;
    Tree* left;
    Tree* right;
    Tree(int data, Tree* l = nullptr, Tree* r = nullptr):data(data), left(l), right(r){}
    void set(Tree* l, Tree* r){
        left = l;
        right = r;
    }
};

/*
    │

    ├──

    └── 这个符号意味着孤单的子树
*/
void printTreeNodes(Tree* root, string prefix, string endpoint);

void printTree(Tree* root){
    if (root==nullptr) { return;}
    cout<<root->data<<endl;

    string endpointForLeft = (root->right) ? "├──" : "└──";

    printTreeNodes(root->left, "", endpointForLeft);
    printTreeNodes(root->right, "", "└──");
}

void printTreeNodes(Tree* root, string prefix, string endpoint){
    if (root==nullptr) {
        return;
    }

    cout<<prefix<<endpoint<<root->data<<endl;

    string endpointForLeft = (root->right) ? "├──" : "└──";
    string prefixExtra = (endpoint == "└──") ? "   " :"│  ";

    printTreeNodes(root->left, prefix+prefixExtra, endpointForLeft);
    printTreeNodes(root->right, prefix+prefixExtra, "└──");
}


int main() {
    Tree left(1);
    Tree right(2);
    Tree root(0, &left, &right);
    Tree l4(3);
    Tree l5(4);
    left.set(&l4, &l5);
    Tree l6(5);
    Tree l7(6);
    right.set(&l6, &l7);
    Tree l8(7);
    Tree l9(8);
    Tree l10(9);
    l8.set(&l9, &l10);
    l4.left = &l8;

    printTree(&root);
}