TechCodeview

Dvejetainis medis yra medžio tipo nelinijinė duomenų struktūra, kuri daugiausia naudojama rūšiavimui ir paieškai, nes saugo duomenis hierarchine forma. Šiame skyriuje mes išmoksime dvejetainio medžio duomenų struktūros įdiegimas Java . Taip pat pateikiamas trumpas dvejetainio medžio duomenų struktūros aprašymas.

Dvejetainis medis

Medis, kuriame kiekvienas mazgas (pagrindinis) turi daugiausia dviejų antrinių mazgų (kairėje ir dešinėje), vadinamas dvejetainiu medžiu. Viršutinis mazgas vadinamas šakniniu mazgu. Dvejetainiame medyje mazge yra kairiojo ir dešiniojo antrinio mazgo duomenys ir rodyklė (adresas).

The aukščio dvejetainio medžio yra kraštų skaičius tarp medžio šaknų ir jo tolimiausias (giliausias) lapas. Jei medis yra tuščia , aukštis yra 0 . Mazgo aukštis žymimas h .

Aukščiau pateikto dvejetainio medžio aukštis yra 2.

Lapų ir mazgo skaičių galime apskaičiuoti naudodami šią formulę.

np.kur

• Didžiausias lapų mazgų skaičius yra dvejetainis medis: 2^h
• Didžiausias mazgų skaičius yra dvejetainis medis: 2^h+1-1

Kur, h yra dvejetainio medžio aukštis.

Dvejetainio medžio pavyzdys

Dvejetainių medžių rūšys

Duomenų struktūroje yra šie dvejetainio medžio tipai:

1. Visas / griežtai dvejetainis medis
2. Pilnas dvejetainis medis
3. Tobulas dvejetainis medis
4. Subalansuokite dvejetainį medį
5. Įsišaknijęs dvejetainis medis
6. Išsigimęs/ patologinis dvejetainis medis
7. Išplėstas dvejetainis medis
8. Iškreiptas dvejetainis medis
   1. Kairėn pakreiptas dvejetainis medis
   2. Dešiniuoju kampu dvejetainis medis
9. Srieginis dvejetainis medis
   1. Vieno sriegio dvejetainis medis
   2. Dviejų sriegių dvejetainis medis

Dvejetainio medžio diegimas Java

Yra daug būdų, kaip įgyvendinti dvejetainį medį. Šiame skyriuje mes įdiegsime dvejetainį medį naudodami LinkedList duomenų struktūrą. Kartu su juo įgyvendinsime ir perėjimo nurodymus, ieškodami mazgo ir įterpdami mazgą į dvejetainį medį.

java eilutės ilgis

Dvejetainio medžio įgyvendinimas naudojant LinkedList

Algoritmas

Apibrėžkite Mazgo klasę, kurią sudaro trys atributai: duomenys kairėje ir dešinėje. Čia kairėje yra kairysis mazgo vaikas, o dešinėje - dešinysis mazgo vaikas.

• Sukūrus mazgą, duomenys bus perduoti mazgo duomenų atributui, o kairėje ir dešinėje bus nustatyta nulinė vertė.
• Apibrėžkite kitą klasę, kuri turi atributo šaknį.
• Šaknis žymi šakninį medžio mazgą ir inicijuoja jį į nulį.

Įdėti()pridės naują mazgą prie medžio:
• Ji patikrina, ar šaknis yra nulinė, o tai reiškia, kad medis tuščias. Tai pridės naują mazgą kaip root.
• Priešingu atveju jis pridės šaknį prie eilės.
• Kintamasis mazgas reiškia dabartinį mazgą.
• Pirmiausia patikrinama, ar mazgas turi kairįjį ir dešinįjį vaikus. Jei taip, abu mazgai bus įtraukti į eilę.
• Jei kairiojo vaiko nėra, naujas mazgas bus pridėtas kaip kairysis vaikas.
• Jei yra kairysis, naujas mazgas bus pridėtas kaip dešinysis antrinis.
inorder ()bus rodomi medžio mazgai netvarkingai.
• Jis kerta visą medį, tada išspausdina kairįjį vaiką, po kurio seka šaknis, po to seka dešinysis vaikas.

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

Išvestis:

 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 

Dvejetainio medžio operacijos

Su dvejetainiu medžiu galima atlikti šias operacijas:

• Įdėjimas
• Ištrynimas
• Paieška
• Perėjimas

Java programa, skirta įterpti mazgą į dvejetainį medį

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

Išvestis:

konvertuojant eilutę į int

 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 programa, skirta pašalinti mazgą Java

Algoritmas

1. Pradėdami nuo šaknies, suraskite giliausią ir dešinįjį dvejetainio medžio mazgą ir mazgą, kurį norime ištrinti.
2. Pakeiskite giliausio dešiniojo mazgo duomenis mazgu, kurį reikia ištrinti.
3. Tada ištrinkite giliausią dešinįjį mazgą.

Apsvarstykite toliau pateiktą paveikslą.

DeleteNode.java

abėcėlė pagal skaičius

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

Išvestis:

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

Java programa, skirta ieškoti mazgo dvejetainiame medyje

Algoritmas

• Apibrėžkite Mazgo klasę, kuri turi tris atributus: duomenis kairėje ir dešinėje. Čia kairėje yra kairysis mazgo vaikas, o dešinėje - dešinysis mazgo vaikas.
• Sukūrus mazgą, duomenys bus perduoti mazgo duomenų atributui, o kairėje ir dešinėje bus nustatyta nulinė vertė.
• Apibrėžkite kitą klasę, kuri turi du atributo šaknį ir vėliavėlę.
  1. Šaknis žymi šakninį medžio mazgą ir inicijuoja jį į nulį.
  2. Vėliava bus naudojama patikrinti, ar nurodytas mazgas yra medyje, ar ne. Iš pradžių jis bus nustatytas į false.

searchNode()ieškos konkretaus mazgo dvejetainiame medyje:
• Ji patikrina, ar šaknis yra nulinė, o tai reiškia, kad medis tuščias.
• Jei medis nėra tuščias, jis palygins temp duomenis su verte. Jei jie yra lygūs, vėliavėlė bus nustatyta į teisingą ir grįš.
• Pereikite kairįjį pomedį, rekursyviai iškviesdami searchNode() ir patikrinkite, ar reikšmė yra kairiajame pomedyje.
• Pereikite dešinįjį pomedį, rekursyviai iškviesdami searchNode() ir patikrinkite, ar reikšmė yra dešiniajame pomedyje.

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

Išvestis:

 Element is present in the binary tree. 

Dvejetainis medžio perėjimas

Pastaba: Išskyrus pirmiau nurodytus tris perėjimus, yra ir kita važiavimo tvarka, vadinama sienų perėjimu.

„Java“ programa, skirta eiti į eiliškumą, išankstinį užsakymą ir postorder perėjimą

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

Išvestis:

 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 

Be minėtų operacijų, taip pat galime atlikti tokias operacijas kaip didelis mazgas, mažiausias mazgas ir visų mazgų suma.

„Java“ programa, skirta rasti didžiausią dvejetainio medžio mazgą

DidžiausiasNode.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)); } } 

Išvestis:

ryšys java mysql

 Largest element in the binary tree: 99 

Java programa, skirta rasti mažiausią mazgą dvejetainiame medyje

Algoritmas

1. Apibrėžkite Mazgo klasę, kuri turi tris atributus: duomenis, kairę ir dešinę. Čia kairėje yra kairysis mazgo vaikas, o dešinėje - dešinysis mazgo vaikas.
2. Sukūrus mazgą, duomenys bus perduoti mazgo duomenų atributui, o kairėje ir dešinėje bus nustatyta nulinė vertė.
3. Apibrėžkite kitą klasę, kurios atributo šaknis.
   Šaknisreiškia medžio šakninį mazgą ir inicijuoja jį į nulį.

mažiausias elementas ()sužinos mažiausią dvejetainio medžio mazgą:
1. Ji tikrina, ar šaknis yra nulinė , o tai reiškia, kad medis tuščias.
2. Jei medis nėra tuščias, apibrėžkite kintamąjį min, kuriame bus saugomi temp duomenys.
3. Išsiaiškinkite minimalų mazgą kairiajame pomedyje, rekursyviai iškviesdami smallestElement(). Išsaugokite šią reikšmę leftMin. Palyginkite min reikšmę su leftMin ir išsaugokite mažiausiai nuo dviejų iki min.
4. Sužinokite mažiausią dešiniojo pomedžio mazgą rekursyviai iškviesdami smallestElement(). Išsaugokite šią vertę dešinėje min. Palyginkite min reikšmę su rightMin ir išsaugokite daugiausia nuo dviejų iki min.
5. Pabaigoje min bus mažiausias dvejetainio medžio mazgas.

MažiausiasNode.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)); } } 

Išvestis:

 Smallest element in the binary tree: 1 

Java programa, skirta rasti didžiausią dvejetainio medžio plotį

Algoritmas

1. Apibrėžkite Mazgo klasę, kuri turi tris atributus: duomenis kairėje ir dešinėje. Čia kairėje yra kairysis mazgo vaikas, o dešinėje - dešinysis mazgo vaikas.
2. Sukūrus mazgą, duomenys bus perduoti mazgo duomenų atributui, o kairėje ir dešinėje bus nustatyta nulinė vertė.
3. Apibrėžkite kitą klasę, kurios atributo šaknis.
   Šaknisreiškia šakninį medžio mazgą ir inicijuoja jį į nulį.

1. Kintamasis maxWidth išsaugos maksimalų bet kuriame lygyje esančių mazgų skaičių.
2. Eilė naudojama peržengiant dvejetainį medį lygiu.
3. Ji patikrina, ar šaknis yra nulinė, o tai reiškia, kad medis tuščias.
4. Jei ne, pridėkite šakninį mazgą į eilę. Kintamasis nodesInLevel seka mazgų skaičių kiekviename lygyje.
5. Jei nodesInLevel > 0, pašalinkite mazgą iš eilės priekio ir į eilę įtraukite kairįjį ir dešinįjį antrinį elementą. Pirmosios iteracijos metu 1 mazgas bus pašalintas, o jo antriniai mazgai 2 ir 3 bus įtraukti į eilę. Antroje iteracijoje 2 mazgas bus pašalintas, jo vaikai 4 ir 5 bus įtraukti į eilę ir pan.
6. MaxWidth išsaugos maks.(maks. plotis, nodesInLevel). Taigi, bet kuriuo momentu jis bus didžiausias mazgų skaičius.
7. Tai tęsis tol, kol bus pereiti visi medžio lygiai.

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

Išvestis:

 Maximum width of the binary tree: 4