ett binärt sökträd (BST) är ett träd där alla noder följer de nedan nämnda egenskaperna-
-
värdet på nyckeln i det vänstra Delträdet är mindre än värdet på dess överordnade (root) nods nyckel.
-
värdet på nyckeln till det högra delträdet är större än eller lika med värdet på dess överordnad (root) nods nyckel.,
således delar BST alla sina underträd i två segment; det vänstra delträdet och det högra delträdet och kan definieras som-
left_subtree (keys) < node (key) ≤ right_subtree (keys)
Representation
BST är en samling noder ordnade på ett sätt där de upprätthåller BST-egenskaper. Varje nod har en nyckel och ett associerat värde. När du söker, jämförs den önskade nyckeln med tangenterna i BST och om den hittas hämtas det associerade värdet.,
Följande är en bildrepresentation av BST −
vi noterar att rotnodnyckeln (27) har alla mindre värderade nycklar på det vänstra delträdet och de högre värderade nycklarna på det högra delträdet.
grundläggande funktioner
Följande är de grundläggande funktionerna i ett träd −
-
Search − söker ett element i ett träd.
-
infoga − infogar ett element i ett träd.
-
pre-order Traversal − Traverses ett träd på ett förbeställnings sätt.
-
i ordning korsar ett träd i ordning.,
-
Post-order Traversal − Traverses ett träd på ett post-order sätt.
nod
definiera en nod som har vissa data, referenser till dess vänstra och högra underordnade noder.
struct node { int data; struct node *leftChild; struct node *rightChild;};
sökfunktion
När ett element ska sökas, börja söka från rotnoden. Om data är mindre än nyckelvärdet, Sök efter elementet i den vänstra undertreen. Annars söker du efter elementet i rätt underträd. Följ samma algoritm för varje nod.,
algoritm
infoga Operation
När ett element ska infogas, lokalisera först dess korrekta plats. Börja söka från rotnoden, om data är mindre än nyckelvärdet, Sök efter den tomma platsen i den vänstra undertreen och sätt in data. Annars, Sök efter den tomma platsen i rätt underträd och infoga data.