Java實現(xiàn)表達式二叉樹

更新時間：2016年08月09日 14:25:39 作者：my筆觸

這篇文章主要為大家詳細介紹了如何利用Java實現(xiàn)表達式二叉樹，感興趣的小伙伴們可以參考一下

什么是二叉樹，這里不再介紹，可以自行百度：二叉樹。在這里利用java實現(xiàn)“表達式二叉樹”。

表達式二叉樹的定義

第一步先要搞懂表達式二叉樹是個什么東東？舉個栗子，表達式：(a+b×(c-d))-e/f。將數(shù)字放在葉子節(jié)點，將操作符放在分支節(jié)點，就構(gòu)成了一個二叉樹，由于存儲的是一個表達式，稱之為“表達式二叉樹”。

童靴們可能好奇這個到底是怎么構(gòu)建的？就拿45+23*56/2-5來說吧。首先取出第一個數(shù)字45放在葉子節(jié)點，遇到“+”后將其放到分支節(jié)點，

然后將“23”、“*”、“56”、“/”、“2”依次放入，

最后放入“-”、“5”,

大致就是這樣。（這些圖我自己畫的，比較丑，大家看看就好(⊙﹏⊙)）

表達式二叉樹的構(gòu)建步驟
1.創(chuàng)建節(jié)點對象；
2.辨析出操作符與數(shù)據(jù)，存放在相應的列表（隊列）中；
3.取出前兩個數(shù)字和一個操作符，組成一個新的數(shù)字節(jié)點；
4.重復第3步，直到操作符取完為止；
5.讓根節(jié)點等于最后一個節(jié)點。

表達式二叉樹的實現(xiàn)
首先構(gòu)建節(jié)點對象類，包括數(shù)據(jù)，左子樹，右子樹和幾個set、get方法。

package tets0714;
/**
 * 結(jié)點對象類
 * @author yuxiu
 *
 */
public class Node {
  // 數(shù)據(jù)
  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;
  }

}

接著就是構(gòu)建表達式二叉樹了。

package tets0714;

import java.util.ArrayList;

/**
 * 表達式二叉樹類
 * @author yuxiu
 *
 */
public class Formaluetree {
  private String s="";
  private Node root;   //根節(jié)點
  /**
   * 創(chuàng)建表達式二叉樹
   * @param str  表達式
   */
  public void creatTree(String str){
    //聲明一個數(shù)組列表，存放的操作符，加減乘除
    ArrayList<String> operList = new ArrayList<String>();
    //聲明一個數(shù)組列表，存放節(jié)點的數(shù)據(jù)
    ArrayList<Node> numList = new ArrayList<Node>();
    //第一，辨析出操作符與數(shù)據(jù)，存放在相應的列表中
    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+"");
        
      }
      
    }
    //把最后的數(shù)字加入到數(shù)字節(jié)點中
    numList.add(new Node(s));
    
    while(operList.size()>0){  //第三步，重復第二步，直到操作符取完為止
      //第二，取出前兩個數(shù)字和一個操作符，組成一個新的數(shù)字節(jié)點
      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é)點作為第一個節(jié)點，同時以前index=0的節(jié)點變?yōu)閕ndex=1
      
    }
    //第四步，讓根節(jié)點等于最后一個節(jié)點
    root = numList.get(0);
            
  }
  /**
   * 輸出結(jié)點數(shù)據(jù)
   */
  public void output(){
      output(root);   //從根節(jié)點開始遍歷
  }
  /**
   * 輸出結(jié)點數(shù)據(jù)
   * @param node
   */
  public void output(Node node){
    if(node.getLchild()!=null){    //如果是葉子節(jié)點就會終止
      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)建表達式的二叉樹
    tree.output();//輸出驗證

  }

}

最后在控制臺可以輸出“45+23*56/2-5”,OK了。這里使用的中序遍歷，小伙伴們可以試試采用先序遍歷、后序遍歷是什么效果。至于遍歷，我們后面再講。

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: