TechCodeview

Binární strom je stromová nelineární datová struktura, která se používá hlavně pro třídění a vyhledávání, protože ukládá data v hierarchické formě. V této části se naučíme implementace binární stromové datové struktury v Javě . Také poskytuje krátký popis binární stromové datové struktury.

Binární strom

Strom, ve kterém má každý uzel (rodič) nejvýše dva podřízené uzly (levý a pravý), se nazývá binární strom. Nejvyšší uzel se nazývá kořenový uzel. V binárním stromu uzel obsahuje data a ukazatel (adresu) levého a pravého podřízeného uzlu.

The výška binárního stromu je počet hran mezi kořenem stromu a jeho nejvzdálenější (nejhlubší) list. Pokud je strom prázdný , výška je 0 . Výška uzlu je označena h .

Výška výše uvedeného binárního stromu je 2.

Počet listů a uzlu můžeme vypočítat pomocí následujícího vzorce.

linux změnit název adresáře

• Maximální počet listových uzlů je binární strom: 2^h
• Maximální počet uzlů je binární strom: 2^h+1-1

Kde, h je výška binárního stromu.

Příklad binárního stromu

Typy binárních stromů

V datové struktuře existují následující typy binárních stromů:

1. Úplný/přísně binární strom
2. Kompletní binární strom
3. Perfektní binární strom
4. Binární strom rovnováhy
5. Zakořeněný binární strom
6. Degenerovaný/patologický binární strom
7. Rozšířený binární strom
8. Zkosený binární strom
   1. Doleva zkosený binární strom
   2. Pravoúhlý binární strom
9. Závitový binární strom
   1. Jednovláknový binární strom
   2. Binární strom s dvojitým závitem

Implementace binárního stromu v Javě

Existuje mnoho způsobů, jak implementovat binární strom. V této části budeme implementovat binární strom pomocí datové struktury LinkedList. Spolu s tím budeme implementovat i příkazy procházení, vyhledání uzlu a vložení uzlu do binárního stromu.

java regulární výraz pro

Implementace binárního stromu pomocí LinkedList

Algoritmus

Definujte třídu Node, která obsahuje tři atributy, konkrétně: data left a right. Zde levá představuje levého potomka uzlu a pravá představuje pravého potomka uzlu.

• Když je uzel vytvořen, data přejdou do datového atributu uzlu a levý i pravý uzel budou nastaveny na hodnotu null.
• Definujte jinou třídu, která má kořen atributu.
• Root představuje kořenový uzel stromu a inicializuje jej na hodnotu null.

vložit()přidá do stromu nový uzel:
• Zkontroluje, zda je kořen null, což znamená, že strom je prázdný. Přidá nový uzel jako root.
• V opačném případě přidá root do fronty.
• Proměnná uzel představuje aktuální uzel.
• Nejprve zkontroluje, zda má uzel levé a pravé potomky. Pokud ano, přidá oba uzly do fronty.
• Pokud levý potomek není přítomen, přidá nový uzel jako levého potomka.
• Pokud je přítomen levý uzel, přidá nový uzel jako pravého potomka.
v pořádku()zobrazí uzly stromu v pořadí.
• Projde celým stromem, vytiskne levé dítě následované kořenem a poté pravé dítě.

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

Výstup:

 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 

Operace binárních stromů

S binárním stromem lze provádět následující operace:

• Vložení
• Vymazání
• Vyhledávání
• Průjezd

Java program pro vložení uzlu do binárního stromu

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

Výstup:

q2 měsíce

 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 Program pro odstranění uzlu v Javě

Algoritmus

1. Začněte u kořene a najděte nejhlubší a nejpravější uzel v binárním stromu a uzel, který chceme odstranit.
2. Nahraďte data nejhlubšího pravého uzlu uzlem, který chcete odstranit.
3. Potom odstraňte nejhlubší uzel vpravo.

Zvažte následující obrázek.

DeleteNode.java

strojopis pro každého

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

Výstup:

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

Java program pro vyhledávání uzlu v binárním stromu

Algoritmus

• Definujte třídu Node, která má tři atributy a to: data left a right. Zde levá představuje levého potomka uzlu a pravá představuje pravého potomka uzlu.
• Když je uzel vytvořen, data přejdou do datového atributu uzlu a levý i pravý uzel budou nastaveny na hodnotu null.
• Definujte další třídu, která má dva atribut root a flag.
  1. Root představuje kořenový uzel stromu a inicializuje jej na hodnotu null.
  2. Příznak slouží ke kontrole, zda je daný uzel ve stromu přítomen či nikoliv. Zpočátku bude nastavena na hodnotu false.

searchNode()vyhledá konkrétní uzel v binárním stromu:
• Zkontroluje, zda je kořen null, což znamená, že strom je prázdný.
• Pokud strom není prázdný, porovná data temp s hodnotou. Pokud jsou stejné, nastaví příznak na hodnotu true a vrátí se.
• Projděte levý podstrom voláním searchNode() rekurzivně a zkontrolujte, zda je hodnota přítomna v levém podstromu.
• Projděte pravý podstrom voláním searchNode() rekurzivně a zkontrolujte, zda je hodnota přítomna v pravém podstromu.

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

Výstup:

 Element is present in the binary tree. 

Binární procházení stromů

Poznámka: Kromě výše uvedených tří přechodů existuje další pořadí přechodů, které se nazývá přechod hranicemi.

Java program pro procházení Inorder, Preorder a Postorder Traversal

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

Výstup:

 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 

Kromě výše uvedených operací můžeme provádět i operace jako velký uzel, nejmenší uzel a součet všech uzlů.

Java program pro nalezení největšího uzlu v binárním stromu

Největší Node.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)); } } 

Výstup:

jak starý je pete davidson

 Largest element in the binary tree: 99 

Program Java pro nalezení nejmenšího uzlu v binárním stromu

Algoritmus

1. Definujte třídu Node, která má tři atributy, jmenovitě: data, left a right. Zde levá představuje levého potomka uzlu a pravá představuje pravého potomka uzlu.
2. Když je uzel vytvořen, data přejdou do datového atributu uzlu a levý i pravý uzel budou nastaveny na hodnotu null.
3. Definujte jinou třídu, která má kořen atributu.
   Vykořenitreprezentovat kořenový uzel stromu a inicializovat jej na null.

nejmenší prvek()zjistí nejmenší uzel v binárním stromu:
1. Kontroluje, zda root je null , což znamená, že strom je prázdný.
2. Pokud strom není prázdný, definujte proměnnou min, která bude ukládat data temp.
3. Zjistěte minimální uzel v levém podstromu rekurzivním voláním smallElement(). Uložte tuto hodnotu do leftMin. Porovnejte hodnotu min s leftMin a uložte minimálně dvě do min.
4. Zjistěte minimální uzel v pravém podstromu rekurzivním voláním smallElement(). Uložte tuto hodnotu do rightMin. Porovnejte hodnotu min s rightMin a uložte maximum ze dvou do min.
5. Na konci bude min obsahovat nejmenší uzel v binárním stromu.

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

Výstup:

 Smallest element in the binary tree: 1 

Java program pro nalezení maximální šířky binárního stromu

Algoritmus

1. Definujte třídu Node, která má tři atributy a to: data left a right. Zde levá představuje levého potomka uzlu a pravá představuje pravého potomka uzlu.
2. Když je uzel vytvořen, data přejdou do datového atributu uzlu a levý i pravý uzel budou nastaveny na hodnotu null.
3. Definujte jinou třídu, která má kořen atributu.
   Vykořenitpředstavuje kořenový uzel stromu a inicializuje jej na hodnotu null.

1. Proměnná maxWidth uloží maximální počet uzlů přítomných v jakékoli úrovni.
2. Fronta se používá k procházení binárním stromem po úrovni.
3. Zkontroluje, zda je kořen null, což znamená, že strom je prázdný.
4. Pokud ne, přidejte kořenový uzel do fronty. Proměnná nodesInLevel sleduje počet uzlů v každé úrovni.
5. Pokud nodesInLevel > 0, odeberte uzel z přední části fronty a přidejte jeho levý a pravý potomek do fronty. Pro první iteraci bude uzel 1 odstraněn a jeho podřízené uzly 2 a 3 budou přidány do fronty. Ve druhé iteraci bude uzel 2 odstraněn, jeho potomci 4 a 5 budou přidáni do fronty a tak dále.
6. MaxWidth uloží max(maxWidth, nodesInLevel). V každém daném okamžiku tedy bude představovat maximální počet uzlů.
7. Toto bude pokračovat, dokud neprojdou všechny úrovně stromu.

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

Výstup:

 Maximum width of the binary tree: 4