请教二叉树的具体应用?
在JAVA程序设计中,什么情况下会用到二叉树,如果有这方面实际开发经验的朋友,请指点一下。
在JAVA程序设计中,什么情况下会用到二叉树,如果有这方面实际开发经验的朋友,请指点一下。
解决方案 »
- java 题目 完成两个数组内容的交换 并输出
- 关于JAVA异常继承的问题。。
- java中socket服务端同时对连接中客户端下发数据方法
- 一个菜鸟关于String的问题!!!
- 菜鸟跪求!! 有关JAVA中main( String[] args)函数和c语言中main(args[])参数的区别??
- 求高手指教:怎么样利用JMF同时使用两个USB摄像头进行视频采集?
- 关于包的引用,以及方法的重构
- 对Java有好多困惑,哪里有好的Java群,大家推荐几个。。。
- 如何用javamail实现自动发送邮件?
- 在Java中有没有类似VB的MDI窗体?即:只有一个父窗体,里面可以容纳许多子窗体。
- 请教一下关于JAVA编写的日历,用控制台的形式显示。
- 初遇JAVA泛型的一个问题。请帮忙。
binary search tree
但也有一些其它用途,比如偶写的一个算术表达式解析器:class Node<E>{ //o:object
public E o;
//p:priority
public int p;
//l:left,r:right
public Node l,r;
public Node(E o){
this.o = o;
}
}class Stack<E>{ private Node cur;
private int size = 0;
public void push(E o){
Node<E> n = new Node<E>(o);
if(cur!=null){
cur.r = n;
n.l = cur;
}
cur = n;
size++;
}
public E pop(){
if(size==0)
return null;
try{
size--;
return (E)cur.o;
}finally{
cur = cur.l;
if(cur!=null)
cur.r = null;
}
}
public int size(){
return size;
}
}class Tree{ private Node<String> cur,root,start;
private Stack<Node> nodes;
private String s[],result;
public void insert(String s[]){
if(s.length<=2)
return;
int x = Parser.X_INIT;
nodes = new Stack<Node>();
cur = new Node<String>(Parser.operators[0]);
cur.l = new Node<String>("0");
cur.p = Parser.p(Parser.operators[0])+x;
root = cur;
start = root;
for(int i=0;i<s.length;i++){ Node<String> n = new Node<String>(s[i]);
x += s[i].equals("(")?Parser.X_STEP:s[i].equals(")")?-Parser.X_STEP:0;
if(Parser.isOperator(s[i])){
n.p = Parser.p(s[i])+x;
while(cur.p>n.p)
rollBack();
if(cur.p<n.p){
nodes.push(cur);
n.l = cur.r;
cur.r = n;
}else if(cur.p==n.p){
n.l = cur;
if(nodes.size()==0)
root = n;
}
cur = n;
}else if(java.util.regex.Pattern.matches("(\\d+\\.\\d+)|\\d+",s[i])){
cur.r = n;
}
}
while(nodes.size()>0)
rollBack();
if(start==root){
root = start.r;
}else{
cur = root;
while(cur.l.l.l!=null)
cur = cur.l;
cur.l = cur.l.r;
}
}
private void rollBack(){
Node<String> temp = nodes.pop();
temp.r = cur;
cur = temp;
if(nodes.size()==0)
root = temp;
}
public String prefix(){
result = "";
prefixIterate(root);
return result;
}
private void prefixIterate(Node n){
if(n==null)
return;
result += n.o+" ";
prefixIterate(n.l);
prefixIterate(n.r);
} public String postfix(){
result = "";
postfixIterate(root);
return result;
}
private void postfixIterate(Node n){
if(n==null)
return;
postfixIterate(n.l);
postfixIterate(n.r);
result += n.o+" ";
}
}class Calculator{
public static double calculateInPostfix(String s[]){
Stack<Double> num = new Stack<Double>();
double result = 0;
for(int i=0;i<s.length;i++)
if(Parser.isOperator(s[i])){
double d1 = num.pop();
double d2 = num.pop();
result = calculate(d1,d2,s[i]);
num.push(result);
}else{
num.push(Double.parseDouble(s[i]));
}
return num.pop();
}
public static double calculate(double d1,double d2,String operator){
double result = 0;
if(operator.equals("+")){
result = d2+d1;
}else if(operator.equals("-")){
result = d2-d1;
}else if(operator.equals("*")){
result = d2*d1;
}else if(operator.equals("/")){
result = d2/d1;
}else if(operator.equals("^")){
result = Math.pow(d2,d1);
}else if(operator.equals("#")){
result = Math.pow(d2,1/d1);
}
return result;
}
}public class Parser{
public static final String operators[] = new String[]{"+","-","*","/","^","#"};
public static final String operators2[] = new String[]{"\\+","\\-","\\*","\\/","\\^","\\#"};
public static final int priorities[] = new int[]{2,2,4,4,6,6};
public static int X_INIT = 1,X_STEP = 10;
private String s[];
private Tree t = new Tree();
public Parser(String s){
this.s = parseSource(s);
t.insert(this.s);
}
public static boolean isOperator(String s){
for(int i=0;i<operators.length;i++)
if(operators[i].equals(s))
return true;
return false;
}
public static int p(String s){
for(int i=0;i<operators.length;i++)
if(operators[i].equals(s))
return priorities[i];
return -1;
}
private String[] parseSource(String s){
String rule = "[^\\d|\\(|\\)|\\.";
for(int i=0;i<operators2.length;i++)
rule += "|"+operators2[i];
rule += "]";
s = s.trim().replaceAll(rule,"");
for(int i=0;i<operators2.length;i++)
s = s.replaceAll(operators2[i]," "+operators2[i]+" ");
s = s.replaceAll("\\(","( ").replaceAll("\\)"," )");
return s.split(" +");
} public double calculate(){
return Calculator.calculateInPostfix(t.postfix().split(" "));
}
public String converToInfix(){
String result = "";
for(int i=0;i<s.length;i++)
result += s[i]+" ";
return result;
}
public String converToPrefix(){
return t.prefix();
}
public String converToPostfix(){
return t.postfix();
}
public static void main(String args[]){
Parser p = new Parser(args[0]);
System.out.println("中缀表达式:"+p.converToInfix());
System.out.println("前缀表达式:"+p.converToPrefix());
System.out.println("后缀表达式:"+p.converToPostfix());
System.out.println("计算结果: "+p.calculate());
}
}