控制台横向输出二叉树树形结构（C++）-创新互联

测试用数据选择的都是两位数，所以二叉树每层设计成横向占3个字符，其中第一个字符是┌或└，'┌’表示是从父节点向上拐过来的，'└’表示向下拐过来的，后面两位留给数字。

输出的树形每一行只会有一个数字出现，且数字之后不是换行（叶节点）就是表示有子树需要分叉的’┤’等。所以输出时主要考虑节点数字前的前置输出，主要包括两方面：

一是与控制台最左边相隔的距离，可以根据当前节点的深度，或者当前节点处于第几层来确定，因为每层长度固定为3。当然这段输出并不全是空格的，前面某些层发出的树枝，即’│’，可能会对后面节点的前置输出造成影响。比如演示图中的16，25和15发出的分支都对16的前置造成了影响（16前面的└与16归属同一层，直接与路径最后是上拐还是下拐相关）。

第二步就是确定这段距离中需要在哪些位置出现’│’。某一层的三个占位中’│’只有可能出现在第一个，而至于前置的几层中哪几个地方会出现’│’，通过观察找规律可以发现与已走过路径的异或值相关。具体的，预览图中的16，其走过的路径为“下下上下”，从第二位将每一位与前一位异或，结果是“011”，所以前置路径就是“ ” + "│ " + "│ "。当然还需要加上根节点所在那一层的三个空格（注意50前面留了一个空格）。然后再根据路径最后的值选择16前面是┌或└，然后输出16，再根据16的子树情况选择是否要输出┐┘┤这些（这些是为下一层留下的东西）。

#define RIGHT '0'
#define LEFT '1'
string up_right = "┌";
string down_right = "└";
string up_left = "┐";
string down_left = "┘";
string T_cross = "┤";
string line = "│";

typedef struct BSTNode
{int key;
    struct BSTNode *left, *right;
} BSTNode;

BSTNode *Insert(BSTNode *T, int key)
{if (T == NULL)
    {T = new BSTNode();
        T->key = key;
        T->left = NULL;
        T->right = NULL;
        return T;
    }
    else if (T->key == key)
        return T;
    else if (T->key >key)
        T->left = Insert(T->left, key);
    else if (T->key< key)
        T->right = Insert(T->right, key);

    return T;
}

void ShowTree(BSTNode *T, string way = "") // way表示达到该节点走过的路，从根开始，向右是'0'，向左是'1'
{if (T->right != NULL)
    {string right_way = way + RIGHT;
        ShowTree(T->right, right_way);
    }

    string pre;            // 打印节点前需要输出的前置数据
    if (way.length() == 0) // 根节点，不考虑前置输出，这里输出一个空格
        pre = " ";
    else
    {pre = "   ";  // 这三个空格来自根节点那一层
        for (int i = 1; i< way.length(); i++)
        {// 按照异或关系补全前置输出
            if (way.at(i) != way.at(i - 1))
            {pre += line;
                pre += "  ";
            }
            else
            {pre += "   ";
            }
        }
        int l = way.length();
        // 根据最后一次转弯方向选择数字前面的符号
        if (way.at(l - 1) == '0')
            pre += up_right;
        else
            pre += down_right;
    }

    cout<< pre<< setw(2)<< T->key;
    // 根据左右子树情况为下一层留下分叉标志
    if (T->left != NULL && T->right != NULL)
        cout<< T_cross;
    else if (T->left != NULL && T->right == NULL)
        cout<< up_left;
    else if (T->left == NULL && T->right != NULL)
        cout<< down_left;
    cout<< endl;

    if (T->left != NULL)
    {string left_way = way + LEFT;
        ShowTree(T->left, left_way);
    }
}

int main()
{int nums[20] = {50, 75, 25, 90, 60, 40, 15, 100, 86, 80, 88, 69, 58, 52, 46, 39, 18, 12, 20, 16};
    BSTNode *T = NULL;
    for (int i = 0; i< 20; i++)
        T = Insert(T, nums[i]);
    ShowTree(T);
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧