Java实现表达式二叉树

 更新时间:2016年08月09日 14:25:39   作者:my笔触   我要评论
这篇文章主要为大家详细介绍了如何利用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了。这里使用的中序遍历,小伙伴们可以试试采用先序遍历、后序遍历是什么效果。至于遍历,我们后面再讲。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持澳门金沙网上娱乐。

相关文章

  • java 算法之希尔排序详解及实现代码

    java 算法之希尔排序详解及实现代码

    这篇文章主要介绍了java 算法之希尔排序详解及实现代码的相关资料,需要的朋友可以参考下
    2017-03-03
  • futuretask源码分析(推荐)

    futuretask源码分析(推荐)

    这篇文章主要介绍了futuretask源码分析(推荐),小编觉得还是挺不错的,这里给大家分享下,供各位参考。
    2017-10-10
  • java.lang.NoSuchMethodException: com.sun.proxy.$Proxy58.list错误解决办法

    java.lang.NoSuchMethodException: com.sun.proxy.$Proxy58.list

    这篇文章主要介绍了java.lang.NoSuchMethodException: com.sun.proxy.$Proxy58.list错误解决办法的相关资料,需要的朋友可以参考下
    2016-12-12
  • Java三大特性-封装知识小结

    Java三大特性-封装知识小结

    所有的面向对象编程语言的思路都是差不多的,而这三大特性,则是思路中的支柱点,接下来我就重点讲解了一下java三大特性-封装,感兴趣的朋友跟随澳门金沙网上娱乐小编一起看看吧
    2018-03-03
  • Java并发编程Semaphore计数信号量详解

    Java并发编程Semaphore计数信号量详解

    这篇文章主要介绍了Java并发编程Semaphore计数信号量详解,具有一定参考价值,需要的朋友可以了解下。
    2017-10-10
  • Java工程师面试题一面二面整理

    Java工程师面试题一面二面整理

    在本篇文章里小编给大家整理的是关于Java 工程师面试题的相关知识点,有需要的可以参考下。
    2019-08-08
  • Java基于Tcp协议的socket编程实例

    Java基于Tcp协议的socket编程实例

    这篇文章主要介绍了Java基于Tcp协议的socket编程实例,较为详细的分析了socket编程客户端与服务器端的具体实现步骤与使用技巧,具有一定的参考借鉴价值,需要的朋友可以参考下
    2014-12-12
  • Java Web端程序实现文件下载的方法分享

    Java Web端程序实现文件下载的方法分享

    这篇文章主要介绍了Java Web端程序实现文件下载的方法分享,包括一个包含防盗链功能的专门针对图片下载的程序代码示例,需要的朋友可以参考下
    2016-05-05
  • Springcloud中的region和zone的使用实例

    Springcloud中的region和zone的使用实例

    这篇文章主要介绍了Springcloud中的region和zone的使用实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
    2019-10-10
  • 简述Java编程语言对象的容纳

    简述Java编程语言对象的容纳

    这篇文章主要对Java编程思想中对象的容纳进行了一个总体的介绍,具有一定的参考价值,需要的朋友可以了解下。
    2017-09-09

最新评论