一、中序线索化

二叉树节点定义：

class TreeNode {

    int val = 0;

    TreeNode left = null;

    TreeNode right = null;

    int isleftChild = 1;//0:线索 1:左孩子

    int isrightChild = 1;

    public TreeNode(int val) {

        this.val = val;

    }

}

在中序遍历的过程中完成线索化

   //preNode始终指向中序序列中前一个访问的节点

    private static TreeNode preNode = null;//只能用全局变量的形式来记录。

    //curNode始终指向中序序列中当前访问的节点

    public static TreeNode inIOrderThread(TreeNode curNode) {

        if (curNode == null)

            return null;

        //线索化左子树

        InClueTree(curNode.left);

        //线索化当前节点

        if (curNode.left == null) {

            curNode.isleftChild = 0;

            curNode.left = preNode;

        }

        if (preNode != null && preNode.right == null) {

            preNode.isrightChild = 0;

            preNode.right = curNode;

        }

        preNode = curNode;//

        //线索化右子树

        InClueTree(curNode.right);

        return curNode;

    }

遍历中序线索二叉树

public static void inOrderThreadTravel(TreeNode root) {

        while (root != null) {

                System.out.print(root.val + " ");

            //存在线索，root的直接后继就是root.rigth;

            if (root.isrightChild == 0) {

                root = root.right;

            }

            //不存在线索的时候一定存在孩子节点,则root的直接后继就是其右子树的中序第一个元素。

            else {

                root = root.right;

                while (root.left != null && root.isleftChild == 1) {

                    root = root.left;

                }

            }

        }

    }

二、表达式求值

有两个表达式

　　(4 + (13 / 5)) = 6　　 (a）

　　((2 + 1) * 3) = 9　　　　(b）

对应的两个表达式树（a）（b）

特点：数字都在叶子节点，运算符都在根节点。

    +                                   *

   / \                                 / \

  4   /                               +   3

     /  \                            / \

    13   5                          2   1

　　(a)　　　　　　　　　　　　　　　　　　　　(b)

来看一下表达式树的前中后三种顺序遍历结果；

中序：

　　4 + 13 / 5　　---　　(a)

　　2 + 1 * 3　　 ---　　(b)

可以看出，表达式树的中序遍历结果就是正常书写顺序，也是计算机可以直接求解的方式。

后序：

　　4 13 5 / +　　---　　(a)

　　2 1 + 3 * 　　---　　(b)

此时遍历结果非书写顺序，计算机也不能直接求解，非要按照这个顺序用计算机求解，怎么办？

解决方案：栈

　　按照遍历顺序对元素如下的操作:

　　　　1、如果元素是数字，入栈

　　　　2、如果元素是操作符不入栈，反而弹栈两个元素a，b；将a作为运算符的左操作数，b作为右操作数计算得到结果c；将结果c入栈。

　　　　3、重复上述操作，直到没有元素时，此时栈中一定只有一个元素，将其返回。

前序：

　　+ 4 / 13 5　　---　　（a）

　　* + 2 / 3 　　---　　　(b)

此时遍历结果非书写顺序，计算机也不能直接求解，非要按照这个顺序用计算机求解，怎么办？

解决方案：栈

　　与后序列操作类似，只不过按照遍历顺序的逆序，为什么是这样呢？

　　因为：栈的特点可以暂存之前遇到的信息，在后续操作中可以从栈中取出之前保存的信息；

　　　　　四则运算符都是二元运算符，因此一次计算的顺利完成需要3个信息，两个数字，一个运算符号；

　　　　因此遇到数字时候压栈，遇到操作符时候不压栈，然而弹出两个元素进行计算，这是合理的

　　　　　而观察表达式树我们发现，叶子节点全都是数字，跟节点全都是操作符号，在进一步可以这么想，父节点都是操作符，孩子节点都是数字（当然直观来看不是这样的，如表达式树（a）中根节点“+”的右孩子明明是“/”；其实在根节点“+”真正计算的时候，13 和 5的父节点“/”早就是新的数字了）；结合树的遍历特点，要么遍历完孩子节点才遍历根节点（后序），要么遍历完孩子节点才遍历根节点（前序），总之，孩子节点（数字）总在父节点（符号）的一侧。不管是先序还是后序，我们都统一为先处理孩子节点，再处理父节点，后序顺序中，孩子节点刚好在父节点之前，因此不做顺序调整，而先序遍历的时候，孩子节点均在父节点之后，因此需要逆序调整。

import java.util.Stack;

public class Solution {

    public int evalRPN(String[] tokens) {

        int res = 0;

        if (tokens == null || tokens.length == 0)

            return res;

        int len = tokens.length;

        Stack<Integer> stack = new Stack();

        int i = 0;

        for (; i < len; i++) {

            if (isNum(tokens[i]))

                stack.push(Integer.parseInt(tokens[i]));

            else {

                int a = stack.pop();

                int b = stack.pop();

                //除法有顺序要求哦

                stack.push(operator(b, a, tokens[i]));

            }

        }

        if (i == len)

            return stack.pop();

        return res;

    }

    private boolean isNum(String str) {

        boolean b = false;

        try {

            Integer.parseInt(str);

            b = true;

        } catch (Exception e) {

        }

        return b;

    }

    private int operator(int a, int b, String s) {

        int res = 0;

        switch (s) {

            case "+": {

                res = a + b;

                break;

            }

            case "-": {

                res = a - b;

                break;

            }

            case "*": {

                res = a * b;

                break;

            }

            case "/": {

                res = a / b;

                break;

            }

        }

        return res;

    }

}

巴特西

binary tree

一、中序线索化

二、表达式求值

最新文章

热门文章