TechCodeview

Бінарне дерево це деревоподібна нелінійна структура даних, яка в основному використовується для сортування та пошуку, оскільки вони зберігають дані в ієрархічній формі. У цьому розділі ми дізнаємося реалізація структури даних бінарного дерева в Java . Також містить короткий опис структури даних бінарного дерева.

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

Дерево, в якому кожен вузол (батьківський) має не більше двох дочірніх вузлів (лівий і правий), називається бінарним деревом. Самий верхній вузол називається кореневим вузлом. У бінарному дереві вузол містить дані та покажчик (адресу) лівого та правого дочірніх вузлів.

The висота бінарного дерева є кількість ребер між коренем дерева і його найдальший (найглибший) лист. Якщо дерево є порожній , висота становить 0 . Висоту вузла позначають ч .

Висота наведеного вище бінарного дерева дорівнює 2.

Ми можемо обчислити кількість листів і вузлів за допомогою такої формули.

• Максимальна кількість листових вузлів є бінарним деревом: 2^ч
• Максимальна кількість вузлів є бінарним деревом: 2^h+1-1

Де h – висота бінарного дерева.

Приклад бінарного дерева

Типи бінарного дерева

Існують наступні типи бінарного дерева в структурі даних:

1. Повне/ Строго двійкове дерево
2. Повне бінарне дерево
3. Ідеальне бінарне дерево
4. Двійкове дерево балансу
5. Кореневе бінарне дерево
6. Вироджене/патологічне бінарне дерево
7. Розширене бінарне дерево
8. Перекошене двійкове дерево
   1. Бінарне дерево зі зміщенням вліво
   2. Бінарне дерево зі зміщенням вправо
9. Потокове бінарне дерево
   1. Однопотокове бінарне дерево
   2. Двопотокове бінарне дерево

Реалізація бінарного дерева в Java

Існує багато способів реалізації бінарного дерева. У цьому розділі ми реалізуємо двійкове дерево за допомогою структури даних LinkedList. Разом із цим ми також реалізуємо порядки обходу, пошук вузла та вставлення вузла в бінарне дерево.

Реалізація бінарного дерева за допомогою LinkedList

Алгоритм

Визначте клас Node, який містить три атрибути, а саме: дані зліва та справа. Тут ліворуч позначає лівий дочірній елемент вузла, а правий – правий дочірній елемент вузла.

• Коли вузол створено, дані будуть передані до атрибута даних вузла, а для лівого та правого буде встановлено значення null.
• Визначте інший клас, який має корінь атрибута.
• Корінь представляє кореневий вузол дерева та ініціалізує його значенням null.

вставити()додасть новий вузол до дерева:
• Він перевіряє, чи корінь є нульовим, що означає, що дерево порожнє. Це додасть новий вузол як root.
• Інакше це додасть root до черги.
• Змінний вузол представляє поточний вузол.
• По-перше, він перевіряє, чи має вузол лівий і правий дочірній елемент. Якщо так, він додасть обидва вузли до черги.
• Якщо лівого дочірнього елемента немає, новий вузол буде додано як лівий дочірній елемент.
• Якщо присутній лівий вузол, він додасть новий вузол як правий дочірній елемент.
в порядку()відображатиме вузли дерева в порядку.
• Він обходить все дерево, потім друкує ліву дочірню частину, за якою слідує корінь, а потім правий дочірній елемент.

BinarySearchTree.java

 public class BinarySearchTree { //Represent the node of binary tree public static class Node{ int data; Node left; Node right; public Node(int data){ //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public BinarySearchTree(){ root = null; } //factorial() will calculate the factorial of given number public int factorial(int num) { int fact = 1; if(num == 0) return 1; else { while(num > 1) { fact = fact * num; num--; } return fact; } } //numOfBST() will calculate the total number of possible BST by calculating Catalan Number for given key public int numOfBST(int key) { int catalanNumber = factorial(2 * key)/(factorial(key + 1) * factorial(key)); return catalanNumber; } public static void main(String[] args) { BinarySearchTree bt = new BinarySearchTree(); //Display total number of possible binary search tree with key 5 System.out.println('Total number of possible Binary Search Trees with given key: ' + bt.numOfBST(5)); } } 

Вихід:

 Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7 

Операції з бінарним деревом

Над бінарним деревом можна виконувати такі операції:

• Вставка
• Видалення
• Пошук
• Обхід

Програма на Java для вставки вузла в бінарне дерево

BinaryTreeInsert.java

 public class BinaryTreeInsert { public static void main(String[] args) { new BinaryTreeInsert().run(); } static class Node { Node left; Node right; int value; public Node(int value) { this.value = value; } } public void run() { Node rootnode = new Node(25); System.out.println('Building tree with root value ' + rootnode.value); System.out.println('================================='); insert(rootnode, 11); insert(rootnode, 15); insert(rootnode, 16); insert(rootnode, 23); insert(rootnode, 79); } public void insert(Node node, int value) { if (value node.value) { if (node.right != null) { insert(node.right, value); } else { System.out.println(' Inserted ' + value + ' to right of Node ' + node.value); node.right = new Node(value); } } } } 

Вихід:

 Building tree with root value 25 ================================= Inserted 11 to left of Node 25 Inserted 15 to right of Node 11 Inserted 16 to right of Node 15 Inserted 23 to right of Node 16 Inserted 79 to right of Node 25 

Програма Java для видалення вузла в Java

Алгоритм

1. Починаючи з кореня, знайдіть найглибший і крайній правий вузол у бінарному дереві та вузол, який ми хочемо видалити.
2. Замініть дані найглибшого правого вузла на вузол, який потрібно видалити.
3. Потім видаліть найглибший правий вузол.

Розглянемо наступний малюнок.

ВидалитиNode.java

 import java.util.LinkedList; import java.util.Queue; public class DeleteNode { // A binary tree node has key, pointer to // left child and a pointer to right child static class Node { int key; Node left, right; // Constructor Node(int key) { this.key = key; left = null; right = null; } } static Node root; static Node temp = root; // Inorder traversal of a binary tree static void inorder(Node temp) { if (temp == null) return; inorder(temp.left); System.out.print(temp.key + ' '); inorder(temp.right); } // Function to delete deepest // element in binary tree static void deleteDeepest(Node root, Node delNode) { Queue q = new LinkedList(); q.add(root); Node temp = null; // Do level order traversal until last node while (!q.isEmpty()) { temp = q.peek(); q.remove(); if (temp == delNode) { temp = null; return; } if (temp.right!=null) { if (temp.right == delNode) { temp.right = null; return; } else q.add(temp.right); } if (temp.left != null) { if (temp.left == delNode) { temp.left = null; return; } else q.add(temp.left); } } } // Function to delete given element // in binary tree static void delete(Node root, int key) { if (root == null) return; if (root.left == null && root.right == null) { if (root.key == key) { root=null; return; } else return; } Queue q = new LinkedList(); q.add(root); Node temp = null, keyNode = null; // Do level order traversal until // we find key and last node. while (!q.isEmpty()) { temp = q.peek(); q.remove(); if (temp.key == key) keyNode = temp; if (temp.left != null) q.add(temp.left); if (temp.right != null) q.add(temp.right); } if (keyNode != null) { int x = temp.key; deleteDeepest(root, temp); keyNode.key = x; } } // Driver code public static void main(String args[]) { root = new Node(10); root.left = new Node(11); root.left.left = new Node(7); root.left.right = new Node(12); root.right = new Node(9); root.right.left = new Node(15); root.right.right = new Node(8); System.out.print('Inorder traversal before deletion: '); inorder(root); //node to delete int key = 7; delete(root, key); System.out.print('
Inorder traversal after deletion: '); inorder(root); } } 

Вихід:

 Inorder traversal before deletion: 7 11 12 10 15 9 8 Inorder traversal after deletion: 8 11 12 10 15 9 

Програма Java для пошуку вузла у двійковому дереві

Алгоритм

• Визначте клас Node, який має три атрибути, а саме: дані зліва та справа. Тут ліворуч позначає лівий дочірній елемент вузла, а правий – правий дочірній елемент вузла.
• Коли вузол створено, дані будуть передані до атрибута даних вузла, а для лівого та правого буде встановлено значення null.
• Визначте інший клас, який має два атрибути root і flag.
  1. Корінь представляє кореневий вузол дерева та ініціалізує його значенням null.
  2. Прапорець буде використовуватися для перевірки наявності даного вузла в дереві чи ні. Спочатку буде встановлено значення false.

searchNode()буде шукати певний вузол у бінарному дереві:
• Він перевіряє, чи корінь є нульовим, що означає, що дерево порожнє.
• Якщо дерево не порожнє, воно порівнює тимчасові дані зі значенням. Якщо вони рівні, він встановить прапор на true та повернеться.
• Перегляньте ліве піддерево, викликавши searchNode() рекурсивно, і перевірте, чи присутнє значення в лівому піддереві.
• Перейдіть до правого піддерева, викликавши searchNode() рекурсивно, і перевірте, чи присутнє значення в правому піддереві.

SearchBinaryTree.java

 public class SearchBinaryTree { //Represent a node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public static boolean flag = false; public SearchBinaryTree() { root = null; } //searchNode() will search for the particular node in the binary tree public void searchNode(Node temp, int value) { //Check whether tree is empty if(root == null) { System.out.println('Tree is empty'); } else { //If value is found in the given binary tree then, set the flag to true if(temp.data == value) { flag = true; return; } //Search in left subtree if(flag == false && temp.left != null) { searchNode(temp.left, value); } //Search in right subtree if(flag == false && temp.right != null) { searchNode(temp.right, value); } } } public static void main(String[] args) { SearchBinaryTree bt = new SearchBinaryTree(); //Add nodes to the binary tree bt.root = new Node(11); bt.root.left = new Node(8); bt.root.right = new Node(12); bt.root.left.left = new Node(78); bt.root.right.left = new Node(23); bt.root.right.right = new Node(36); //Search for node 5 in the binary tree bt.searchNode(bt.root, 23); if(flag) System.out.println('Element is present in the binary tree.'); else System.out.println('Element is not present in the binary tree.'); } } 

Вихід:

 Element is present in the binary tree. 

Обхід бінарного дерева

Примітка. Окрім трьох вищезазначених обходів, існує ще один порядок обходу, який називається обходом межі.

Програма Java для обходу в порядку, попереднього та після замовлення

BinaryTree.java

java подвійний до рядка

 public class BinaryTree { // first node private Node root; BinaryTree() { root = null; } // Class representing tree nodes static class Node { int value; Node left; Node right; Node(int value) { this.value = value; left = null; right = null; } public void displayData() { System.out.print(value + ' '); } } public void insert(int i) { root = insert(root, i); } //Inserting node - recursive method public Node insert(Node node, int value) { if(node == null){ return new Node(value); } // Move to the left if passed value is // less than the current node if(value node.value) { node.right = insert(node.right, value); } return node; } // Search node in binary search tree public Node find(int searchedValue) { Node current = root; while(current.value != searchedValue) { if(searchedValue = current = current.right; if(current == null) { return null; } } return current; } // For traversing in order public void inOrder(Node node) { if(node != null) { inOrder(node.left); node.displayData(); inOrder(node.right); } } // Preorder traversal public void preOrder(Node node) { if(node != null){ node.displayData(); preOrder(node.left); preOrder(node.right); } } // Postorder traversal public void postOrder(Node node) { if(node != null) { postOrder(node.left); postOrder(node.right); node.displayData(); } } public static void main(String[] args) { BinaryTree bst = new BinaryTree(); bst.insert(34); bst.insert(56); bst.insert(12); bst.insert(89); bst.insert(67); bst.insert(90); System.out.println('Inorder traversal of binary tree'); bst.inOrder(bst.root); System.out.println(); System.out.println('Preorder traversal of binary tree'); bst.preOrder(bst.root); System.out.println(); System.out.println('Postorder traversal of binary tree'); bst.postOrder(bst.root); System.out.println(); } } 

Вихід:

 Inorder traversal of binary tree 12 34 56 67 89 90 Preorder traversal of binary tree 34 12 56 89 67 90 Postorder traversal of binary tree 12 67 90 89 56 34 

Крім перерахованих вище операцій, ми також можемо виконувати такі операції, як великий вузол, найменший вузол і сума всіх вузлів.

Програма Java для пошуку найбільшого вузла в бінарному дереві

Найбільший вузол.java

 public class LargestNode { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public LargestNode() { root = null; } //largestElement() will find out the largest node in the binary tree public int largestElement(Node temp) { //Check whether tree is empty if(root == null) { System.out.println('Tree is empty'); return 0; } else { int leftMax, rightMax; //Max will store temp's data int max = temp.data; //It will find largest element in left subtree if(temp.left != null){ leftMax = largestElement(temp.left); //Compare max with leftMax and store greater value into max max = Math.max(max, leftMax); } //It will find largest element in right subtree if(temp.right != null){ rightMax = largestElement(temp.right); //Compare max with rightMax and store greater value into max max = Math.max(max, rightMax); } return max; } } public static void main(String[] args) { LargestNode bt = new LargestNode(); //Add nodes to the binary tree bt.root = new Node(90); bt.root.left = new Node(99); bt.root.right = new Node(23); bt.root.left.left = new Node(96); bt.root.right.left = new Node(45); bt.root.right.right = new Node(6); bt.root.right.left = new Node(13); bt.root.right.right = new Node(77); //Display largest node in the binary tree System.out.println('Largest element in the binary tree: ' + bt.largestElement(bt.root)); } } 

Вихід:

 Largest element in the binary tree: 99 

Програма Java для пошуку найменшого вузла в двійковому дереві

Алгоритм

1. Визначте клас Node, який має три атрибути, а саме: дані, лівий і правий. Тут ліворуч позначає лівий дочірній елемент вузла, а правий – правий дочірній елемент вузла.
2. Коли вузол створено, дані будуть передані до атрибута даних вузла, а для лівого та правого буде встановлено значення null.
3. Визначте інший клас, який має корінь атрибута.
   Коріньпредставляють кореневий вузол дерева та ініціалізують його значенням null.

smallestElement()знайде найменший вузол у бінарному дереві:
1. Перевіряє чи корінь нульовий , що означає, що дерево порожнє.
2. Якщо дерево не порожнє, визначте змінну min, яка зберігатиме дані temp.
3. Знайдіть мінімальний вузол у лівому піддереві, викликавши smallestElement() рекурсивно. Збережіть це значення в leftMin. Порівняйте значення min з leftMin і збережіть мінімум від двох до min.
4. Знайдіть мінімальний вузол у правому піддереві, викликавши smallestElement() рекурсивно. Збережіть це значення в rightMin. Порівняйте значення min із rightMin і збережіть максимум від двох до min.
5. Зрештою, min міститиме найменший вузол у бінарному дереві.

SmallestNode.java

 public class SmallestNode { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public SmallestNode() { root = null; } //smallestElement() will find out the smallest node in the binary tree public int smallestElement(Node temp) { //Check whether tree is empty if(root == null) { System.out.println('Tree is empty'); return 0; } else { int leftMin, rightMin; //Min will store temp's data int min = temp.data; //It will find smallest element in left subtree if(temp.left != null) { leftMin = smallestElement(temp.left); //If min is greater than leftMin then store the value of leftMin into min min = Math.min(min, leftMin); } //It will find smallest element in right subtree if(temp.right != null) { rightMin = smallestElement(temp.right); //If min is greater than rightMin then store the value of rightMin into min min = Math.min(min, rightMin); } return min; } } public static void main(String[] args) { SmallestNode bt = new SmallestNode(); //Add nodes to the binary tree bt.root = new Node(9); bt.root.left = new Node(5); bt.root.right = new Node(7); bt.root.left.left = new Node(1); bt.root.right.left = new Node(2); bt.root.right.right = new Node(8); bt.root.right.left = new Node(4); bt.root.right.right = new Node(3); //Display smallest node in the binary tree System.out.println('Smallest element in the binary tree: ' + bt.smallestElement(bt.root)); } } 

Вихід:

 Smallest element in the binary tree: 1 

Програма Java для пошуку максимальної ширини бінарного дерева

Алгоритм

1. Визначте клас Node, який має три атрибути, а саме: дані зліва та справа. Тут ліворуч позначає лівий дочірній елемент вузла, а правий – правий дочірній елемент вузла.
2. Коли вузол створено, дані будуть передані до атрибута даних вузла, а для лівого та правого буде встановлено значення null.
3. Визначте інший клас, який має корінь атрибута.
   Коріньпредставляє кореневий вузол дерева та ініціалізує його значенням null.

1. Змінна maxWidth зберігатиме максимальну кількість вузлів, присутніх на будь-якому рівні.
2. Черга використовується для обходу бінарного дерева по рівнях.
3. Він перевіряє, чи корінь є нульовим, що означає, що дерево порожнє.
4. Якщо ні, додайте кореневий вузол до черги. Змінна nodesInLevel відстежує кількість вузлів на кожному рівні.
5. Якщо nodesInLevel > 0, видаліть вузол з початку черги та додайте його лівий і правий дочірні вузли до черги. Під час першої ітерації вузол 1 буде видалено, а його дочірні вузли 2 і 3 буде додано до черги. У другій ітерації вузол 2 буде видалено, його дочірні вузли 4 і 5 будуть додані до черги і так далі.
6. MaxWidth зберігатиме max(maxWidth, nodesInLevel). Таким чином, у будь-який заданий момент часу він представлятиме максимальну кількість вузлів.
7. Це триватиме, доки не будуть пройдені всі рівні дерева.

BinaryTree.java

 import java.util.LinkedList; import java.util.Queue; public class BinaryTree { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public BinaryTree() { root = null; } //findMaximumWidth() will find out the maximum width of the given binary tree public int findMaximumWidth() { int maxWidth = 0; //Variable nodesInLevel keep tracks of number of nodes in each level int nodesInLevel = 0; //queue will be used to keep track of nodes of tree level-wise Queue queue = new LinkedList(); //Check if root is null, then width will be 0 if(root == null) { System.out.println('Tree is empty'); return 0; } else { //Add root node to queue as it represents the first level queue.add(root); while(queue.size() != 0) { //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue nodesInLevel = queue.size(); //maxWidth will hold maximum width. //If nodesInLevel is greater than maxWidth then, maxWidth will hold the value of nodesInLevel maxWidth = Math.max(maxWidth, nodesInLevel); //If variable nodesInLevel contains more than one node //then, for each node, we'll add left and right child of the node to the queue while(nodesInLevel > 0) { Node current = queue.remove(); if(current.left != null) queue.add(current.left); if(current.right != null) queue.add(current.right); nodesInLevel--; } } } return maxWidth; } public static void main(String[] args) { BinaryTree bt = new BinaryTree(); //Add nodes to the binary tree bt.root = new Node(1); bt.root.left = new Node(2); bt.root.right = new Node(3); bt.root.left.left = new Node(4); bt.root.left.right = new Node(5); bt.root.right.left = new Node(6); bt.root.right.right = new Node(7); bt.root.left.left.left = new Node(8); //Display the maximum width of given tree System.out.println('Maximum width of the binary tree: ' + bt.findMaximumWidth()); } } 

Вихід:

 Maximum width of the binary tree: 4