Java完成表達式二叉樹。本站提示廣大學習愛好者：（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<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了。這裡應用的中序遍歷，小同伴們可以嘗嘗采取先序遍歷、後序遍歷是甚麼後果。至於遍歷，我們前面再講。
以上就是本文的全體內容，願望對年夜家的進修有所贊助，也願望年夜家多多支撐。
