Drzewo binarne to nieliniowa struktura danych typu drzewiastego, używana głównie do sortowania i wyszukiwania, ponieważ przechowuje dane w formie hierarchicznej. W tej części nauczymy się implementacja binarnej struktury danych w języku Java . Zawiera także krótki opis struktury danych drzewa binarnego.

ups

Drzewo binarne

Drzewo, w którym każdy węzeł (rodzic) ma co najwyżej dwa węzły potomne (lewy i prawy), nazywa się drzewem binarnym. Węzeł znajdujący się najwyżej nazywa się węzłem głównym. W drzewie binarnym węzeł zawiera dane i wskaźnik (adres) lewego i prawego węzła podrzędnego.

The wysokość drzewa binarnego to liczba krawędzi pomiędzy korzeniem drzewa i jego najdalszy (najgłębszy) liść. Jeśli drzewo jest pusty , wysokość wynosi 0 . Wysokość węzła jest oznaczona przez H .

Wysokość powyższego drzewa binarnego wynosi 2.

Liczbę liści i węzłów możemy obliczyć, korzystając z poniższego wzoru.

• Maksymalna liczba węzłów liściowych jest drzewem binarnym: 2^H
• Maksymalna liczba węzłów to drzewo binarne: 2^h+1-1

Gdzie, h jest wysokością drzewa binarnego.

Przykład drzewa binarnego

Rodzaje drzew binarnych

W strukturze danych istnieją następujące typy drzew binarnych:

1. Pełne/ściśle binarne drzewo
2. Kompletne drzewo binarne
3. Idealne drzewo binarne
4. Równowaga drzewa binarnego
5. Ukorzenione drzewo binarne
6. Zdegenerowane/patologiczne drzewo binarne
7. Rozszerzone drzewo binarne
8. Przekrzywione drzewo binarne
   1. Drzewo binarne przekrzywione w lewo
   2. Prawoskośne drzewo binarne
9. Wątkowe drzewo binarne
   1. Jednowątkowe drzewo binarne
   2. Podwójnie gwintowane drzewo binarne

Implementacja drzewa binarnego w Javie

Istnieje wiele sposobów implementacji drzewa binarnego. W tej sekcji zaimplementujemy drzewo binarne przy użyciu struktury danych LinkedList. Razem z nim zaimplementujemy także polecenia przejścia, przeszukania węzła i wstawienia węzła do drzewa binarnego.

Implementacja drzewa binarnego przy użyciu LinkedList

Algorytm

Zdefiniuj klasę Node zawierającą trzy atrybuty, a mianowicie: dane lewe i prawe. Tutaj lewe reprezentuje lewe dziecko węzła, a prawe reprezentuje prawe dziecko węzła.

• Po utworzeniu węzła dane zostaną przekazane do atrybutu danych węzła, a lewy i prawy element zostaną ustawione na wartość null.
• Zdefiniuj inną klasę, która ma katalog główny atrybutu.
• Root reprezentuje węzeł główny drzewa i inicjuje go na wartość null.

wstawić()doda nowy węzeł do drzewa:
• Sprawdza, czy korzeń ma wartość null, co oznacza, że ​​drzewo jest puste. Doda nowy węzeł jako root.
• W przeciwnym razie doda root do kolejki.
• Węzeł zmiennej reprezentuje bieżący węzeł.
• Najpierw sprawdza, czy węzeł ma lewe i prawe dziecko. Jeśli tak, doda oba węzły do ​​kolejki.
• Jeśli lewe dziecko nie jest obecne, doda nowy węzeł jako lewe dziecko.
• Jeśli lewy jest obecny, doda nowy węzeł jako prawy element podrzędny.
w celu()wyświetli węzły drzewa w kolejności.
• Przechodzi przez całe drzewo, a następnie wypisuje lewe dziecko, po którym następuje korzeń, a następnie prawe dziecko.

BinarySearchTree.java

mapa w maszynopisie

 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)); } } 

Wyjście:

 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 

Operacje na drzewach binarnych

Na drzewie binarnym można wykonać następujące operacje:

• Wprowadzenie
• Usunięcie
• Szukaj
• Przejście

Program Java do wstawiania węzła do drzewa binarnego

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); } } } } 

Wyjście:

 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 

Program Java do usuwania węzła w Javie

Algorytm

1. Zaczynając od korzenia, znajdź najgłębszy i najbardziej na prawo położony węzeł w drzewie binarnym oraz węzeł, który chcemy usunąć.
2. Zastąp dane najgłębszego prawego węzła węzłem, który ma zostać usunięty.
3. Następnie usuń najgłębszy węzeł położony skrajnie na prawo.

Rozważ następujący rysunek.

UsuńNode.java

leksykograficznie

 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); } } 

Wyjście:

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

Program Java do wyszukiwania węzła w drzewie binarnym

Algorytm

• Zdefiniuj klasę Node, która ma trzy atrybuty, a mianowicie: dane lewe i prawe. Tutaj lewe reprezentuje lewe dziecko węzła, a prawe reprezentuje prawe dziecko węzła.
• Po utworzeniu węzła dane zostaną przekazane do atrybutu danych węzła, a lewy i prawy element zostaną ustawione na wartość null.
• Zdefiniuj inną klasę, która ma dwa atrybuty root i flag.
  1. Root reprezentuje węzeł główny drzewa i inicjuje go na wartość null.
  2. Flaga posłuży do sprawdzenia, czy dany węzeł znajduje się w drzewie, czy nie. Początkowo zostanie ustawiona na wartość false.

węzeł wyszukiwania()wyszuka konkretny węzeł w drzewie binarnym:
• Sprawdza, czy korzeń ma wartość null, co oznacza, że ​​drzewo jest puste.
• Jeśli drzewo nie jest puste, porówna dane temp z wartością. Jeśli są równe, ustawi flagę na true i zwróci.
• Przejdź przez lewe poddrzewo, wywołując rekurencyjnie funkcję searchNode() i sprawdź, czy wartość występuje w lewym poddrzewie.
• Przejdź przez prawe poddrzewo, wywołując rekurencyjnie funkcję searchNode() i sprawdź, czy wartość występuje w prawym poddrzewie.

Wyszukaj plik 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.'); } } 

Wyjście:

 Element is present in the binary tree. 

Przechodzenie przez drzewo binarne

Uwaga: Z wyjątkiem powyższych trzech przejść, istnieje inny porządek przejścia, zwany przejściem przez granicę.

Program Java do przeglądania zamówień w przedsprzedaży, przedsprzedaży i po zamówieniu

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(); } } 

Wyjście:

 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 

Oprócz powyższych operacji możemy również wykonywać operacje takie jak duży węzeł, najmniejszy węzeł i suma wszystkich węzłów.

Program Java do wyszukiwania największego węzła w drzewie binarnym

Największy węzeł.java

10 1 milion

 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)); } } 

Wyjście:

 Largest element in the binary tree: 99 

Program Java do wyszukiwania najmniejszego węzła w drzewie binarnym

Algorytm

1. Zdefiniuj klasę Node, która ma trzy atrybuty, a mianowicie: dane, lewy i prawy. Tutaj lewe reprezentuje lewe dziecko węzła, a prawe reprezentuje prawe dziecko węzła.
2. Po utworzeniu węzła dane zostaną przekazane do atrybutu danych węzła, a lewy i prawy element zostaną ustawione na wartość null.
3. Zdefiniuj inną klasę, która ma katalog główny atrybutu.
   Źródłoreprezentuje węzeł główny drzewa i inicjuje go na wartość null.

najmniejszyElement()znajdzie najmniejszy węzeł w drzewie binarnym:
1. Sprawdza, czy root ma wartość zerową , co oznacza, że ​​drzewo jest puste.
2. Jeśli drzewo nie jest puste, zdefiniuj zmienną min, która będzie przechowywać dane temp.
3. Znajdź minimalny węzeł w lewym poddrzewie, wywołując rekursywnie metodę najmniejszyElement(). Zapisz tę wartość w leftMin. Porównaj wartość min z leftMin i zapisz minimum dwa do min.
4. Znajdź minimalny węzeł w prawym poddrzewie, wywołując rekurencyjnie metodę najmniejszego elementu(). Zapisz tę wartość w RightMin. Porównaj wartość min z RightMin i zapisz maksymalnie od dwóch do min.
5. Na koniec min będzie zawierał najmniejszy węzeł w drzewie binarnym.

Najmniejszy węzeł.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)); } } 

Wyjście:

 Smallest element in the binary tree: 1 

Program Java do znajdowania maksymalnej szerokości drzewa binarnego

Algorytm

1. Zdefiniuj klasę Node, która ma trzy atrybuty, a mianowicie: dane lewe i prawe. Tutaj lewe reprezentuje lewe dziecko węzła, a prawe reprezentuje prawe dziecko węzła.
2. Po utworzeniu węzła dane zostaną przekazane do atrybutu danych węzła, a lewy i prawy element zostaną ustawione na wartość null.
3. Zdefiniuj inną klasę, która ma katalog główny atrybutu.
   Źródłoreprezentuje węzeł główny drzewa i inicjuje go na wartość null.

1. Zmienna maxWidth będzie przechowywać maksymalną liczbę węzłów obecnych na dowolnym poziomie.
2. Kolejka służy do poruszania się po drzewie binarnym na poziomie.
3. Sprawdza, czy korzeń ma wartość null, co oznacza, że ​​drzewo jest puste.
4. Jeśli nie, dodaj węzeł główny do kolejki. Zmienna nodesInLevel śledzi liczbę węzłów na każdym poziomie.
5. Jeśli nodesInLevel > 0, usuń węzeł z przodu kolejki i dodaj jego lewe i prawe dziecko do kolejki. W pierwszej iteracji węzeł 1 zostanie usunięty, a jego węzły podrzędne 2 i 3 zostaną dodane do kolejki. W drugiej iteracji węzeł 2 zostanie usunięty, jego dzieci 4 i 5 zostaną dodane do kolejki i tak dalej.
6. MaxWidth będzie przechowywać max (maxWidth, nodesInLevel). Zatem w dowolnym momencie będzie to reprezentować maksymalną liczbę węzłów.
7. Dzieje się tak aż do przejścia wszystkich poziomów drzewa.

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()); } } 

Wyjście:

 Maximum width of the binary tree: 4