Java实现表达式二叉树

时间:2021-05-20

什么是二叉树,这里不再介绍,可以自行百度:二叉树。在这里利用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了。这里使用的中序遍历,小伙伴们可以试试采用先序遍历、后序遍历是什么效果。至于遍历,我们后面再讲。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章