TechCodeview

Binært træ er en trætype ikke-lineær datastruktur, der hovedsageligt bruges til sortering og søgning, fordi de gemmer data i hierarkisk form. I dette afsnit lærer vi implementering af binær trædatastruktur i Java . Giver også en kort beskrivelse af binære trædatastruktur.

Binært træ

Et træ, hvor hver node (forælder) højst har to-under-knuder (venstre og højre), kaldes binært træ. Den øverste knude kaldes rodknuden. I et binært træ indeholder en node dataene og markøren (adressen) til venstre og højre underknudepunkt.

Det højde af et binært træ er antal kanter mellem træets rod og dets fjerneste (dybeste) blad. Hvis træet er tom , højden er 0 . Højden af ​​knudepunktet er angivet med h .

Højden af ​​ovenstående binære træ er 2.

Vi kan beregne antallet af blade og node ved at bruge følgende formel.

• Det maksimale antal bladknuder er et binært træ: 2^h
• Det maksimale antal noder er et binært træ: 2^h+1-1

Hvor h er højden af ​​binært træ.

Eksempel på binært træ

Typer af binære træer

Der er følgende typer binære træer i datastrukturen:

1. Fuldt/strengt binært træ
2. Komplet binært træ
3. Perfekt binært træ
4. Balance binært træ
5. Rodet binært træ
6. Degenereret/ patologisk binært træ
7. Udvidet binært træ
8. Skævt binært træ
   1. Venstreskævt binært træ
   2. Højreskævt binært træ
9. Binært træ med gevind
   1. Enkelt gevind binært træ
   2. Dobbelttrådet binært træ

Binært træimplementering i Java

Der er mange måder at implementere binært træ på. I dette afsnit vil vi implementere binært træ ved hjælp af LinkedList-datastruktur. Sammen med det vil vi også implementere gennemløbsordenerne, søge i en node og indsætte en node i et binært træ.

Implementering af binært træ ved hjælp af LinkedList

Algoritme

Definer Node-klasse, der indeholder tre attributter, nemlig: data venstre og højre. Her repræsenterer venstre knudepunktets venstre underordnede, og højre repræsenterer knudepunktets højre underordnede.

• Når en node er oprettet, vil data overføres til nodens dataattribut, og både venstre og højre vil blive sat til null.
• Definer en anden klasse, der har en attributrod.
• Rod repræsenterer træets rodknude og initialiser den til null.

indsæt()vil tilføje en ny node til træet:
• Den kontrollerer, om roden er nul, hvilket betyder, at træet er tomt. Det vil tilføje den nye node som root.
• Ellers vil det tilføje rod til køen.
• Den variable knude repræsenterer den aktuelle knude.
• Først tjekker den, om en node har et venstre og højre underordnet. Hvis ja, tilføjer den begge noder til køen.
• Hvis det venstre barn ikke er til stede, tilføjer det den nye node som det venstre barn.
• Hvis venstre er til stede, tilføjer den den nye node som det højre barn.
inorder()vil vise noder i træet på uordentligt vis.
• Den krydser hele træet og udskriver derefter venstre barn efterfulgt af rod og derefter efterfulgt af højre barn.

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

Produktion:

 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 

Binære træoperationer

Følgende operationer kan udføres på et binært træ:

• Indskud
• Sletning
• Søg
• Traversering

Java-program til at indsætte en node i binært træ

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

Produktion:

 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 til at slette en node i Java

Algoritme

1. Start ved roden, find den dybeste og længst til højre knude i binært træ og knude, som vi ønsker at slette.
2. Erstat den dybeste node længst til højre med den node, der skal slettes.
3. Slet derefter den dybeste knude længst til højre.

Overvej følgende figur.

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

Produktion:

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

Java-program til at søge en node i binært træ

Algoritme

• Definer Node-klasse, som har tre attributter, nemlig: data venstre og højre. Her repræsenterer venstre knudepunktets venstre underordnede, og højre repræsenterer knudepunktets højre underordnede.
• Når en node er oprettet, vil data overføres til nodens dataattribut, og både venstre og højre vil blive sat til null.
• Definer en anden klasse, som har to attributter root og flag.
  1. Rod repræsenterer træets rodknude og initialiserer det til null.
  2. Flaget vil blive brugt til at kontrollere, om den givne node er til stede i træet eller ej. I første omgang vil den være indstillet til falsk.

searchNode()vil søge efter en bestemt node i det binære træ:
• Den kontrollerer, om roden er nul, hvilket betyder, at træet er tomt.
• Hvis træet ikke er tomt, vil det sammenligne temps data med værdi. Hvis de er ens, vil det sætte flaget til sand og returnere.
• Gå gennem venstre undertræ ved at kalde searchNode() rekursivt og kontroller, om værdien er til stede i venstre undertræ.
• Gå gennem højre undertræ ved at kalde searchNode() rekursivt og kontroller, om værdien er til stede i det højre undertræ.

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

Produktion:

 Element is present in the binary tree. 

Binær trægennemgang

Bemærk: Bortset fra de tre ovennævnte gennemløb, er der en anden gennemkøringsrækkefølge, der kaldes grænseoverskridelse.

Java-program til at krydse Inorder, Preorder og 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(); } } 

Produktion:

 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 

Udover ovenstående operationer kan vi også udføre operationer såsom stor node, mindste node og summen af ​​alle noder.

Java-program til at finde den største node i binært træ

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

Produktion:

solrig deol alder

 Largest element in the binary tree: 99 

Java-program til at finde den mindste node i binært træ

Algoritme

1. Definer Node-klasse, som har tre attributter, nemlig: data, venstre og højre. Her repræsenterer venstre knudepunktets venstre underordnede, og højre repræsenterer knudepunktets højre underordnede.
2. Når en node er oprettet, vil data overføres til nodens dataattribut, og både venstre og højre vil blive sat til null.
3. Definer en anden klasse, som har en attributrod.
   Rodrepræsentere træets rodknude og initialisere det til null.

smallestElement()vil finde ud af den mindste node i binært træ:
1. Den tjekker om root er nul , hvilket betyder, at træet er tomt.
2. Hvis træet ikke er tomt, skal du definere en variabel min, der gemmer temps data.
3. Find ud af minimumsknuden i venstre undertræ ved at kalde smallestElement() rekursivt. Gem denne værdi i leftMin. Sammenlign værdien af ​​min med leftMin og gem minimum to til min.
4. Find ud af minimumsknuden i højre undertræ ved at kalde smallestElement() rekursivt. Gem denne værdi i rightMin. Sammenlign værdien af ​​min med rightMin og gem maksimum to til min.
5. Til sidst vil min holde den mindste node i det binære træ.

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

Produktion:

 Smallest element in the binary tree: 1 

Java-program til at finde den maksimale bredde af et binært træ

Algoritme

1. Definer Node-klasse, som har tre attributter, nemlig: data venstre og højre. Her repræsenterer venstre knudepunktets venstre underordnede, og højre repræsenterer knudepunktets højre underordnede.
2. Når en node er oprettet, vil data overføres til nodens dataattribut, og både venstre og højre vil blive sat til null.
3. Definer en anden klasse, som har en attributrod.
   Rodrepræsenterer træets rodknude og initialiserer det til null.

1. Variabel maxWidth vil gemme det maksimale antal noder til stede på ethvert niveau.
2. Køen bruges til at krydse binært træ niveau-mæssigt.
3. Den kontrollerer, om roden er nul, hvilket betyder, at træet er tomt.
4. Hvis ikke, skal du tilføje rodnoden til køen. Variable nodesInLevel holder styr på antallet af noder i hvert niveau.
5. Hvis nodesInLevel > 0, skal du fjerne noden fra forsiden af ​​køen og tilføje dens venstre og højre underordnede til køen. For den første iteration vil node 1 blive fjernet, og dens underordnede noder 2 og 3 vil blive tilføjet til køen. I den anden iteration vil node 2 blive fjernet, dens børn 4 og 5 vil blive tilføjet til køen og så videre.
6. MaxWidth vil gemme max(maxWidth, nodesInLevel). Så på ethvert givet tidspunkt vil det repræsentere det maksimale antal noder.
7. Dette vil fortsætte, indtil alle træets niveauer er krydset.

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

Produktion:

 Maximum width of the binary tree: 4