之前了解过二叉树但是一直不怎么理解，前天接到一个任务，给我一个字符串15+(2+(3+6)*3)，在控制台打印成一颗二叉树。网上有好些例子，但有些是C语言的，有些只有一些片段，做了两天终于弄出来拉。 先写要给工具类
package com.jsm.test; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; import javax.rmi.CORBA.Tie; import com.jsm.test.OrderTree.BTree; import com.jsm.test.OrderTree.Point; public class Util { public static Node findIndexAndValue(String str){ //String src="100+(2+(3+6)*3)"; if(str.startsWith("(")&&str.endsWith(")")){ str=str.substring(1,str.length()-1); } char [] chars=null; Node node=new Node(); //如果包含括号 String value=""; int value_index=0; String str_left2=""; String str_right2="";// /// 100+(2+(3+6)*3) chars=str.toCharArray(); if(containsParentheses(str)){ //如果（前面有 *好 则他们也是一起的 int index_s=str.indexOf("("); if(index_s>0){ if(chars[index_s-1]=='*'){ index_s--; } } int index_e=str.lastIndexOf(")"); if(index_e<(str.length()-1)){ //如果 if(chars[index_e+1]=='*'){ //如果括号外面没有+ 则*不能去掉 if(isAddInnerStr(str,index_s,index_e)){ index_e++; } } }//2+(3+6)*3 String str_inPa=str.substring(index_s,index_e+1); String str_flag=getLog(str_inPa.length()); String str_left=str.replace(str_inPa, str_flag); if(str_left.indexOf("+")>0){ value="+"; value_index=str_left.indexOf("+"); str_left2=str.substring(0, value_index); str_right2=str.substring(value_index+1); /*node.value="+"; node.value_index=str_left.indexOf("+"); return node;*/ } if(str_left.indexOf("*")>0){ value="*"; value_index=str_left.indexOf("*"); str_left2=str.substring(0, value_index); str_right2=str.substring(value_index+1); // return node; } }else {//如果不包含括号 if(str.contains("*")&&str.contains("+")){ value="+"; value_index=str.indexOf("+"); str_left2=str.substring(0, value_index); str_right2=str.substring(value_index+1); //return node; } if(str.contains("*")&&!str.contains("+")){ value="*"; value_index=str.indexOf("*"); str_left2=str.substring(0, value_index); str_right2=str.substring(value_index+1); //return node; } if(!str.contains("*")&&str.contains("+")){ value="+"; value_index=str.indexOf("+"); str_left2=str.substring(0, value_index); str_right2=str.substring(value_index+1); //return node; } if(!str.contains("*")&&!str.contains("+")){ value=str; value_index=0; str_left2=null; str_right2=null; } } node.value=value; node.value_index=value_index; node.str_left=str_left2; node.str_right=str_right2; return node; } private static boolean isAddInnerStr(String str, int indexS, int indexE) { char [] arr=str.toCharArray(); for (int i = 0; i < indexS; i++) { if(arr[i]=='+'){ return true; } } for(int i = indexE; i <arr.length; i++){ if(arr[i]=='+'){ return true; } } return false; } public static String getLog(int n){ String str=""; for (int i = 0; i < n; i++) { str=str+"-"; } return str; } /* * 此方法用于找出str中的顶节点 */ public static String findOperatorOfNode(String str){ Node node=new Node(); //如果包含括号 if(containsParentheses(str)){ int index_s=str.indexOf("("); int index_e=str.lastIndexOf(")"); String str_inPa=str.substring(index_s,index_e+1); String str_left=str.replace(str_inPa, ""); if(str_left.indexOf("+")>0){ return "+"; } if(str_left.indexOf("*")>0){ return "*"; } }else {//如果不包含括号 if(str.contains("*")&&str.contains("+")){ } } return null; } public static boolean containsParentheses(String str){ if(str.contains("(")||str.contains(")")){ return true; }else { return false; } } public static boolean containsOperator (String str){ if(str.contains("*")||str.contains("+")){ return true; }else { return false; } } /** * @param args */ public static void main(String[] args) { System.out.println("ab\ncd"); } // public static void fun(){ String[] str={"+", "100", "+", null, null, "2","*", null, null, null, null, null, null, "+", "3", null, null, null, null, null, null, null, null, null, null, null, null, "3", "6"}; int i=0; int co=str.length/2; print(co); System.out.println(str[0]); while(i<str.length){ if(i==0){ }else{ } i++; } } private static void print(int co) { for (int i = 0; i < co; i++) { System.out.print("--"); } } //static String left_str; // static String right_str; //static Node last_node; // static int count=0; // public static int index=0; //static String [] arr=null; // static Map<Integer,Node> map =new HashMap<Integer,Node>(); public static void btree2array (int index,String str,Map<Integer,Node> map) { if(str==null){ return; } Node node =Util.findIndexAndValue(str); map.put(index, node); if(node.value_index==0){//this node has no sub-node return; } btree2array( index * 2 + 1,map.get(Integer.valueOf(index)).str_left,map); btree2array( index * 2 + 2,map.get(Integer.valueOf(index)).str_right,map); } /* *get the max key of a map who's key is countable; */ public static int getMaxMapKey(Map<Integer,String> map){ List<Integer> list2 =new ArrayList<Integer>(); for (Integer integer : map.keySet()) { list2.add(integer); } return Collections.max(list2); } public static String[] putMapValueToStrArray(int maxIndex, Map<Integer, String> map2) { String [] arr_result=new String [maxIndex+1]; for (int i = 0; i < arr_result.length; i++) { if(map2.get(Integer.valueOf(i))==null){ arr_result[i]=" "; }else{ arr_result[i]=map2.get(Integer.valueOf(i)); } } return arr_result; } public static Map<Integer, String> getNodeMapData(Map<Integer, Node> map) { Map<Integer,String> map_result=new HashMap<Integer, String>(); for(Integer s:map.keySet()){ map_result.put(s, map.get(s).value);// only the value is what we need so get it and put it to map2 } return map_result; } /* * print binary tree */ public static void printArrToBinaryTree(String [] arr){ String[] arr_userful=arr; for (int i = 0; i < arr_userful.length; i++) { arr_userful[i]=arr_userful[i].trim(); if(arr_userful[i].trim().length()==0||arr_userful[i].equals(" ")){ arr_userful[i]=" "; } } BTree root= createTree(arr_userful,0); List<Point> points = new ArrayList<Point>(); // the height of binary tree int floors = totalfloor(root); //put the binary tree data to points printTree(root, points, 0, -1,floors); // sort the points Collections.sort(points); //print out the binary tree data according to row and col int row = 0; StringBuilder sb = new StringBuilder(); int totalLength = 1*(squat(2, floors)-1); for(Point p : points){ if(row == p.row){ sb.append(printTimes(" ",1*p.col-sb.length())); sb.append(printWidth(""+p.data, 1)); }else{ if(sb.length()< totalLength){ sb.append(printTimes(" ", totalLength-sb.length())); } System.out.println(sb.toString()); sb = new StringBuilder(); row++; sb.append(printTimes(" ",1*p.col-sb.length())); sb.append(printWidth(""+p.data, 1)); } } if(sb.length()< totalLength){ sb.append(printTimes(" ", totalLength-sb.length())); } System.out.println(sb.toString()); } //create an Object to store Binary structure data private static BTree createTree(String[] arr, int i) { if(arr[i].trim().length()==0){ return null; } BTree root = new BTree(arr[i]); int lnode = 2*i + 1;//the left' index in arr int rnode = 2*i + 2;//the right' index in arr if ( lnode > arr.length -1) { root.left = null; }else{ root.left = createTree(arr, lnode); } if (rnode > arr.length-1) { root.right =null; }else{ root.right = createTree(arr, rnode); } return root; } static int totalfloor(BTree root){ if(root == null)return 0; return internalLoop(root, 0); } static int internalLoop(BTree root,int floor){ if(root != null){ floor++; int left = internalLoop(root.left, floor); int right = internalLoop(root.right, floor); return Math.max(left, right); } else return floor; } static String printTimes(String s,int time){ StringBuilder sb = new StringBuilder(); for(int i=0;i<time;i++){ sb.append(s); } return sb.toString(); } static String printWidth(String s ,int width){ if(s == null ){ return printTimes(" ", width); }else{ if(s.length() < width){ return new StringBuilder(s).append(printTimes("@", width-s.length())).toString(); }else{ // return s.substring(0,width); return s.substring(0); } } } //implemtns the Comparable interface for sort List of point static class Point implements Comparable<Point>{ public Point(int row,int col,String data){ this.row = row; this.col = col; this.data = data; } int row = 0; int col = 0; String data =""; @Override public int compareTo(Point o) { if(this.row == o.row){ if(col == o.col) return 0; else if(col < o.col){ return -1; }else{ return 1; } }else if(row < o.row){ return -1; }else{ return 1; } } } static void printTree(BTree root,List<Point> points,int row,int col,int floors){ if(root != null){ int inter = squat(2, floors-1)-1; if(col == -1){ col = inter; } points.add(new Point(row, col, root.data)); printTree(root.left,points,row+1, col - ((inter-1)/2)-1,floors -1); printTree(root.right,points,row+1,col + (inter-1)/2+1 ,floors -1); } } static int squat(int s,int b){ if(b == 0) return 1; int result = 1; for(int i=0;i<b ;i++){ result *=s; } return result; } static void preOrder(BTree root){ if(root == null) { return ; } System.out.print("-"+root.data); preOrder(root.left); preOrder(root.right); } static void midOrder(BTree root){ if(root == null) return ; midOrder(root.left); System.out.print("-"+root.data); midOrder(root.right); } static void lastOrder(BTree root){ if(root == null) return ; lastOrder(root.left); lastOrder(root.right); System.out.print("-"+root.data); } //declare a Object to store binary tree static class BTree{ BTree left; BTree right; String data; public BTree() { super(); } public BTree(String data) { super(); this.data = data; this.right=null; this.left=null; } } } 再定义一个节点类package com.jsm.test; public class Node {
public String value; public Node node_right; public Node node_left; public String str_right; public String str_left; public int value_index; public int arr_index; @Override public String toString() { return "Node [node_left=" + node_left + ", node_right=" + node_right + ", str_left=" + str_left + ", str_right=" + str_right + ", value=" + value + ", value_index=" + value_index + "]"; }} 最后是主文件，含有main方法的：
package com.jsm.test; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Scanner; import java.util.Set; public class TransStrToBinaryTree { static Map<Integer,Node> map =new HashMap<Integer,Node>(); public static void main(String[] args) { //test string String src="5+(2+(3+6)*3)"; String srcStr="15+(2+(3+6)*3)"; try { //resolve the srcStr to map Util.btree2array(0, srcStr, map); } catch (Exception ex) { System.out.println("some syntactic error in this string lead to program stop\nplease check your string"); ex.printStackTrace(); } Map<Integer,String> map2 =Util.getNodeMapData(map); //get the max value of map2 to declare a array int arr_length=Util.getMaxMapKey(map2); //declare a array to store binary tree data String [] arr_result= Util.putMapValueToStrArray(arr_length,map2); //print the binary tree Util.printArrToBinaryTree(arr_result); } }