НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №7 з навчальної дисципліни “Програмування складних алгоритмів” Тема: Поняття бінарного дерева. Обхід бінарного дерева. Створення, відображення дерева. Вставлення, видалення елементів у бінарному дереві. Варіант 7 Київ 20____ Мета: Набути навичок створення та обробки бінарних дерев. Теоретична частина: Дерево – це сукупність вузлів і відношень, що утворює ієрархічну структуру. Вузол (або вершина) дерева – це математична абстракція, яка моделює абстрактні об’єкти чи об’єкти реального світу. Вузол, як правило, має ім’я, яке називається його ключем або ідентифікатором. У вище наведеному прикладі, таким ідентифікатором є повний шлях до файлу або папки(разом з іменем). Відношення визначають зв’язки між вершинами типу батько-дитина. Ці зв’язки називаються гілками (ребрами) дерева. На малюнку зображено впорядковане бінарне дерево: / Дерево називається впорядкованим, якщо набір дітей кожного його вузла є впорядкований. Діти вузла впорядкованого дерева, як правило впорядковуються зліва на право, якщо інакший порядок окремо не зазначений. Впорядкування дерев використовується для співставлення вузлів, що не пов’язані співвідношенням типу батько-син. У даній роботі використовується послідовний спосіб проходження дерева. Який проходить дерево за наведеною схемою: / Кожна вершина бінарного дерева є структурою, що складається з чотирьох видів полів. Вмістом цих полів будуть відповідно: • інформаційне поле (ключ вершини); • службове поле (їх може бути декілька або жодного); • покажчик на ліве піддерево; • покажчик на праве піддерево. Завдання до роботи: Створити бінарне дерево та виконати завдання згідно варіанту: Варіант Використовуваний спосіб обходу дерева для виконання завдання Завдання  7 Послідовний 1. Реверсувати кожен елемент дерева, тобто якщо є елемент 345, то замінюємо його на 543. 2. Визначити в якому піддереві (лівому або правому) кількість парних елементів більша. Вивести ці елементи на екран для кожного піддерева окремо.   Результати виконання лабораторної роботи: / Дана програма спочатку створює дерево, а далі додає елементи, щоб заповнити дерево інформацією. Потім програма проходить кожен елемент дерева та реверсує ці елементи. Також програма рахує у якому піддереві парних елементів більше та виводить ці парні елементи. Програмний код: public class LR7 { public static void main(String[] args) { Tree tree = new Tree(); Tree.Node root = new Tree.Node(123); System.out.println("Бінарне дерево"); System.out.println("Початкове значення дерева - " + root.value); tree.insert(root, 106); tree.insert(root, 95); tree.insert(root, 45); tree.insert(root, 101); tree.insert(root, 118); tree.insert(root, 112); tree.insert(root, 121); tree.insert(root, 95); tree.insert(root, 167); tree.insert(root, 142); tree.insert(root, 136); tree.insert(root, 153); tree.insert(root, 215); tree.insert(root, 189); tree.insert(root, 329); System.out.println("Елементи дерева:"); tree.traverseInOrder(root); System.out.println("\nЕлементи дерева після реверсування:"); tree.reverse(root); tree.traverseInOrder(root); //повертаємось до початкового вигляду tree.reverse(root); int evenLeft = tree.evenNumbers(root.left); Tree.count1=0; int evenRight = tree.evenNumbers(root.right); if(evenLeft > evenRight) System.out.println("\nУ лівій частині парних чисел більше. У лівій " + evenLeft + ", а у правій " + evenRight); else if(evenLeft < evenRight) System.out.println("\nУ правій частині парних чисел більше. У правій " + evenLeft + ", а у лівій " + evenRight); else System.out.println("\nВ обох піддеревах рівна кількість парних чисел. У правій " + evenLeft + ", а у лівій " + evenRight); System.out.println("\nПарні елементи у лівій частині:"); tree.displayEven(root.left); System.out.println("\nПарні елементи у правій частині:"); tree.displayEven(root.right); } } class Tree { static class Node { int value; Node left, right; Node(int value){ this.value = value; left = null; right = null; } } public void insert(Node node, int value) { if (value < node.value){ if (node.left != null){ insert(node.left, value); } else { System.out.println("\tДодано " + value + " до лівої вітки від " + node.value); node.left = new Node(value); } } else if (value > node.value) { if (node.right != null) { insert(node.right, value); } else { System.out.println("\tДодано " + value + " до правої вітки від " + node.value); node.right = new Node(value); } } } public void traverseInOrder(Node node) { if (node != null) { System.out.print(node.value + " "); traverseInOrder(node.left); traverseInOrder(node.right); } } public void reverse(Node node) { if (node != null) { int reverse = 0; while(node.value != 0) { int remainder = node.value % 10; reverse = reverse * 10 + remainder; node.value = node.value/10; } node.value = reverse; reverse(node.left); reverse(node.right); } } public static int count1 = 0; public int evenNumbers(Node node) { if (node != null) { if(node.value % 2 ==0) count1++; evenNumbers(node.left); evenNumbers(node.right); } return count1; } public void displayEven(Node node) { if (node != null) { if(node.value % 2 == 0) System.out.print(node.value + " "); displayEven(node.left); displayEven(node.right); } } } Висновки. Під час виконання лабораторної роботи було набуто навичок створення бінарних дерев та виконання операцій над ними. Програма вміє додавати нові елементи, виводити дерево на екран, реверсувати елементи та рахувати кількість парних елементів.