表达式二叉树

表达式二叉树

文章目录

• • 1. 表达数二叉树构建
  • 2. 表达式二叉树求值
  • 3. 代码实现

表达式二叉树是指：用二叉树表示表达式的运算规则，节点元素有两种含义； *** 作数（包含变量）和运算法。 *** 作数节点都是叶子节点，运算符节点都是二度节点，其中子节点是参加该运算的子表达式。
其中表达式分为前缀（二叉树前序遍历）、中缀（二叉树中序遍历）、后缀（二叉树后序遍历）。

日常中算数表达式习惯的书写习惯为中缀表达式。中序遍历统计运算中先运算的一定为左子树
一般来说通过一种遍历无法确定唯一的一颗二叉树，但是算数表达式比较特殊，表达式二叉树可以根据表达式确定一颗唯一的二叉树。

1. 表达数二叉树构建

表达式构建规则如下：
创建 *** 作符栈用来存储 *** 作符，遍历字符串：
1.如果字符是数字，则获取后续所有的数字，创建 *** 作数节点;
2.如果字符是 *** 作符：
2.1 首先创建 *** 作符节点
2.2 *** 作符节点一定要设置左孩子节点（ *** 作数节点/子表达式）
2.2.1 如果栈顶 *** 作符不为空且栈顶 *** 作符不等于“(”，比较当前 *** 作符与栈顶 *** 作符的优先级，如果栈顶 *** 作符优先级低于当前 *** 作符，则为当前 *** 作符设置 *** 作数节点作为左孩子节点，当前 *** 作符入栈；（该情况下一定有 *** 作数节点）
2.2.2 如果栈顶 *** 作符优先级高于或等于当前 *** 作符，则栈顶 *** 作符出栈， *** 作数节点作为栈顶 *** 作符的右孩子节点，栈顶 *** 作符节点作为当前 *** 作符节点的左孩子节点，当前 *** 作符节点入栈；
2.2.3 特殊情况（如果栈为空或者栈顶 *** 作符为“(” -23 或（-2+3））对于这种情况，遍历至“-”时，没有 *** 作数节点，可以创建一个值为“0”的 *** 作数节点作为左孩子节点，然后将当前 *** 作符节点入栈；
“(1+2)(3+4)”对于这种情况，“*” *** 作符无左孩子节点且左孩子节点不为“0”，栈顶 *** 作符作为当前 *** 作符的左孩子节点。
3.如果当前 *** 作符是“(”,直接入栈
4.如果当前 *** 作符是“)”,则出栈所有 *** 作符，直到“(”为止；将 *** 作数节点作为第一个 *** 作符节点的右孩子节点，上层 *** 作符节点均作为下层 *** 作符节点的右孩子节点；
遍历结束后出栈所有 *** 作符节点， *** 作数作为栈顶 *** 作符的右孩子节点，上层 *** 作符作为下层 *** 作符的右孩子节点。

简单总结：入栈设置左孩子，出栈设置右孩子，遇到“(”找“)”，入栈无 *** 作数左孩子设置为“0”，栈定 *** 作符必有右 *** 作数。

2. 表达式二叉树求值

利用递归方法求值，如果遇到 *** 作符则根据当前规则计算子表达式，遇到 *** 作数则直接返回。

3. 代码实现

public class expressionBinTree {
    //表达式优先级
    static Map operator = new HashMap() {
        {
            put("+", 1);
            put("-", 1);
            put("*", 2);
            put("/", 2);
        }
    };

    //二叉树
    static class TreeNode {
        private String val;
        private TreeNode left;
        private TreeNode right;

        public String getVal() {
            return val;
        }

        public void setVal(String val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }

    //根据中缀表达式创建二叉树
    public static TreeNode createByInfix(String infix) {
        //去除空格
        infix = infix.replaceAll(" ", "");
        char[] chars = infix.toCharArray();
        int n = chars.length;
        // *** 作符存储栈
        linkedList stack = new linkedList<>();
        TreeNode p = null;
        TreeNode child = null;
        for (int i = 0; i < n; i++) {
            char c = chars[i];
            //"("直接入栈
            if (c == '(') {
                p = new TreeNode();
                p.setVal(String.valueOf(c));
            } else if (c == ')') {
                //出栈所有操作符到"（"节点为止
                while (!stack.isEmpty()) {
                    //当前操作符作为栈顶操作符的右子树
                    if (!Objects.equals(stack.peek().getVal(), "(")) {
                        TreeNode treeNode = stack.pop();
                        if (child != null) {
                            treeNode.setRight(child);
                            child = null;
                        }
                        if (p != null) {
                            treeNode.setRight(p);
                        }

                        p = treeNode;
                    } else {
                        //"("直接出栈
                        stack.pop();
                        break;
                    }
                }
            } else {
                //创建数字子节点
                if (isNumber(c)) {
                    StringBuilder num = new StringBuilder(c + "");
                    int j = i + 1;
                    while (j < n && isNumber(chars[j])) {
                        num.append(chars[j++]);
                    }
                    i = j - 1;
                    child = new TreeNode();
                    child.setVal(num.toString());
                } else {
                    //构建操作符节点p
                    p = new TreeNode();
                    p.setVal(String.valueOf(c));
                    TreeNode treeNode = stack.peek();
                    if (treeNode != null) {
                        if (!Objects.equals(treeNode.getVal(), "(")) {
                            //如果栈顶操作符优先级低于当前操作符优先级 直接入栈
                            if (operator.get(treeNode.getVal()) < operator.get(String.valueOf(c))) {
                                if (child != null) {
                                    p.setLeft(child);
                                    child = null;
                                }
                            } else {
                                //同级或栈顶操作符优先级高于当前操作符，则应该将当前操作符作为栈顶操作符的右孩子节点
                                if (!Objects.equals(treeNode.getVal(), "(")) {
                                    treeNode = stack.pop();
                                    p.setLeft(treeNode);
                                    if (child != null) {
                                        treeNode.setRight(child);
                                        child = null;
                                    }
                                }
                            }
                        } else {
                            //如果栈顶元素是"（"，child == null则为操作符增加左孩子节点"0"
                            if (child == null) {
                                treeNode = new TreeNode();
                                treeNode.setVal("0");
                                p.setLeft(treeNode);
                            }
                        }
                    } else {
                        if (child == null) {
                            treeNode = new TreeNode();
                            treeNode.setVal("0");
                            p.setLeft(treeNode);
                        }
                    }

                    if (child != null) {
                        p.setLeft(child);
                        child = null;
                    } else if (p.getLeft() == null && !stack.isEmpty()) {
                        p.setLeft(stack.pop());
                    }
                }
            }

            //操作符节点不为null，操作符节点入栈
            if (p != null) {
                stack.push(p);
                p = null;
            }
        }

        //出栈所有操作符
        while (!stack.isEmpty()) {
            TreeNode treeNode = stack.pop();
            //child节点作为栈顶操作符的右孩子节点
            if (child != null) {
                treeNode.setRight(child);
                child = null;
            }
            if (p != null) {
                treeNode.setRight(p);
            }

            p = treeNode;
        }

        return p;
    }

    //表达式二叉树求值
    static int calculator(TreeNode root) {
        switch (root.val) {
            case "+": return calculator(root.left) + calculator(root.right);
            case "-": return calculator(root.left) - calculator(root.right);
            case "*": return calculator(root.left) * calculator(root.right);
            case "/": return calculator(root.left) / calculator(root.right);
            default: return Integer.parseInt(root.val);
        }
    }

    //判断字符是否是数字
    static boolean isNumber(Character character) {
        return Character.isDigit(character);
    }

    public static void main(String[] args) {
        TreeNode byInfix = createByInfix("(+2)");
        int res = calculator(byInfix);
        System.out.println(res);
    }
}