首先，感谢https://www.jianshu.com/p/765ed8e6102e作者的文章，为我提供了思路。

然后，说一下问题：要求输入一个中序运算表达式，用二叉树将其存储起来，并且可以得到前序和后序表示。

关键：

  • 找出表达式中优先级最小的运算符，作为根节点，然后从其左右分成一个树
  • 优先级的大小定义：1. 不同级别之间的顺序是，括号 > 乘除 > 加减； 2. 同级，左边 > 右边
  • 要去掉表达式最外层的括号
  • 定义一个括号标志，用来记录进入的括号层级，由于括号内优先级最大，找最小优先级运算符时相当于屏蔽掉括号内的运算符
  • 定义一个结果标志，用来表示找到的最小优先级运算符是加减还是乘除，有加减就没乘除什么事
  • 递归，不停地找表达式的最小优先级运算符，直到表达式的长度小于3，即他不可能再有运算符（我们认为表达式长度至少3，例如负数应该写作(-4)这样）

找到字符串中优先级最小的运算符

// 找到字符串中优先级最小的运算符
function getMinPriorityOpe(exp) {
    let bracketFlag = 0; // 括号标志
    let resultFlag = 0; // 结果标志
    let result;
    for (let i = 0; i < exp.length; i++) {
        let char = exp.charAt(i);
        switch (char) {
            case "+":
            case "-":
                if (bracketFlag === 0) {
                    resultFlag = 1; // 有了+-肯定就没*/什么事了
                    result = {
                        root: char,
                        left: exp.slice(0, i),
                        right: exp.slice(i + 1)
                    }
                }
                break;
            case "*":
            case "/":
                if (bracketFlag === 0 && resultFlag === 0) {
                    result = {
                        root: char,
                        left: exp.slice(0, i),
                        right: exp.slice(i + 1)
                    };
                }
                break;
            case "(":
                bracketFlag++;
                break;
            case ")":
                bracketFlag--;
                break;
            default:
                break;
        }
    }
    return result;
}

去掉最外层括号

// 去最外层括号运算
function brackets(exp) {
    if (exp.charAt(0) === '(' && exp.charAt(exp.length - 1) === ")") {
        return exp.slice(1, -1);
    }
    return exp;
}

递归实现

// 递归
function recursive(tree) {
    if (tree.left.length >= 3) {
        tree.left = recursive(getMinPriorityOpe(brackets(tree.left)));
    }
    if (tree.right.length >= 3) {
        tree.right = recursive(getMinPriorityOpe(brackets(tree.right)));
    }
    return tree
}
// 前序遍历
function print_prefix(tree) {
    if (tree.root !== null) {
        console.log(tree.root);
        if (typeof (tree.left) === 'string') {
            console.log(tree.left);
        } else {
            print_prefix(tree.left);
        }
        if (typeof (tree.right) === 'string') {
            console.log(tree.right)
        } else {
            print_prefix(tree.right)
        }
    }
}
// 后序遍历
function print_postfix(tree) {
    if (tree.root !== null) {
        if (typeof (tree.left) === 'string') {
            console.log(tree.left);
        } else {
            print_postfix(tree.left);
        }
        if (typeof (tree.right) === 'string') {
            console.log(tree.right)
        } else {
            print_postfix(tree.right)
        }
        console.log(tree.root);
    }
}

// main
let exp = "(1*(2+3)/4*5+6)";
let tree = recursive(getMinPriorityOpe(brackets(exp)));

console.log("前序遍历：")
print_prefix(tree);
console.log("后序遍历：")
print_postfix(tree);

最终前序遍历的结果应该是：+*/*1+23456

后序遍历结果是：123+*4/5*6+

鉴于网上js实现数据结构的资料不是很多，后续有机会的话我会分享更多js数据结构的实现，抛砖引玉，以飨读者。