Ім'я файлу: ASDlab6.docx
Розширення: docx
Розмір: 37кб.
Дата: 28.02.2020

Міністерство науки і освіти України

Вінницький національний технічний університет

Кафедра програмного забезпечення

Лабораторна робота № 6

з дисципліни «Алгоритми та структури даних»

Бінарні дерева

Група 3ПІ-18б

Виконав: Пацалюк В. С.

Перевірив: Коваленко О.О.

Вінниця 2019

Мета: Набуття практичних вмінь та навичок опрацювання нелінійних структур даних, представлених у вигляді бінарних дерев.

Завдання:

1.Написати програму, в якій дані вашого варіанту структури записуються в дерева (використати три поля для вузла –текстове дане та два числові. Наприклад, вузол дерева містить таку корисну інформацію: прізвище студента, рік народження, оцінка).Ввести з клавіатури декілька"студентів" у двійкове дерево, організоване за порядком текстового поля. Роздрукувати отримане дерево.

2.Знайти середню значення однго з числових полів, зчитуючи дані з дерева.

3.Дописати функцію видалення з пам’яті всього дерева

Вказівка: рекурсивна функція, яка

1) видаляє ліве піддерево, іліву гілку занулює;

2) видаляє праве піддерево, і правугілку занулює;

3) видаляє сам вузол, потім зануливши вказівник на нього Наприкінці програми видалити з пам’яті дерево.

4."Пересипати" дані з першого дерева у друге дерево того ж типу, тільки організованого за першим числовим ключем (напр., роком народження) та роздрукувати його (а перше дерево стерти).

Лістинг програми:

Лістинг файлу Main.java

  1. package com.company;  

  2.   

  3.   

  4.   

  5.     public class Main {  

  6.         public static void main(String... args) {  

  7.             BinaryTree binaryTree = new BinaryTree();  

  8.             binaryTree.add(new Student("Ваня", 2, 2));  

  9.             binaryTree.add(new Student("Вова", 2, 5));  

  10.             binaryTree.add(new Student("Маша", 3, 3));  

  11.             binaryTree.add(new Student("Маша", 3, 2));  

  12.             binaryTree.add(new Student("Миша",2,3));  

  13.             binaryTree.traverseInOrder(binaryTree.root);  

  14.             binaryTree.showTree();  

  15.             BinaryTree binaryTree1 = new BinaryTree();  

  16.             binaryTree1.showTree();  

  17.         }  

  18.     }  

Лістинг файлу BinaryTree.java

  1. package com.company;  

  2.   

  3. public class BinaryTree {  

  4.     private int allMarks;  

  5.     private int allStudents;  

  6.     Node root;  

  7.   

  8.     private Node addRecursive(Node current, Student student) {  

  9.   

  10.         if (current == null) {  

  11.             return new Node(student);  

  12.         }  

  13.         int value = student.compareTo(current.student);  

  14.         if (value < 0) {  

  15.             current.left = addRecursive(current.left, student);  

  16.         } else if (value > 0) {  

  17.             current.right = addRecursive(current.right, student);  

  18.         } else {  

  19.             return current;  

  20.         }  

  21.         return current;  

  22.     }  

  23.   

  24.     private Node addRecursiveByMark(Node current, Student student) {  

  25.   

  26.         if (current == null) {  

  27.             return new Node(student);  

  28.         }  

  29.         int value = student.compareMarkTo(current.student);  

  30.         if (value < 0) {  

  31.             current.left = addRecursive(current.left, student);  

  32.         } else if (value > 0) {  

  33.             current.right = addRecursive(current.right, student);  

  34.         } else {  

  35.             return current;  

  36.         }  

  37.         return current;  

  38.     }  

  39.   

  40.     void add(Student student) {  

  41.         root = addRecursive(root, student);  

  42.         allMarks += student.getMark();  

  43.         allStudents++;  

  44.     }  

  45.   

  46.     void addByMark(Student student) {  

  47.         root = addRecursiveByMark(root, student);  

  48.     }  

  49.   

  50.     void traverseInOrder(Node node) {  

  51.         if (node != null) {  

  52.             System.out.println(node.student.toString());  

  53.             traverseInOrder(node.left);  

  54.             traverseInOrder(node.right);  

  55.         }  

  56.     }  

  57.   

  58.     private void showLeftTree(Node node) {  

  59.         if (node != null) {  

  60.             System.out.println("Left->" + node.student.toString());  

  61.             showLeftTree(node.left);  

  62.         }  

  63.     }  

  64.   

  65.     private void showRightTree(Node node) {  

  66.         if (node != null) {  

  67.             System.out.println("Right->" + node.student.toString());  

  68.             showRightTree(node.right);  

  69.         }  

  70.     }  

  71.   

  72.     private void showRoot(Node node) {  

  73.         if (node != null) {  

  74.             System.out.println("Root->" + node.student.toString());  

  75.         } else {  

  76.             System.out.println("No root");  

  77.         }  

  78.     }  

  79.   

  80.     void showTree() {  

  81.         showRoot(root);  

  82.         try {  

  83.             showLeftTree(root.left);  

  84.         } catch (NullPointerException e) {  

  85.             System.out.println("No left tree");  

  86.         }  

  87.         try {  

  88.             showRightTree(root.right);  

  89.         } catch (NullPointerException e) {  

  90.             System.out.println("No right tree");  

  91.         }  

  92.     }  

  93.   

  94.     int findMiddleMark() {  

  95.         return allMarks / allStudents;  

  96.     }  

  97.   

  98.     private void deleteLeftRecursive(Node node) {  

  99.         if (node != null) {  

  100.             System.out.println("Delete->" + node.student.toString());  

  101.             node.student = null;  

  102.             deleteLeftRecursive(node.left);  

  103.         }  

  104.     }  

  105.   

  106.     private void deleteRightRecursive(Node node) {  

  107.         if (node != null) {  

  108.             System.out.println("Delete->" + node.student.toString());  

  109.             node.student = null;  

  110.             deleteRightRecursive(node.left);  

  111.         }  

  112.     }  

  113.   

  114.     private void deleteRoot(Node node) {  

  115.         System.out.println("Delete->" + node.student.toString());  

  116.         node.student = null;  

  117.         root = null;  

  118.     }  

  119.   

  120.     void deleteTree() {  

  121.         deleteLeftRecursive(root.left);  

  122.         deleteRightRecursive(root.right);  

  123.         deleteRoot(root);  

  124.     }  

  125.   

  126.     void tranferStudents(Node node, BinaryTree binaryTree) {  

  127.         if (node != null) {  

  128.             binaryTree.addByMark(node.student);  

  129.             tranferStudents(node.left, binaryTree);  

  130.             tranferStudents(node.right, binaryTree);  

  131.         }  

  132.     }  

  133.   

  134. }  

Лістинг файлу Student.java

  1. package com.company;  

  2.   

  3. import java.util.Comparator;  

  4.   

  5. public class Student {  

  6.     private String surname;  

  7.     private int year;  

  8.     private int mark;  

  9.   

  10.     public Student(String surname, int year, int mark) {  

  11.         this.surname = surname;  

  12.         this.year = year;  

  13.         this.mark = mark;  

  14.     }  

  15.   

  16.   

  17.     public int compareTo(Student o) {  

  18.         return Comparator.comparing(Student::getSurname)  

  19.                 .thenComparing(Student::getYear)  

  20.                 .thenComparing(Student::getMark)  

  21.                 .compare(this, o);  

  22.     }  

  23.   

  24.     public int compareMarkTo(Student o) {  

  25.         return Comparator.comparing(Student::getSurname)  

  26.                 .thenComparing(Student::getMark)  

  27.                 .compare(this, o);  

  28.     }  

  29.   

  30.     @Override  

  31.     public String toString() {  

  32.         return "Student{" +  

  33.                 "surname='" + surname + '\'' +  

  34.                 ", year=" + year +  

  35.                 ", mark=" + mark +  

  36.                 '}';  

  37.     }  

  38.   

  39.     public String getSurname() {  

  40.         return surname;  

  41.     }  

  42.   

  43.     public int getYear() {  

  44.         return year;  

  45.     }  

  46.   

  47.     public int getMark() {  

  48.         return mark;  

  49.     }  

  50. }  

  51.   

  52. class Node {  

  53.   

  54.     Student student;  

  55.     Node left;  

  56.     Node right;  

  57.   

  58.     public Node(Student student) {  

  59.         this.student = student;  

  60.         left = null;  

  61.         right = null;  

  62.     }  

  63. }  

Результат роботи програми:



Висновок: Набули практичних вмінь та навичок опрацювання нелінійних структур даних, представлених у вигляді бінарних дерев.
скачати

© Усі права захищені
написати до нас