TechCodeview

Binärt träd är en icke-linjär datastruktur av trädtyp som huvudsakligen används för sortering och sökning eftersom de lagrar data i hierarkisk form. I det här avsnittet kommer vi att lära oss implementering av binär träddatastruktur i Java . Ger också en kort beskrivning av binär träddatastruktur.

Binärt träd

Ett träd där varje nod (förälder) har högst två barnnoder (vänster och höger) kallas binärt träd. Den översta noden kallas rotnoden. I ett binärt träd innehåller en nod data och pekaren (adressen) till vänster och höger undernod.

De höjd av ett binärt träd är antal kanter mellan trädets rot och dess längsta (djupaste) blad. Om trädet är tömma , höjden är 0 . Höjden på noden betecknas med h .

Höjden på ovanstående binära träd är 2.

Vi kan beräkna antalet löv och nod genom att använda följande formel.

omvänd sträng i java

• Maximalt antal lövnoder är ett binärt träd: 2^h
• Maximalt antal noder är ett binärt träd: 2^h+1-1

Där, h är höjden på binärt träd.

Exempel på binärt träd

Typer av binära träd

Det finns följande typer av binära träd i datastrukturen:

1. Fullständigt/ strikt binärt träd
2. Komplett binärt träd
3. Perfekt binärt träd
4. Balansera binärt träd
5. Rotat binärt träd
6. Degenererat/patologiskt binärt träd
7. Förlängt binärt träd
8. Skevt binärt träd
   1. Vänstersnedvridet binärt träd
   2. Höger-sned binärt träd
9. Gängat binärt träd
   1. Enkeltrådigt binärt träd
   2. Dubbeltrådigt binärt träd

Binary Tree Implementation i Java

Det finns många sätt att implementera binära träd. I det här avsnittet kommer vi att implementera binärt träd med hjälp av LinkedList-datastruktur. Tillsammans med det kommer vi också att implementera korsningsorder, genomsökning av en nod och infoga en nod i ett binärt träd.

skillnaden mellan företag och företag

Implementering av binärt träd med hjälp av LinkedList

Algoritm

Definiera nodklass som innehåller tre attribut nämligen: data vänster och höger. Här representerar vänster nodens vänstra barn och höger representerar nodens högra barn.

• När en nod skapas kommer data att skickas till nodens dataattribut och både vänster och höger kommer att ställas in på null.
• Definiera en annan klass som har en attributrot.
• Rot representerar trädets rotnod och initialisera den till null.

Föra in()kommer att lägga till en ny nod i trädet:
• Den kontrollerar om roten är null, vilket betyder att trädet är tomt. Det kommer att lägga till den nya noden som root.
• Annars kommer det att lägga till root till kön.
• Den variabla noden representerar den aktuella noden.
• Först kontrollerar den om en nod har ett vänster och höger barn. Om ja, kommer det att lägga till båda noderna i kön.
• Om det vänstra barnet inte är närvarande kommer det att lägga till den nya noden som det vänstra barnet.
• Om den vänstra är närvarande, kommer den att lägga till den nya noden som det högra barnet.
i ordning()kommer att visa noder i trädet på ett inordnat sätt.
• Den korsar hela trädet och skriver sedan ut vänster barn följt av rot och sedan följt av höger 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ära trädoperationer

Följande operationer kan utföras på ett binärt träd:

• Införande
• Radering
• Sök
• Traversering

Java-program för att infoga en nod i binärt träd

BinaryTreeInsert.java

print array i 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 för att ta bort en nod i Java

Algoritm

1. Börja vid roten, hitta den djupaste och längst till höger noden i binärt träd och nod som vi vill ta bort.
2. Ersätt den djupaste nodens data längst till höger med noden som ska raderas.
3. Ta sedan bort den djupaste noden längst till höger.

Betrakta följande figur.

Ta bortNode.java

fackförbund vs fackförbund alla

 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 för att söka efter en nod i binärt träd

Algoritm

• Definiera nodklass som har tre attribut nämligen: data vänster och höger. Här representerar vänster nodens vänstra barn och höger representerar nodens högra barn.
• När en nod skapas kommer data att skickas till nodens dataattribut och både vänster och höger kommer att ställas in på null.
• Definiera en annan klass som har två attribut rot och flagga.
  1. Root representerar trädets rotnod och initierar den till null.
  2. Flaggan kommer att användas för att kontrollera om den givna noden finns i trädet eller inte. Inledningsvis kommer det att vara inställt på falskt.

searchNode()kommer att söka efter en viss nod i det binära trädet:
• Den kontrollerar om roten är null, vilket betyder att trädet är tomt.
• Om trädet inte är tomt kommer det att jämföra temps data med värde. Om de är lika, kommer den att ställa in flaggan på sant och återgå.
• Gå igenom vänster underträd genom att anropa searchNode() rekursivt och kontrollera om värdet finns i det vänstra underträdet.
• Gå igenom höger underträd genom att anropa searchNode() rekursivt och kontrollera om värdet finns i det högra underträdet.

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ädgenomgång

Obs: Förutom de tre ovanstående övergångarna finns det en annan korsningsordning som kallas gränsövergång.

Java Program to Traverse Inorder, Preorder, and 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 

Förutom ovanstående operationer kan vi också utföra operationer som stor nod, minsta nod och summan av alla noder.

Java-program för att hitta den största noden i binärt träd

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:

sträng java innehåller

 Largest element in the binary tree: 99 

Java-program för att hitta den minsta noden i binärt träd

Algoritm

1. Definiera nodklass som har tre attribut nämligen: data, vänster och höger. Här representerar vänster nodens vänstra barn och höger representerar nodens högra barn.
2. När en nod skapas kommer data att skickas till nodens dataattribut och både vänster och höger kommer att ställas in på null.
3. Definiera en annan klass som har en attributrot.
   Rotrepresentera rotnoden för trädet och initiera den till null.

smallestElement()kommer att ta reda på den minsta noden i binärt träd:
1. Den kontrollerar om roten är null , vilket betyder att trädet är tomt.
2. Om trädet inte är tomt, definiera en variabel min som lagrar temps data.
3. Ta reda på minimumnoden i det vänstra underträdet genom att anropa smallestElement() rekursivt. Lagra det värdet i leftMin. Jämför värdet på min med leftMin och spara minst två till min.
4. Ta reda på minimumnoden i höger underträd genom att anropa smallestElement() rekursivt. Lagra det värdet i rightMin. Jämför värdet på min med rightMin och lagra maxvärdet två till min.
5. I slutet kommer min att hålla den minsta noden i det binära trädet.

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 för att hitta den maximala bredden på ett binärt träd

Algoritm

1. Definiera nodklass som har tre attribut nämligen: data vänster och höger. Här representerar vänster nodens vänstra barn och höger representerar nodens högra barn.
2. När en nod skapas kommer data att skickas till nodens dataattribut och både vänster och höger kommer att ställas in på null.
3. Definiera en annan klass som har en attributrot.
   Rotrepresenterar trädets rotnod och initierar den till null.

1. Variabel maxWidth kommer att lagra det maximala antalet noder som finns på vilken nivå som helst.
2. Kön används för att korsa binärt träd nivåmässigt.
3. Den kontrollerar om roten är null, vilket betyder att trädet är tomt.
4. Om inte, lägg till rotnoden i kön. Variable nodesInLevel håller reda på antalet noder i varje nivå.
5. Om nodesInLevel > 0, ta bort noden från framsidan av kön och lägg till dess vänstra och högra underordnade i kön. För den första iterationen kommer nod 1 att tas bort och dess underordnade noder 2 och 3 kommer att läggas till i kön. I den andra iterationen kommer nod 2 att tas bort, dess barn 4 och 5 kommer att läggas till i kön och så vidare.
6. MaxWidth kommer att lagra max(maxWidth, nodesInLevel). Så, vid varje given tidpunkt, kommer det att representera det maximala antalet noder.
7. Detta kommer att fortsätta tills alla nivåer i trädet korsas.

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