什么是二叉樹(shù)，這里不再介紹，可以自行百度：二叉樹(shù)。在這里利用java實(shí)現(xiàn)“表達(dá)式二叉樹(shù)”。
表達(dá)式二叉樹(shù)的定義
第一步先要搞懂表達(dá)式二叉樹(shù)是個(gè)什么東東？舉個(gè)栗子，表達(dá)式：(a+b×(c-d))-e/f。將數(shù)字放在葉子節(jié)點(diǎn)，將操作符放在分支節(jié)點(diǎn)，就構(gòu)成了一個(gè)二叉樹(shù)，由于存儲(chǔ)的是一個(gè)表達(dá)式，稱之為“表達(dá)式二叉樹(shù)”。
童靴們可能好奇這個(gè)到底是怎么構(gòu)建的？就拿45+23*56/2-5來(lái)說(shuō)吧。首先取出第一個(gè)數(shù)字45放在葉子節(jié)點(diǎn)，遇到“+”后將其放到分支節(jié)點(diǎn)，
然后將“23”、“*”、“56”、“/”、“2”依次放入，
最后放入“-”、“5”,
大致就是這樣。（這些圖我自己畫(huà)的，比較丑，大家看看就好(⊙﹏⊙)）
表達(dá)式二叉樹(shù)的構(gòu)建步驟
1.創(chuàng)建節(jié)點(diǎn)對(duì)象；
2.辨析出操作符與數(shù)據(jù)，存放在相應(yīng)的列表（隊(duì)列）中；
3.取出前兩個(gè)數(shù)字和一個(gè)操作符，組成一個(gè)新的數(shù)字節(jié)點(diǎn)；
4.重復(fù)第3步，直到操作符取完為止；
5.讓根節(jié)點(diǎn)等于最后一個(gè)節(jié)點(diǎn)。
表達(dá)式二叉樹(shù)的實(shí)現(xiàn)
首先構(gòu)建節(jié)點(diǎn)對(duì)象類，包括數(shù)據(jù)，左子樹(shù)，右子樹(shù)和幾個(gè)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;/** * 結(jié)點(diǎn)對(duì)象類 * @author yuxiu * */public class Node { // 數(shù)據(jù) private String data; // 左子樹(shù) private Node lchild; // 右子樹(shù) 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; }} |
接著就是構(gòu)建表達(dá)式二叉樹(shù)了。
|
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;/** * 表達(dá)式二叉樹(shù)類 * @author yuxiu * */public class Formaluetree { private String s=""; private Node root; //根節(jié)點(diǎn) /** * 創(chuàng)建表達(dá)式二叉樹(shù) * @param str 表達(dá)式 */ public void creatTree(String str){ //聲明一個(gè)數(shù)組列表，存放的操作符，加減乘除 ArrayList<String> operList = new ArrayList<String>(); //聲明一個(gè)數(shù)組列表，存放節(jié)點(diǎn)的數(shù)據(jù) ArrayList<Node> numList = new ArrayList<Node>(); //第一，辨析出操作符與數(shù)據(jù)，存放在相應(yīng)的列表中 for(int i=0;i<str.length();i++){ char ch = str.charAt(i); //取出字符串的各個(gè)字符 if(ch>='0'&&ch<='9'){ s+=ch; }else{ numList.add(new Node(s)); s=""; operList.add(ch+""); } } //把最后的數(shù)字加入到數(shù)字節(jié)點(diǎn)中 numList.add(new Node(s)); while(operList.size()>0){ //第三步，重復(fù)第二步，直到操作符取完為止 //第二，取出前兩個(gè)數(shù)字和一個(gè)操作符，組成一個(gè)新的數(shù)字節(jié)點(diǎn) 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); //將新生的節(jié)點(diǎn)作為第一個(gè)節(jié)點(diǎn)，同時(shí)以前index=0的節(jié)點(diǎn)變?yōu)閕ndex=1 } //第四步，讓根節(jié)點(diǎn)等于最后一個(gè)節(jié)點(diǎn) root = numList.get(0); } /** * 輸出結(jié)點(diǎn)數(shù)據(jù) */ public void output(){ output(root); //從根節(jié)點(diǎn)開(kāi)始遍歷 } /** * 輸出結(jié)點(diǎn)數(shù)據(jù) * @param node */ public void output(Node node){ if(node.getLchild()!=null){ //如果是葉子節(jié)點(diǎn)就會(huì)終止 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");//創(chuàng)建表達(dá)式的二叉樹(shù) tree.output();//輸出驗(yàn)證 }} |
最后在控制臺(tái)可以輸出“45+23*56/2-5”,OK了。這里使用的中序遍歷，小伙伴們可以試試采用先序遍歷、后序遍歷是什么效果。至于遍歷，我們后面再講。
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
