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, който съдържа три атрибута, а именно: данни отляво и отдясно. Тук лявото представлява левия дъщерен елемент на възела, а дясното представлява дясното дете на възела.

• Когато се създаде възел, данните ще преминат към атрибута на данните на възела и левият и десният ще бъдат зададени на нула.
• Дефинирайте друг клас, който има корен на атрибут.
• Root представлява основния възел на дървото и го инициализира на нула.

вмъкване ()ще добави нов възел към дървото:
• Той проверява дали коренът е нулев, което означава, че дървото е празно. Той ще добави новия възел като root.
• В противен случай ще добави 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. След това изтрийте най-дълбокия най-десен възел.

Помислете за следната фигура.

DeleteNode.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, който има три атрибута, а именно: данни отляво и отдясно. Тук лявото представлява левия дъщерен елемент на възела, а дясното представлява дясното дете на възела.
• Когато се създаде възел, данните ще преминат към атрибута на данните на възела и левият и десният ще бъдат зададени на нула.
• Дефинирайте друг клас, който има два атрибута корен и флаг.
  1. Root представлява основния възел на дървото и го инициализира на нула.
  2. Флагът ще се използва за проверка дали дадения възел присъства в дървото или не. Първоначално ще бъде зададено на false.

searchNode()ще търси определен възел в двоичното дърво:
• Той проверява дали коренът е нулев, което означава, че дървото е празно.
• Ако дървото не е празно, то ще сравни данните на temp със стойността. Ако те са равни, той ще зададе флага на true и ще се върне.
• Преминете през лявото поддърво, като извикате searchNode() рекурсивно и проверете дали стойността присъства в лявото поддърво.
• Обходете дясното поддърво, като извикате searchNode() рекурсивно и проверете дали стойността присъства в дясното поддърво.

ТърсенеBinaryTree.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

 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 програма за намиране на най-големия възел в двоичното дърво

LargestNode.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. Когато се създаде възел, данните ще преминат към атрибута на данните на възела и както левият, така и десният ще бъдат зададени на нула.
3. Дефинирайте друг клас, който има корен на атрибут.
   коренпредставя коренния възел на дървото и го инициализира на нула.

smallestElement()ще намери най-малкия възел в двоичното дърво:
1. Проверява дали коренът е нула , което означава, че дървото е празно.
2. Ако дървото не е празно, дефинирайте променлива min, която ще съхранява данните на temp.
3. Намерете минималния възел в лявото поддърво, като извикате smallestElement() рекурсивно. Запазете тази стойност в leftMin. Сравнете стойността на min с leftMin и запазете минимума от две до min.
4. Намерете минималния възел в дясното поддърво, като извикате smallestElement() рекурсивно. Запазете тази стойност в rightMin. Сравнете стойността на min с rightMin и запазете максимума от две до min.
5. В края min ще съдържа най-малкия възел в двоичното дърво.

Най-малкият възел.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. Когато се създаде възел, данните ще преминат към атрибута на данните на възела и левият и десният ще бъдат зададени на нула.
3. Дефинирайте друг клас, който има корен на атрибут.
   коренпредставлява основния възел на дървото и го инициализира на нула.

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