什麼是二叉樹，這裡不再介紹，可以自行百度：二叉樹。在這裡利用java實現“表達式二叉樹”。
表達式二叉樹的定義
第一步先要搞懂表達式二叉樹是個什麼東東？舉個栗子，表達式：(a+b×(cd))-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了。這裡使用的中序遍歷，小伙伴們可以試試採用先序遍歷、後序遍歷是什麼效果。至於遍歷，我們後面再講。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。