[数据结构与算法]c++可视化 横向打印二叉树（连线、规整）

最近本人在和 avl 树、红黑树进行“友好交流”，特此水一篇可视化辅助。直接放结果 ：

一、 二叉树实现?

#include <iostream>
#include <vector>
using namespace std;
#define MAX_SIZE 1000

struct node
{
    int key;
    int l, r;
};

node tree[MAX_SIZE] = {{0, 1, 0}};
int cnt;

void add(int key, int &root = tree[0].l)
{
    if (root == 0)
    {
        root = ++cnt;
        tree[cnt] = {key};
    }
    else if (key < tree[root].key)
        add(key, tree[root].l);
    else
        add(key, tree[root].r);
}

二、打印函数

#include <iostream>
#include <vector>
using namespace std;

inline void trans(vector<string> &x, string before, string after)//转换第一个匹配的字符串
{
    for (auto &p : x)
        if (p == before)
        {
            p = after;
            break;
        }
}

void show(int root, vector<string> pre = vector<string>(0))
{
    auto &p = tree[root];

    if (p.key != 0)
    {
        vector<string> temp(pre);
        trans(temp, "┌──", "   ");
        trans(temp, "└──", "│  ");
        temp.push_back("┌──");
        show(p.l, temp);
    }

    for (auto &i : pre)
        cout << i;
    if (p.key == 0)
        cout << "null" << endl;
    else
        cout << p.key << endl;

    if (p.key != 0)
    {
        vector<string> temp(pre);
        trans(temp, "┌──", "│  ");
        trans(temp, "└──", "   ");
        temp.push_back("└──");
        show(p.r, temp);
    }
}


// cout << string("┌──").size() << endl;
// cout << string("├──").size() << endl;
// cout << string("└──").size() << endl;
// cout << string("│  ").size() << endl;
// cout << string("   ").size() << endl;

三、完整代码

更新：引入删除功能?

#include <iostream>
#include <vector>
#include <time.h>
using namespace std;
#define MAX_SIZE 1000

struct node
{
    int key;
    int l, r;
};

node tr[MAX_SIZE] = {{0, 0, 1}};
int cnt;

void add(int key, int &root = tr[0].r)
{
    if (root == 0)
    {
        root = ++cnt;
        tr[cnt] = {key, 0, 0};
    }
    else if (key < tr[root].key)
        add(key, tr[root].l);
    else if (key > tr[root].key)
        add(key, tr[root].r);
}

void del(int key, int &root = tr[0].r)
{
    if (root == 0)
        return;
    auto &p = tr[root];
    if (key < p.key)
        del(key, p.l);
    else if (key > p.key)
        del(key, p.r);
    else
    {
        if (p.l == 0 && p.r == 0)
            root = 0;
        else if (p.l == 0 && p.r != 0)
            root = p.r;
        else if (p.l != 0 && p.r == 0)
            root = p.l;
        else if (tr[p.r].l == 0) //后继是右子树的根
        {
            tr[p.r].l = p.l;
            root = p.r;
        }
        else
        {
            int last = root;
            root = p.r;
            while (tr[root].l != 0) //找右子树的最小值，维护父指针last
            {
                last = root;
                root = tr[root].l;
            }
            tr[last].l = tr[root].r;
            tr[root].l = p.l;
            tr[root].r = p.r;
        }
    }
}

//
void show(int root = 1, vector<string> pre = vector<string>(0));

int main()
{
    srand(time(0));
    for (int i = 1; i <= 20; ++i)
        add(rand() % 100);
    show();
    int ch = 1;
    do
    {
        int temp;
        puts("请输出操作码：");
        puts("1：打印");
        puts("2：删除");
        puts("0：退出");
        cin >> ch;
        if (ch == 1)
            show();
        else if (ch == 2)
        {
            cin >> temp;
            del(temp);
        }
    } while (ch);
}

inline void trans(vector<string> &x, string before, string after)
{
    for (auto &p : x)
        if (p == before)
        {
            p = after;
            break;
        }
}

void show(int root, vector<string> pre)
{
    auto &p = tr[root];

    if (p.key != 0)
    {
        vector<string> temp(pre);
        trans(temp, "┌──", "   ");
        trans(temp, "└──", "│  ");
        temp.push_back("┌──");
        show(p.l, temp);
    }

    for (auto &i : pre)
        cout << i;
    if (p.key == 0)
        cout << "null" << endl;
    else
        cout << p.key << endl;

    if (p.key != 0)
    {
        vector<string> temp(pre);
        trans(temp, "┌──", "│  ");
        trans(temp, "└──", "   ");
        temp.push_back("└──");
        show(p.r, temp);
    }
}

// cout << string("┌──").size() << endl;
// cout << string("├──").size() << endl;
// cout << string("└──").size() << endl;
// cout << string("│  ").size() << endl;
// cout << string("   ").size() << endl;