什么是二叉树，这里不再介绍，可以自行百度：二叉树。在这里利用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方法。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
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;
}
}
|
接着就是构建表达式二叉树了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
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了。这里使用的中序遍历，小伙伴们可以试试采用先序遍历、后序遍历是什么效果。至于遍历，我们后面再讲。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。