数据结构与算法——Java实现 45.根据后缀表达式建树

别担心，一切都是最好的安排

                                —— 24.10.22

根据后缀表达式建树

根据一个后缀表达式来构造表达式的树

中缀表达式：(2-1)*3

后缀（逆波兰）表达式：21-3*

表达式的树：

                *

              /    \

            -        3

          /    \    

        2       1 

思路

用栈解决这个问题（首先判断合法性）

从左向右遍历后缀表达式

1.遇到数字则入栈

2.遇到运算符则出栈，建立节点关系，然后再入栈

3.先弹栈的是右孩子，后弹栈的是左孩子

合法性：

先弹栈的是右孩子，后弹栈的是左孩子

验证：根据后缀表达式建的树，进行后序遍历，求得的表达式应该是原来的后缀表达式

代码实现

节点类

由于传入的后缀表达式是字符串，所以将结点类和实现改变一下

    static class TreeNode{
        public String val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(String val){
            this.val = val;
        }

        public TreeNode(String val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return this.val;
        }
    }

后缀表达式建树

使用栈对后缀表达式从左到右进行遍历，对后缀表达式中的每一个字符进行判断，如果是数字则入栈，如果是字符则将栈中的元素出栈，先出的元素建立在符号的右子树，后出的元素为左子树，然后再将这个字符进行入栈，继续遍历

    public static TreeNode constructExpression(String[] expression) {
        if (expression == null || expression.length == 0) {
            return null;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();
        for (String s : expression) {
            switch (s){
                case "+","-","*","/" -> {
                    TreeNode right = stack.pop();
                    TreeNode left = stack.pop();
                    TreeNode parent = new TreeNode(s);
                    parent.left = left;
                    parent.right = right;
                    stack.push(parent);
                }
                default -> {
                    stack.push(new TreeNode(s));
                }
            }
        }
        return stack.peek();
    }

后序遍历 

根据后缀表达式建的树，进行后序遍历，求得的表达式应该是原来的后缀表达式

反向思考，要想验证出所建立的二叉树，最后将二叉树进行后序遍历，与给出的后缀表达式进行比较，则可以判断是否正确

    public static void post(CreateTreeByExpression.TreeNode node, ArrayList<String> res){
        if (node == null){
            return;
        }
        post(node.left, res);
        post(node.right, res);
        res.add(node.val);
    }

整体代码

package Day16BinaryTree;

import java.util.ArrayList;
import java.util.LinkedList;

public class CreateTreeByExpression {
    static class TreeNode{
        public String val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(String val){
            this.val = val;
        }

        public TreeNode(String val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return this.val;
        }
    }

    public static void post(CreateTreeByExpression.TreeNode node, ArrayList<String> res){
        if (node == null){
            return;
        }
        post(node.left, res);
        post(node.right, res);
        res.add(node.val);
    }

    public static TreeNode constructExpression(String[] expression) {
        if (expression == null || expression.length == 0) {
            return null;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();
        for (String s : expression) {
            switch (s){
                case "+","-","*","/" -> {
                    TreeNode right = stack.pop();
                    TreeNode left = stack.pop();
                    TreeNode parent = new TreeNode(s);
                    parent.left = left;
                    parent.right = right;
                    stack.push(parent);
                }
                default -> {
                    stack.push(new TreeNode(s));
                }
            }
        }
        return stack.peek();
    }

    public static void main(String[] args) {
        String[] expression = {"2","1","-","3","*"};
        TreeNode root = new CreateTreeByExpression().constructExpression(expression);
        ArrayList<String> res = new ArrayList<>();
        post(root, res);
        System.out.println(res.toString());
    }
}