Java实现表达式二叉树

package tets0714;/** * 结点对象类 * @author yuxiu * */public class Node {  // 数据  private String data;  // 左子树  private Node lchild;  // 右子树  private Node rchild;  Node() {  }  Node(String data) {    this.data = data;  }  Node(String data, Node lchild, Node rchild) {    super();    this.data = data;    this.lchild = lchild;    this.rchild = rchild;  }  public String getData() {    return data;  }  public Node getLchild() {    return lchild;  }  public Node getRchild() {    return rchild;  }}

package tets0714;import java.util.ArrayList;/** * 表达式二叉树类 * @author yuxiu * */public class Formaluetree {  private String s="";  private Node root;   //根节点  /**   * 创建表达式二叉树   * @param str  表达式   */  public void creatTree(String str){    //声明一个数组列表，存放的操作符，加减乘除    ArrayList<String> operList = new ArrayList<String>();    //声明一个数组列表，存放节点的数据    ArrayList<Node> numList = new ArrayList<Node>();    //第一，辨析出操作符与数据，存放在相应的列表中    for(int i=0;i<str.length();i++){      char ch = str.charAt(i);     //取出字符串的各个字符      if(ch>='0'&&ch<='9'){        s+=ch;      }else{        numList.add(new Node(s));        s="";        operList.add(ch+"");              }          }    //把最后的数字加入到数字节点中    numList.add(new Node(s));        while(operList.size()>0){  //第三步，重复第二步，直到操作符取完为止      //第二，取出前两个数字和一个操作符，组成一个新的数字节点      Node left = numList.remove(0);      Node right = numList.remove(0);      String oper = operList.remove(0);            Node node = new Node(oper,left,right);      numList.add(0,node);    //将新生的节点作为第一个节点，同时以前index=0的节点变为index=1          }    //第四步，让根节点等于最后一个节点    root = numList.get(0);              }  /**   * 输出结点数据   */  public void output(){      output(root);   //从根节点开始遍历  }  /**   * 输出结点数据   * @param node   */  public void output(Node node){    if(node.getLchild()!=null){    //如果是叶子节点就会终止      output(node.getLchild());    }    System.out.print(node.getData());   //遍历包括先序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）    if(node.getRchild()!=null){      output(node.getRchild());    }      }    public static void main(String[] args) {    Formaluetree tree = new Formaluetree();    tree.creatTree("45+23*56/2-5");//创建表达式的二叉树    tree.output();//输出验证  }}