====== Занятие II (весна 2014 г.) ======

Перед выполнением задания прочитайте информацию о {{:java:kormen_p.236-245.pdf|двоичных деревьях поиска}}.

===== Задание. Часть 1 =====

Приведем одну из возможных реализаций двоичного дерева поиска:

<code java>
public class MyBinarySearchTree{
	private static class Node{
		Integer data = null;
		Node parent = null;
		Node left = null;
		Node right = null;
		
		Node (int data){
			this.data = new Integer(data);
		}
	}
	
	private Node root;
	
	public void treeInsert(int data){
		Node y = null;
		Node x = root;
		
		while(x != null){
			y = x;
			if(data < x.data.intValue())
				x = x.left;
			else
				x = x.right;
		}
		
		Node z = new Node(data);
		z.parent = y;
		
		if(y == null)
			root = z;
		else{
			if(data < y.data.intValue())
				y.left = z;
			else
				y.right = z;
		}
	}
	
	private Node treeSearch(Node x, int data){
		if(x == null || data == x.data.intValue())
			return x;
		else if (data < x.data.intValue())
			return treeSearch(x.left, data);
		else
			return treeSearch(x.right, data);
	}
	
	public boolean treeSearch(int data){
		if (treeSearch(root, data) == null)
			return false;
		return true;
	}
}
</code>

Протестируем работу метода ''treeSearch'':

<code java>
int tmpInt;
Random random = new Random();

ArrayList<Integer> list = new ArrayList<Integer>();
MyBinarySearchTree tree = new MyBinarySearchTree();

for (int i = 0; i < 10; i++) {
	tmpInt = random.nextInt(20);
	tree.treeInsert(tmpInt);
	list.add(new Integer(tmpInt));
}

System.out.println(list.toString());
for (int i = 0; i < 20; i++) {
	System.out.println(i + ": " + (list.indexOf(i) >= 0) + " "
				+ tree.treeSearch(i));
}
</code>

Допишите методы ''inOrderTreeWalk'', ''treeMinimum'', ''treeMaximum'', ''treeSuccessor'', ''treePredecessor'', ''treeDelete'', описанные в {{:java:kormen_p.236-245.pdf|тексте}}.

===== Задание. Часть 2 =====

Преобразуйте написанный вами класс в класс, предназначенный для работы со строками. Получившийся класс должен выглядеть примерно так:

<code java>
public class ModifiedBinarySearchTree{
	private static class Node{
		String data = null;
		Node parent = null;
		Node left = null;
		Node right = null;
		
		Node (String data){
			this.data = data;
		}
	}
	
	private Node root;
	
	public void treeInsert(String data){
		Node y = null;
		Node x = root;
		
		while(x != null){
			y = x;
			if(data.compareTo(x.data) < 0)
				x = x.left;
			else
				x = x.right;
		}
		
		Node z = new Node(data);
		z.parent = y;
		
		if(y == null)
			root = z;
		else{
			if(data.compareTo(y.data) < 0)
				y.left = z;
			else
				y.right = z;
		}
	}

	/* Остальные методы (модифицированные соответствующим образом) */
}
</code>

Дан {{:java:elective:list_of_countries.txt|текстовый файл}}, содержащий английские названия стран мира. С помощью класса ''ModifiedBinarySearchTree'' составьте алфавитный список названий стран и запишите его в файл ''alphabetical_list_of_countries.txt''

Код для чтения из файла и записи в файл:

<code java>
/* чтение из файла list_of_countries.txt и сохранение списка стран в виде ArrayList */

BufferedReader inputFile = null;
try {
	inputFile = new BufferedReader(new FileReader("list_of_countries.txt"));
} catch (FileNotFoundException e) {
	e.printStackTrace();
}
		
String tmpString;
ArrayList<String> arr = new ArrayList<String>();
try {
	while ((tmpString = inputFile.readLine()) != null)
		arr.add(tmpString);
} catch (IOException e) {
	e.printStackTrace();
}


/* запись списка стран в файл alphabetical_list_of_countries.txt */		
		
BufferedWriter outputFile = null;
try {
	outputFile = new BufferedWriter(new FileWriter("alphabetical_list_of_countries.txt"));
} catch (IOException e) {
	e.printStackTrace();
}

try {
	for (int i = 0; i < arr.size(); i++){
		outputFile.write(arr.get(i));
		outputFile.newLine();
	}
} catch (IOException e) {
	e.printStackTrace();
} finally{
	try{
		if(outputFile != null){
			outputFile.flush();
			outputFile.close();
		}
	}
	catch(IOException e){
		e.printStackTrace();
	}
}
</code>



;#;
[[java:elective|Список занятий]]
;#;