什么是二叉树，这里不再介绍，可以自行百度：二叉树。在这里利用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了。这里使用的中序遍历，小伙伴们可以试试采用先序遍历、后序遍历是什么效果。至于遍历，我们后面再讲。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持移动技术网。
如对本文有疑问， 点击进行留言回复！！
现在微服务这么火，你还不了解吗？阿里P8推荐的微服务学习指南
论文笔记：SlowFast Networks for Video Recognition
网友评论