Міністерство науки і освіти України
Вінницький національний технічний університет
Кафедра програмного забезпечення
Лабораторна робота № 6
з дисципліни «Алгоритми та структури даних»
Бінарні дерева
Група 3ПІ-18б
Виконав: Пацалюк В. С.
Перевірив: Коваленко О.О.
Вінниця 2019
Мета: Набуття практичних вмінь та навичок опрацювання нелінійних структур даних, представлених у вигляді бінарних дерев.
Завдання:
1.Написати програму, в якій дані вашого варіанту структури записуються в дерева (використати три поля для вузла –текстове дане та два числові. Наприклад, вузол дерева містить таку корисну інформацію: прізвище студента, рік народження, оцінка).Ввести з клавіатури декілька"студентів" у двійкове дерево, організоване за порядком текстового поля. Роздрукувати отримане дерево.
2.Знайти середню значення однго з числових полів, зчитуючи дані з дерева.
3.Дописати функцію видалення з пам’яті всього дерева
Вказівка: рекурсивна функція, яка
1) видаляє ліве піддерево, іліву гілку занулює;
2) видаляє праве піддерево, і правугілку занулює;
3) видаляє сам вузол, потім зануливши вказівник на нього Наприкінці програми видалити з пам’яті дерево.
4."Пересипати" дані з першого дерева у друге дерево того ж типу, тільки організованого за першим числовим ключем (напр., роком народження) та роздрукувати його (а перше дерево стерти).
Лістинг програми:
Лістинг файлу Main.java
package com.company;
public class Main {
public static void main(String... args) {
BinaryTree binaryTree = new BinaryTree();
binaryTree.add(new Student("Ваня", 2, 2));
binaryTree.add(new Student("Вова", 2, 5));
binaryTree.add(new Student("Маша", 3, 3));
binaryTree.add(new Student("Маша", 3, 2));
binaryTree.add(new Student("Миша",2,3));
binaryTree.traverseInOrder(binaryTree.root);
binaryTree.showTree();
BinaryTree binaryTree1 = new BinaryTree();
binaryTree1.showTree();
}
}
Лістинг файлу BinaryTree.java
package com.company;
public class BinaryTree {
private int allMarks;
private int allStudents;
Node root;
private Node addRecursive(Node current, Student student) {
if (current == null) {
return new Node(student);
}
int value = student.compareTo(current.student);
if (value < 0) {
current.left = addRecursive(current.left, student);
} else if (value > 0) {
current.right = addRecursive(current.right, student);
} else {
return current;
}
return current;
}
private Node addRecursiveByMark(Node current, Student student) {
if (current == null) {
return new Node(student);
}
int value = student.compareMarkTo(current.student);
if (value < 0) {
current.left = addRecursive(current.left, student);
} else if (value > 0) {
current.right = addRecursive(current.right, student);
} else {
return current;
}
return current;
}
void add(Student student) {
root = addRecursive(root, student);
allMarks += student.getMark();
allStudents++;
}
void addByMark(Student student) {
root = addRecursiveByMark(root, student);
}
void traverseInOrder(Node node) {
if (node != null) {
System.out.println(node.student.toString());
traverseInOrder(node.left);
traverseInOrder(node.right);
}
}
private void showLeftTree(Node node) {
if (node != null) {
System.out.println("Left->" + node.student.toString());
showLeftTree(node.left);
}
}
private void showRightTree(Node node) {
if (node != null) {
System.out.println("Right->" + node.student.toString());
showRightTree(node.right);
}
}
private void showRoot(Node node) {
if (node != null) {
System.out.println("Root->" + node.student.toString());
} else {
System.out.println("No root");
}
}
void showTree() {
showRoot(root);
try {
showLeftTree(root.left);
} catch (NullPointerException e) {
System.out.println("No left tree");
}
try {
showRightTree(root.right);
} catch (NullPointerException e) {
System.out.println("No right tree");
}
}
int findMiddleMark() {
return allMarks / allStudents;
}
private void deleteLeftRecursive(Node node) {
if (node != null) {
System.out.println("Delete->" + node.student.toString());
node.student = null;
deleteLeftRecursive(node.left);
}
}
private void deleteRightRecursive(Node node) {
if (node != null) {
System.out.println("Delete->" + node.student.toString());
node.student = null;
deleteRightRecursive(node.left);
}
}
private void deleteRoot(Node node) {
System.out.println("Delete->" + node.student.toString());
node.student = null;
root = null;
}
void deleteTree() {
deleteLeftRecursive(root.left);
deleteRightRecursive(root.right);
deleteRoot(root);
}
void tranferStudents(Node node, BinaryTree binaryTree) {
if (node != null) {
binaryTree.addByMark(node.student);
tranferStudents(node.left, binaryTree);
tranferStudents(node.right, binaryTree);
}
}
}
Лістинг файлу Student.java
package com.company;
import java.util.Comparator;
public class Student {
private String surname;
private int year;
private int mark;
public Student(String surname, int year, int mark) {
this.surname = surname;
this.year = year;
this.mark = mark;
}
public int compareTo(Student o) {
return Comparator.comparing(Student::getSurname)
.thenComparing(Student::getYear)
.thenComparing(Student::getMark)
.compare(this, o);
}
public int compareMarkTo(Student o) {
return Comparator.comparing(Student::getSurname)
.thenComparing(Student::getMark)
.compare(this, o);
}
@Override
public String toString() {
return "Student{" +
"surname='" + surname + '\'' +
", year=" + year +
", mark=" + mark +
'}';
}
public String getSurname() {
return surname;
}
public int getYear() {
return year;
}
public int getMark() {
return mark;
}
}
class Node {
Student student;
Node left;
Node right;
public Node(Student student) {
this.student = student;
left = null;
right = null;
}
}
Результат роботи програми:
Висновок: Набули практичних вмінь та навичок опрацювання нелінійних структур даних, представлених у вигляді бінарних дерев.