package Bbstree;



import java.io.*;

import java.util.HashMap;

import java.util.Map;

public class Tree {



	TreeNode trnode[];

	public static void main(String[] args) {

		// TODO Auto-generated method stub

		String allword=null,buffword; //保存单个单词

		String sentense[]=null;//读取整个字符串，tree用来实现二叉树

		int length,a,dep=0;

		TreeNode tnodebuf,thead;

		try

		{

			String encoding="UTF-8";

			File file = new File("D://test_2.txt");    //file 指向目录中的文件

			if(file.isFile() && file.exists())

			{ //判断文件是否存在

		           InputStreamReader read = new InputStreamReader(new FileInputStream(file),encoding);//考虑到汉子编码格式		          

		           BufferedReader br =new BufferedReader(read);		       

		           allword=br.readLine();    //读取文件中的一行数据

		           length=allword.length();    //获得字符串s1的长度并赋值给length_1	

		           read.close();

			}

			

			else{

				   System.out.println("找不到指定的文件");

				}

		}

		catch(Exception e){

			System.out.println("读取文件内容出错");

			e.printStackTrace();

		}

		if(allword!=null)

		{

			sentense=allword.split(" ");

		}

		TreeNode trnode[]=new TreeNode[sentense.length];

		for(int i=0;i<sentense.length;i++)

		{

			trnode[i]=new TreeNode(sentense[i]);

			

		}

		for(int i=0;i<sentense.length;i++)

			for(int j=0;j<sentense.length-i-1;j++)

			{

				if(trnode[j].length>trnode[j+1].length)

				{

					tnodebuf=new TreeNode(sentense[i]);

					tnodebuf.NodeCopy(trnode[j]);

					trnode[j].NodeCopy(trnode[j+1]);

					trnode[j+1].NodeCopy(tnodebuf);

				}

			}

		thead=new TreeNode();

		thead.pos=(0+sentense.length)/2;

		int depth=Creatbtree(trnode,0,sentense.length-1,0,sentense.length,dep);

		TreeNode netree[]=new TreeNode[sentense.length];

		for(int i=0;i<sentense.length;i++)

		{

			netree[i]=new TreeNode();	

		}

		int nelength=FindAcctimes(trnode,netree,sentense.length);

		wordsort(netree,nelength-1);

		fiwrite(netree,depth,nelength-1);

	}

//trnode保存二叉树，netree保存出现次数，以及去除了相同的字符串

	private static int Creatbtree(TreeNode trnode[],int pos1,int pos2,int i,int length,int dep)

	{	//递归简历平衡排序二叉树	

		int dep1,dep2;

			dep++;

			

			if(pos1<=pos2)

			{

				if(pos1==pos2)

				{

					trnode[(pos1+pos2)/2].lchild=-1;

					trnode[(pos1+pos2)/2].rchild=-1;

					trnode[(pos1+pos2)/2].pos=dep;

				}

				else if((pos1+pos2)/2==pos1)

				{

					trnode[(pos1+pos2)/2].lchild=-1;

					trnode[(pos1+pos2)/2].rchild=(pos2+(pos1+pos2)/2+1)/2;

					trnode[(pos1+pos2)/2].pos=dep;

				}

				else

				{

					trnode[(pos1+pos2)/2].lchild=(pos1+(pos1+pos2)/2-1)/2;

					trnode[(pos1+pos2)/2].rchild=(pos2+(pos1+pos2)/2+1)/2;

					trnode[(pos1+pos2)/2].pos=dep;

				}

				

				dep1=Creatbtree(trnode,pos1,(pos1+pos2)/2-1,i,length,dep);

				dep2=Creatbtree(trnode,(pos1+pos2)/2+1,pos2,i,length,dep);

				dep=((dep1>dep2)?dep1:dep2)>dep?((dep1>dep2)?dep1:dep2):dep;//得出深度

				

			

			}

			return dep;

	}

	private static int FindAcctimes(TreeNode trnode[],TreeNode treenode[],int length)

	{

		//找出每个单词出现次数并去除同样字符串

		

		int tnum=0,relength=length;

		Map<String, String> existMap = new HashMap<String, String>();	

		for(int i=0;i<length;i++)//将数据存入一个数组，有相同字符串ACCTIMES就+1

		{

			

			if(existMap.get(trnode[i].treenode)==null)//字符串不存在

			 {

				 existMap.put(trnode[i].treenode,Integer.toString(trnode[i].acctimes));

				 treenode[tnum].NodeCopy(trnode[i]);

					tnum++;

			 }

			else if(existMap.get(trnode[i].treenode)!=null)//字符串已存在

			{

				existMap.put(trnode[i].treenode,Integer.toString(trnode[i].acctimes+1));

				relength--;

			}

		}

		for(int i=0;i<length;i++)

		{//存入出现次数

			try

				{

				treenode[i].acctimes=Integer.valueOf(existMap.get(treenode[i].treenode)).intValue();

				}

			catch(Exception e){}

		}

		return length;

		 

	}

	private static void fiwrite(TreeNode trnode[],int dep,int length)

	{

		try

		{

			File file = new File("D://test_1.txt");	

			FileWriter fw_clear = new FileWriter(file);

			BufferedWriter bw_clear = new BufferedWriter(fw_clear);

			bw_clear.write("");

			bw_clear.close();

		}

		catch(Exception e){}

		try

		{

			File file = new File("D://test_1.txt");							

			FileWriter fw = new FileWriter(file,true);

			BufferedWriter bw = new BufferedWriter(fw);

			bw.write("深度为："+dep);