binary search tree java implementation code examples
Ta vadnica zajema binarno drevo iskanja v Javi. Naučili se boste ustvariti BST, vstaviti, odstraniti in iskati element, preiti in implementirati BST v Javi:
Binarno drevo iskanja (v nadaljnjem besedilu BST) je vrsta binarnega drevesa. Lahko ga definiramo tudi kot binarno drevo, ki temelji na vozlišču. BST se imenuje tudi 'Urejeno binarno drevo'. V BST imajo vsa vozlišča v levem poddrevesu vrednosti, ki so manjše od vrednosti korenskega vozlišča.
Podobno imajo vsa vozlišča desnega poddrevesa BST vrednosti, ki so večje od vrednosti korenskega vozlišča. Ta vrstni red vozlišč mora veljati tudi za posamezna poddrevesa.
=> Obiščite tukaj za ekskluzivno serijo vadnic Java.
Kaj se boste naučili:
- Binarno drevo iskanja v Javi
- Zaključek
Binarno drevo iskanja v Javi
BST ne dovoljuje podvojenih vozlišč.
Spodnji diagram prikazuje predstavitev BST:
Zgoraj je prikazan vzorec BST. Vidimo, da je 20 korensko vozlišče tega drevesa. Levo poddrevo ima vse vrednosti vozlišč, ki so manjše od 20. Desno poddrevo ima vsa vozlišča, ki so večja od 20. Lahko rečemo, da zgornje drevo izpolnjuje lastnosti BST.
Struktura podatkov BST velja za zelo učinkovito v primerjavi z nizi in povezanim seznamom, ko gre za vstavljanje / brisanje in iskanje elementov.
BST potrebuje čas O (log n) za iskanje elementa. Ko so elementi razvrščeni, se pri iskanju elementa na vsakem koraku zavrže polovica poddrevesa. To postane mogoče, ker lahko zlahka določimo grobo lokacijo elementa, ki ga želimo iskati.
Podobno so operacije vstavljanja in brisanja učinkovitejše v BST. Ko želimo vstaviti nov element, približno vemo, v katero poddrevo (levo ali desno) bomo vstavili element.
Ustvarjanje binarnega drevesa iskanja (BST)
Glede na vrsto elementov moramo zgraditi BST.
Naredimo to, kot je prikazano spodaj:
Podana matrika: 45, 10, 7, 90, 12, 50, 13, 39, 57
Najprej upoštevajmo zgornji element, tj.45 kot korensko vozlišče. Od tod bomo nadaljevali z ustvarjanjem BST z upoštevanjem že obravnavanih lastnosti.
Če želite ustvariti drevo, bomo primerjali vsak element v matriki s korenom. Nato bomo element postavili na ustrezen položaj v drevesu.
Celoten postopek ustvarjanja BST je prikazan spodaj.

Operacije binarnega drevesa iskanja
BST podpira različne operacije. Naslednja tabela prikazuje metode, ki jih BST podpira v Javi. Vsako od teh metod bomo obravnavali posebej.
Metoda / delovanje | Opis |
---|---|
Vstavi | BST dodajte element, tako da ne kršite lastnosti BST. |
Izbriši | Odstranite dano vozlišče iz BST. Vozlišče je lahko korensko vozlišče, nelistno ali listno vozlišče. |
Iskanje | V BST poiščite lokacijo danega elementa. Ta operacija preveri, ali drevo vsebuje navedeni ključ. |
Vstavite element v BST
Element se v BST vedno vstavi kot listno vozlišče.
Spodaj so navedeni koraki za vstavljanje elementa.
- Začnite od korena.
- Primerjajte element, ki ga želite vstaviti, s korenskim vozliščem. Če je manj kot root, prehodite levo ali desno poddrevo.
- Prehodite poddrevo do konca želenega poddrevesa. Vozlišče vstavite v ustrezno poddrevo kot listno vozlišče.
Poglejmo ponazoritev vstavljanja BST.
Razmislite o naslednjem BST in vstavimo element 2 v drevo.


Postopek vstavljanja za BST je prikazan zgoraj. Na sliki (1) prikazujemo pot, ki jo prehodimo, da vstavimo element 2 v BST. Prikazali smo tudi pogoje, ki se preverijo na vsakem vozlišču. Kot rezultat rekurzivne primerjave je element 2 vstavljen kot desni podrejeni 1, kot je prikazano na sliki (2).
Iskalna operacija v BST
Za iskanje, ali je element prisoten v BST, spet začnemo od korena in nato prehodimo levo ali desno poddrevo, odvisno od tega, ali je element, ki ga želimo iskati, manjši ali večji od korenskega.
Spodaj so navedeni koraki, ki jih moramo upoštevati.
- Primerjajte element, ki ga želite iskati, s korenskim vozliščem.
- Če je ključ (element, ki ga je treba iskati) = root, vrni korensko vozlišče.
- Drugače, če je ključno
- Drugače preči desno poddrevo.
- Ponavljajoče se primerjajte elemente poddrevesa, dokler ne najdete ključa ali konec drevesa.
Ponazorimo iskalno operacijo s primerom. Upoštevajte, da moramo poiskati ključ = 12.
Na spodnji sliki bomo zasledili pot, po kateri smo iskali ta element.
Kot je prikazano na zgornji sliki, najprej primerjamo ključ s korenskim. Ker je ključ večji, prehodimo desno poddrevo. V desnem poddrevesu znova primerjamo ključ s prvim vozliščem v desnem poddrevesu.
Ugotovili smo, da je ključ manjši od 15. Torej se premaknemo v levo poddrevo vozlišča 15. Neposredno levo vozlišče 15 je 12, ki se ujema s ključem. Na tem mestu ustavimo iskanje in vrnemo rezultat.
Odstrani element z BST
Ko izbrišemo vozlišče iz BST, obstajajo tri možnosti, o katerih bomo razpravljali spodaj:
Vozlišče je listno vozlišče
Če je vozlišče, ki ga je treba izbrisati, vozlišče listov, potem lahko to vozlišče neposredno izbrišemo, saj nima podrejenih vozlišč. To je prikazano na spodnji sliki.
Kot je prikazano zgoraj, je vozlišče 12 listno vozlišče in ga je mogoče takoj izbrisati.
Vozlišče ima samo enega otroka
Ko moramo vozlišče z enim otrokom izbrisati, nato v vozlišču kopiramo vrednost otroka in nato otroka.
V zgornjem diagramu želimo izbrisati vozlišče 90, ki ima enega podrejenega 50. Torej vrednost 50 zamenjamo z 90 in nato izbrišemo vozlišče 90, ki je zdaj podrejeno vozlišče.
Vozlišče ima dva otroka
Če ima vozlišče, ki ga je treba izbrisati, dva podrejena sistema, ga nadomestimo z naslednjim (levo-korensko-desnim) naslednikom vozlišča ali preprosto izgovorimo minimalno vozlišče v desnem poddrevesu, če desno poddrevo vozlišča ni prazno. Vozlišče nadomestimo s tem najmanjšim vozliščem in ga izbrišemo.
V zgornjem diagramu želimo izbrisati vozlišče 45, ki je korensko vozlišče BST. Ugotovili smo, da desno poddrevo tega vozlišča ni prazno. Nato prehodimo desno poddrevo in ugotovimo, da je tukaj vozlišče 50 najmanjše vozlišče. Torej zamenjamo to vrednost namesto 45 in nato izbrišemo 45.
Če preverimo drevo, vidimo, da izpolnjuje lastnosti BST. Tako je bila zamenjava vozlišča pravilna.
Izvajanje binarnega drevesa iskanja (BST) v Javi
Naslednji program v Javi prikazuje predstavitev vseh zgornjih operacij BST z uporabo istega drevesa, kot je prikazano na sliki.
najboljši brezplačni pretvornik datotek za Windows 10
class BST_class { //node class that defines BST node class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } // BST root node Node root; // Constructor for BST =>initial empty tree BST_class(){ root = null; } //delete a node from BST void deleteKey(int key) { root = delete_Recursive(root, key); } //recursive delete function Node delete_Recursive(Node root, int key) { //tree is empty if (root == null) return root; //traverse the tree if (key root.key) //traverse right subtree root.right = delete_Recursive(root.right, key); else { // node contains only one child if (root.left == null) return root.right; else if (root.right == null) return root.left; // node has two children; //get inorder successor (min value in the right subtree) root.key = minValue(root.right); // Delete the inorder successor root.right = delete_Recursive(root.right, root.key); } return root; } int minValue(Node root) { //initially minval = root int minval = root.key; //find minval while (root.left != null) { minval = root.left.key; root = root.left; } return minval; } // insert a node in BST void insert(int key) { root = insert_Recursive(root, key); } //recursive insert function Node insert_Recursive(Node root, int key) { //tree is empty if (root == null) { root = new Node(key); return root; } //traverse the tree if (key root.key) //insert in the right subtree root.right = insert_Recursive(root.right, key); // return pointer return root; } // method for inorder traversal of BST void inorder() { inorder_Recursive(root); } // recursively traverse the BST void inorder_Recursive(Node root) { if (root != null) { inorder_Recursive(root.left); System.out.print(root.key + ' '); inorder_Recursive(root.right); } } boolean search(int key) { root = search_Recursive(root, key); if (root!= null) return true; else return false; } //recursive insert function Node search_Recursive(Node root, int key) // Base Cases: root is null or key is present at root if (root==null } class Main{ public static void main(String() args) { //create a BST object BST_class bst = new BST_class(); /* BST tree example 45 / 10 90 / / 7 12 50 */ //insert data into BST bst.insert(45); bst.insert(10); bst.insert(7); bst.insert(12); bst.insert(90); bst.insert(50); //print the BST System.out.println('The BST Created with input data(Left-root-right):'); bst.inorder(); //delete leaf node System.out.println('
The BST after Delete 12(leaf node):'); bst.deleteKey(12); bst.inorder(); //delete the node with one child System.out.println('
The BST after Delete 90 (node with 1 child):'); bst.deleteKey(90); bst.inorder(); //delete node with two children System.out.println('
The BST after Delete 45 (Node with two children):'); bst.deleteKey(45); bst.inorder(); //search a key in the BST boolean ret_val = bst.search (50); System.out.println('
Key 50 found in BST:' + ret_val ); ret_val = bst.search (12); System.out.println('
Key 12 found in BST:' + ret_val ); } }
Izhod:
Prehod drevesa binarnega iskanja (BST) v Javi
Drevo je hierarhična struktura, zato ga ne moremo linearno prečkati kot druge podatkovne strukture, kot so nizi. Vsako vrsto drevesa je treba prehoditi na poseben način, tako da so vsa njegova drevesa in vozlišča obiskana vsaj enkrat.
Glede na vrstni red, v katerem se v drevesu prečkajo korensko vozlišče, levo poddrevo in desno poddrevo, obstajajo določeni prečkanje, kot je prikazano spodaj:
- Notranji prehod
- Prehod po predhodnem naročilu
- Prehod PostOrder
Vse zgoraj omenjene poti uporabljajo tehniko, ki temelji na globini, tj.drevo se prečka globinsko.
Drevesa uporabljajo tudi tehniko širine najprej za prečkanje. Imenuje se pristop, ki uporablja to tehniko “Level Order” prehod.
V tem razdelku bomo prikazali vsako od prečk z uporabo BST-ja kot primer.
Pri BST, kot je prikazano na zgornjem diagramu, je prehod vrstnega reda za zgornje drevo:
Prehod vrstnega reda: 10 6 12 4 8
Notranji prehod
Pristop notranjega prečka je BST prečkal v vrstnem redu, Levo poddrevo => RootNode => Desno poddrevo . Prehod po vrstnem redu zagotavlja padajoče zaporedje vozlišč BST.
Algoritem InOrder (bstTree) za InOrder Traversal je podan spodaj.
- Prehodite levo poddrevo z uporabo InOrder (left_subtree)
- Obiščite korensko vozlišče.
- Prehodite desno poddrevo z uporabo InOrder (right_subtree)
Prehod v zgornjem drevesu je:
4 6 8 10 12
Kot je razvidno, je zaporedje vozlišč kot prehod po vrstnem redu v padajočem vrstnem redu.
Prehod po predhodnem naročilu
Pri preusmeritvi prednaročila najprej obišče koren, nato levo in desno drevo. Prehod po predhodnem naročilu ustvari kopijo drevesa. Uporablja se lahko tudi v drevesih izrazov za pridobitev izraza predpone.
Algoritem za prehod PreOrder (bst_tree) je podan spodaj:
- Obiščite korensko vozlišče
- Prehodite levo poddrevo s funkcijo PreOrder (left_subtree).
- Prehodite desno poddrevo s funkcijo PreOrder (desno_poddrevo).
Zgoraj navedeni prehod za BST je:
10 6 4 8 12
Prehod PostOrder
Prehod postOrder prečka BST v vrstnem redu: Levo poddrevo-> Desno poddrevo-> Root vozlišče . Prehod PostOrder se uporablja za brisanje drevesa ali pridobitev izraza postfix v primeru dreves izrazov.
Algoritem za prehod postOrder (bst_tree) je naslednji:
- Levo poddrevo prehodite s postOrder (left_subtree).
- Prehodite desno poddrevo s postOrder (desno_poddrevo).
- Obiščite korensko vozlišče
Prehod postOrder za zgornji primer BST je:
4 8 6 12 10
Nato bomo te poteze izvedli s tehniko globine prve pri implementaciji Jave.
//define node of the BST class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } //BST class class BST_class { // BST root node Node root; BST_class(){ root = null; } //PostOrder Traversal - Left:Right:rootNode (LRn) void postOrder(Node node) { if (node == null) return; // first traverse left subtree recursively postOrder(node.left); // then traverse right subtree recursively postOrder(node.right); // now process root node System.out.print(node.key + ' '); } // InOrder Traversal - Left:rootNode:Right (LnR) void inOrder(Node node) { if (node == null) return; //first traverse left subtree recursively inOrder(node.left); //then go for root node System.out.print(node.key + ' '); //next traverse right subtree recursively inOrder(node.right); } //PreOrder Traversal - rootNode:Left:Right (nLR) void preOrder(Node node) { if (node == null) return; //first print root node first System.out.print(node.key + ' '); // then traverse left subtree recursively preOrder(node.left); // next traverse right subtree recursively preOrder(node.right); } // Wrappers for recursive functions void postOrder_traversal() { postOrder(root); } void inOrder_traversal() { inOrder(root); } void preOrder_traversal() { preOrder(root); } } class Main{ public static void main(String() args) { //construct a BST BST_class tree = new BST_class(); /* 45 // \ 10 90 // \ 7 12 */ tree.root = new Node(45); tree.root.left = new Node(10); tree.root.right = new Node(90); tree.root.left.left = new Node(7); tree.root.left.right = new Node(12); //PreOrder Traversal System.out.println('BST => PreOrder Traversal:'); tree.preOrder_traversal(); //InOrder Traversal System.out.println('
BST => InOrder Traversal:'); tree.inOrder_traversal(); //PostOrder Traversal System.out.println('
BST => PostOrder Traversal:'); tree.postOrder_traversal(); } }
Izhod:
Pogosto zastavljena vprašanja
V # 1) Zakaj potrebujemo binarno drevo iskanja?
Odgovor : Način iskanja elementov v linearni podatkovni strukturi, kot so nizi z binarno tehniko iskanja, pri čemer je drevo hierarhična struktura, potrebujemo strukturo, ki jo lahko uporabimo za iskanje elementov v drevesu.
Tu pride do binarnega drevesa iskanja, ki nam pomaga pri učinkovitem iskanju elementov na sliki.
V # 2) Kakšne so lastnosti binarnega drevesa iskanja?
Odgovor : Binarno drevo iskanja, ki spada v kategorijo binarnega drevesa, ima naslednje lastnosti:
- Podatki, shranjeni v binarnem drevesu iskanja, so edinstveni. Ne dovoljuje podvojenih vrednosti.
- Vozlišča levega poddrevesa so manjša od korenskega vozlišča.
- Vozlišča desnega poddrevesa so večja od korenskega vozlišča.
V # 3) Kakšne so aplikacije binarnega drevesa iskanja?
Odgovor : Binarna iskalna drevesa lahko uporabimo za reševanje nekaterih neprekinjenih funkcij v matematiki. Iskanje podatkov v hierarhičnih strukturah je z binarnimi drevesi iskanja učinkovitejše. Z vsakim korakom iskanje zmanjšamo za polovico poddrevesa.
V # 4) Kakšna je razlika med binarnim drevesom in binarnim drevesom iskanja?
Odgovor: Binarno drevo je hierarhična drevesna struktura, v kateri ima lahko vsako vozlišče, znano kot nadrejeno, največ dva otroka. Binarno drevo iskanja izpolnjuje vse lastnosti binarnega drevesa in ima tudi svoje edinstvene lastnosti.
V binarnem drevesu iskanja leva poddrevesa vsebujejo vozlišča, ki so manjša ali enaka korenskemu vozlišču, desno poddrevo pa ima večja od korenskega vozlišča.
V # 5) Ali je binarno drevo iskanja edinstveno?
Odgovor : Binarno drevo iskanja spada v kategorijo binarnega drevesa. Edinstven je v smislu, da ne dovoljuje podvojenih vrednosti, prav tako pa so vsi njegovi elementi razvrščeni po posebnem vrstnem redu.
Zaključek
Drevesa binarnega iskanja so del kategorije binarnih dreves in se v glavnem uporabljajo za iskanje po hierarhičnih podatkih. Uporablja se tudi za reševanje nekaterih matematičnih problemov.
V tej vadnici smo videli izvajanje binarnega drevesa iskanja. Videli smo tudi različne operacije, izvedene na BST z njihovo ilustracijo, in tudi raziskali poti za BST.
=> Tukaj si oglejte preproste vadbene serije Java.
Priporočeno branje
- Binarno drevo iskanja C ++: Implementacija BST in operacije s primeri
- Binarni algoritem iskanja v Javi - implementacija in primeri
- Struktura podatkov binarnega drevesa v jeziku C ++
- Drevesa v jeziku C ++: osnovna terminologija, tehnike prečkanja in drevesne vrste C ++
- TreeMap v Javi - Vadnica z primeri Java TreeMap
- TreeSet v Javi: Vadnica s primeri programiranja
- JAVA Vadnica za začetnike: 100+ praktičnih Javnih video vadnic
- Povezani seznam v Javi - Implementacija povezanega seznama in primeri Java