Java实现表达式二叉树

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 operList = new ArrayList();

//声明一个数组列表，存放节点的数据

ArrayList numList = new ArrayList();

//第一，辨析出操作符与数据，存放在相应的列表中

for(int i=0;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())http://; //遍历包括先序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）

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://

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())http://; //遍历包括先序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）

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://

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。