博客

思路：先把输入的中缀表达式转化为后缀表达式，再通过后缀表达式来建立一颗表达式二叉树，最后正向打印二叉树。

正向打印二叉树的思路已写在_initPos_函数中，具体参见注释。

#include <bits/stdc++.h>
using namespace std;`在这里插入代码片`
struct node
{//节点类
    char value;
    node *left;
    node *right;
    int level = 0;//节点的行坐标
    int column = 10;//节点的列坐标 默认为10
    node(char _a, node *_l = NULL, node *_r = NULL)
    {//节点类的构造函数
        value = _a;
        left = _l;
        right = _r;
    }
};
class Tree
{//二叉树类
private:
    stack<node*> lake;//用于在构建二叉树时保存子树的栈
    node *myroot;//树根
    char draw[100][100];//画板 默认时全都为空格字符 
    int Cmin = 100; //二叉树的最左边的y坐标
    int Cmax = 0;//二叉树最右边的y坐标 列坐标
    int Lmax = 0;//二叉树的最大x坐标 即行坐标
public:
    Tree()
    {//二叉树的构造函数
        _initD_();//初始化画板数组
        myroot = NULL;//初始化根节点
    }

    void _initD_(){//画板数组的初始化函数
        for (int i = 0; i < 100; i++){
            for (int j = 0; j < 100; j++){
                draw[i][j] = ' ';//默认全都置空
            }
        }
    }

    node *front()
    {//头节点的访问函数
        return myroot;
    }

    void creatTreeByMidExpression(string midexp)
    {//通过中缀表达式建立二叉树
        string s = TransToAfexp(midexp);//把中缀表达式转化为后缀表达式 便于之后的处理
        for (int i = 0; i < s.length(); i++)
        {
            node* father = NULL;
            node *left = NULL;
            node *right = NULL;
            if (IsOperator(s[i]))
            {
                right = lake.top();
                lake.pop();
                left = lake.top();
                lake.pop();
            }
            father = new node(s[i], left, right);
            lake.push(father);
        }//程序逻辑：从头至尾遍历后缀表达式  遇到运算符 就将运算符前面的两个元素与运算符一起建立一个子树 然后将这个子树压入待处理栈 当遇到一个运算符前面的两个字符中有运算符时 就讲栈顶的元素作为当前所访问的运算符的左子树或右子树
        myroot = lake.top();//最后直接返回栈顶的元素就是要求的表达式二叉树
    }

    string TransToAfexp(string midexp)
    {//将中缀表达式转化为后缀表达式的函数
        string res;
        map<char, int> Operator;
        Operator['+'] = 1;
        Operator['-'] = 1;
        Operator['*'] = 2;
        Operator['/'] = 2;
        Operator['('] = 3;
        Operator['0'] = 0;//定义各种运算符的优先级 保证栈顶的元素的优先级一定是最大的 具体实现方法和教材采取的方法大同小异
        stack<char> OpratorStack;
        OpratorStack.push('0');
        for (int i = 0; i < midexp.length(); i++)
        {
            if (!IsOperator(midexp[i]))
            {
                res += midexp[i];
            }
            else
            {
                if (midexp[i] == '(')
                {
                    OpratorStack.push(midexp[i]);
                    continue;
                }
                if (midexp[i] == ')')
                {
                    while (OpratorStack.top() != '(')
                    {
                        res += OpratorStack.top();
                        OpratorStack.pop();
                    }
                    OpratorStack.pop();
                    continue;
                }
                if (OpratorStack.top() == '(')
                {
                    OpratorStack.push(midexp[i]);
                    continue;
                }
                if (Operator[midexp[i]] > Operator[OpratorStack.top()])
                    OpratorStack.push(midexp[i]);
                else
                {
                    while (Operator[midexp[i]] <= Operator[OpratorStack.top()] && OpratorStack.top() != '0')
                    {
                        res += OpratorStack.top();
                        OpratorStack.pop();
                    }
                    OpratorStack.push(midexp[i]);
                }
            }
        }
        while (OpratorStack.top() != '0')
        {
            res += OpratorStack.top();
            OpratorStack.pop();
        }
        return res;//返回处理好的后缀表达式
    }

    bool IsOperator(char s)
    {//判断一个字符是否是运算符
        return s == '+' || s == '-' || s == '*' || s == '/' || s == ')' || s == '(';
    }

    void display(node *root)
    {//调试用的显示函数
        if (root != NULL)
        {
            display(root->left);
            display(root->right);
            cout << root->value << endl;
        }
    }

    void _initPos_(node* root){//初始化各个节点的位置
        if (root != NULL){
            if (root->left){
                root->left->level = root->level + 1;
                if (2*root->left->level > Lmax) Lmax = 2*root->left->level;
                root->left->column = root->column - (5 - root->left->level);
                if (Cmin > 2*root->left->column) Cmin = 2*root->left->column;
            } 
            _initPos_(root->left);
            if (root->right){
                if (2*root->right->level > Lmax) Lmax = 2*root->right->level;
                root->right->level = root->level + 1;
                root->right->column = root->column + (5 - root->right->level);
                if (Cmax < 2*root->right->column) Cmax = 2*root->right->column;
            }
            _initPos_(root->right);
        }
    }//程序逻辑：越接近于根节点的位置 列坐标的变化越大 而对于接近根的程度可以用行坐标来描述 对于一个节点 左儿子的列坐标比父节点的列坐标小 而右儿子的列坐标比父节点的列坐标要大 根据深度来做出相应的调整即可

    void printPos(node* root){ //中序遍历整棵树 输出各个节点的坐标和值
        if (root != NULL){
            printPos(root->left);
            cout << "(" << root->level << "," << root->column << ") " << root->value                                                                   << endl;
            printPos(root->right);
        }
    }

    void _initPrint_(node* root){ //初始化画板数组 将各个节点的坐标映射到画板数组中去 为了让效果更明显 坐标进行了放大处理
        if (root != NULL){
            _initPrint_(root->left);
            draw[2*root->level][2*root->column] = root->value;
            _initPrint_(root->right);
        }
    }

    void print(){//打印二叉树
        for (int j = 0; j <= Lmax; j++){
            for (int i = Cmin; i <= Cmax; i++){
                cout << draw[j][i];
            }
            cout << endl;
        }
    }
};
int main()
{
    Tree s;
    s.creatTreeByMidExpression("a*b+(c-d)/e-f");
    s._initPos_(s.front());
    cout << "position of each node:" << endl;
    s.printPos(s.front());
    s._initPrint_(s.front());
    cout << "expression tree of a*b+(c-d)/e-f is:\n";
    s.print();
    system("pause");
    return 0;
}