这里有新鲜出炉的Java设计模式,程序狗速度看过来!
java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台(即JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。
这篇文章主要为大家详细介绍了如何利用Java实现表达式二叉树,感兴趣的小伙伴们可以参考一下
什么是二叉树,这里不再介绍,可以自行百度:二叉树。在这里利用java实现“表达式二叉树”。
表达式二叉树的定义
第一步先要搞懂表达式二叉树是个什么东东?举个栗子,表达式:(a+b×(c-d))-e/f。将数字放在叶子节点,将操作符放在分支节点,就构成了一个二叉树,由于存储的是一个表达式,称之为“表达式二叉树”。
童靴们可能好奇这个到底是怎么构建的?就拿45+23*56/2-5来说吧。首先取出第一个数字45放在叶子节点,遇到“+”后将其放到分支节点,
然后将“23”、“*”、“56”、“/”、“2”依次放入,
最后放入“-”、“5”,
大致就是这样。(这些图我自己画的,比较丑,大家看看就好(⊙﹏⊙))
表达式二叉树的构建步骤
1.创建节点对象;
2.辨析出操作符与数据,存放在相应的列表(队列)中;
3.取出前两个数字和一个操作符,组成一个新的数字节点;
4.重复第3步,直到操作符取完为止;
5.让根节点等于最后一个节点。
表达式二叉树的实现
首先构建节点对象类,包括数据,左子树,右子树和几个set、get方法。
- 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(); //输出验证
- }
- }
最后在控制台可以输出“45+23*56/2-5”,OK了。这里使用的中序遍历,小伙伴们可以试试采用先序遍历、后序遍历是什么效果。至于遍历,我们后面再讲。
来源: http://www.phperz.com/article/17/1121/360264.html