Inzeráty

Strom představuje uzly spojeny hranami. Budeme konkrétně diskutovat o binárním stromu nebo binárním vyhledávacím stromu.

binární strom je speciální datastruktura používaná pro účely ukládání dat. Binární strom má zvláštní podmínku, že každý uzel může mít maximálně dvě děti., Binární strom má výhody jak uspořádaného pole, tak propojeného seznamu, protože vyhledávání je stejně rychlé jako v tříděném poli a operace vložení nebo odstranění jsou stejně rychlé jako v propojeném seznamu.

důležité pojmy

následující jsou důležité pojmy týkající se stromu.

  • Path-Path označuje posloupnost uzlů podél okrajů stromu.

  • Root-uzel v horní části stromu se nazývá root. Na strom je pouze jeden kořen a jedna cesta od kořenového uzlu k libovolnému uzlu.,

  • Parent – libovolný uzel kromě kořenového uzlu má jeden okraj směrem nahoru k uzlu zvanému parent.

  • dítě-uzel pod daným uzlem spojeným jeho okrajem směrem dolů se nazývá jeho podřízený uzel.

  • Leaf-uzel, který nemá žádný dětský uzel, se nazývá Leaf node.

  • Subtree-Subtree představuje potomky uzlu.

  • Visiting-Visiting odkazuje na kontrolu hodnoty uzlu, když je ovládání na uzlu.

  • Křížení − Křížení znamená, procházející uzly v určitém pořadí.,

  • úrovně-Úroveň uzlu představuje generování uzlu. Pokud je kořenový uzel na úrovni 0, pak je jeho další dětský uzel na úrovni 1, jeho vnouče je na úrovni 2 a tak dále.

  • keys-Key představuje hodnotu uzlu, na jehož základě má být pro uzel provedena vyhledávací operace.

reprezentace binárního vyhledávacího stromu

binární vyhledávací strom vykazuje zvláštní chování. Levé dítě uzlu musí mít hodnotu menší než hodnota jeho rodiče a pravé dítě uzlu musí mít hodnotu větší než jeho mateřská hodnota.,

budeme implementovat strom pomocí uzlu objektu a jejich připojení pomocí odkazů.

stromový uzel

kód pro zápis stromového uzlu by byl podobný tomu, co je uvedeno níže. Má datovou část a odkazy na její levé a pravé podřízené uzly.

struct node { int data; struct node *leftChild; struct node *rightChild;};

ve stromu všechny uzly sdílejí společný konstrukt.

BST Základní Operace

základní operace, které lze provádět na binární vyhledávací strom datová struktura, jsou následující −

  • Vložit − Vloží prvek na stromě/vytvořit strom.,

  • vyhledávání-vyhledá prvek ve stromu.

  • Předobjednávka Traversal-prochází stromem předobjednávkovým způsobem.

  • Inorder Traversal-prochází strom v pořadí způsobem.

  • Postorder Traversal-prochází strom v post-order způsobem.

naučíme se vytvářet (vkládat do) stromovou strukturu a hledat datovou položku ve stromu v této kapitole. O metodách procházení stromů se dozvíme v nadcházející kapitole.

vložit operaci

první vložení vytvoří strom., Poté, kdykoli má být prvek vložen, nejprve vyhledejte jeho správné umístění. Začněte hledat z kořenového uzlu, pak pokud jsou data menší než hodnota klíče, vyhledejte prázdné místo v levém podstromu a vložte data. V opačném případě vyhledejte prázdné místo v pravém podstromu a vložte data.,

Algoritmus

If root is NULL then create root nodereturnIf root exists then compare the data with node.data while until insertion position is located If data is greater than node.data goto right subtree else goto left subtree endwhile insert dataend If

Provedení

provádění li vložit funkce by měla vypadat takto.

Hledání Operace

vždy, když je prvek, které mají být prohledány, začít hledání z kořenového uzlu, pak v případě, že dat je menší než hodnota klíče, hledání prvku v levém podstromu. V opačném případě vyhledejte prvek v pravém podstromu. Postupujte podle stejného algoritmu pro každý uzel.

algoritmus 

If root.data is equal to search.data return rootelse while data not found If data is greater than node.data goto right subtree else goto left subtree If data found return node endwhile return data not found end if

implementace tohoto algoritmu by měla vypadat takto.,

Chcete-li vědět o implementaci struktury dat binárního vyhledávacího stromu, klikněte zde.

Inzeráty