träd representerar de noder som är anslutna med kanter. Vi kommer att diskutera binärt träd eller binärt sökträd specifikt.
binärt träd är en speciell datastruktur som används för datalagring. Ett binärt träd har ett speciellt villkor att varje nod kan ha högst två barn., Ett binärt träd har fördelarna med både en beställd array och en länkad lista eftersom sökningen är lika snabb som i en sorterad array och insättning eller radering är lika snabb som i länkad lista.
viktiga termer
Följande är viktiga termer med avseende på träd.
-
sökväg avser sekvensen av noder längs kanterna på ett träd.
-
Root − noden längst upp i trädet kallas root. Det finns bara en rot per träd och en väg från rotnoden till någon nod.,
-
överordnad − en nod utom rotnoden har en kant uppåt till en nod som kallas överordnad.
-
barn − noden under en given nod som är ansluten genom kanten nedåt kallas dess underordnade nod.
-
Leaf − noden som inte har någon underordnad nod kallas bladnoden.
-
Subtree − Subtree representerar ättlingar till en nod.
-
besök − besök avser att kontrollera värdet på en nod när kontrollen är på noden.
-
Traversing − Traversing innebär att passera genom noder i en viss ordning.,
-
nivåer − nivå för en nod representerar generering av en nod. Om rotnoden är på nivå 0, är dess nästa barnnod på nivå 1, dess barnbarn är på nivå 2 och så vidare.
-
keys − Key representerar ett värde för en nod baserat på vilken en sökoperation ska utföras för en nod.
binär sökning träd Representation
binär sökning träd uppvisar ett speciellt beteende. En nods vänstra barn måste ha ett värde som är mindre än dess förälders värde och nodens högra barn måste ha ett värde som är större än dess överordnade värde.,
Vi kommer att implementera träd med nodobjekt och ansluta dem via referenser.
Trädnod
koden för att skriva en trädnod skulle likna vad som anges nedan. Den har en datadel och referenser till sina vänstra och högra underordnade noder.
struct node { int data; struct node *leftChild; struct node *rightChild;};
i ett träd delar alla noder gemensam konstruktion.
BST grundläggande funktioner
de grundläggande operationer som kan utföras på en binär sök träddatastruktur, är följande −
-
infoga − infogar ett element i ett träd / skapa ett träd.,
-
Sök − söker ett element i ett träd.
-
förbeställa Traversal − traverserar ett träd på ett förbeställnings sätt.
-
Inorder Traversal − traverserar ett träd i ordning.
-
Postorder Traversal − traverserar ett träd på ett postorder sätt.
vi ska lära oss att skapa (infoga i) en trädstruktur och söka efter ett dataobjekt i ett träd i det här kapitlet. Vi ska lära oss om trädkorsningsmetoder i det kommande kapitlet.
infoga åtgärd
den allra första insättningen skapar trädet., Efteråt, 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.,
algoritm
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
implementering
implementeringen av insert −funktionen ska se ut så här –
sökoperation
När ett element ska sökas, börja söka från rotnoden, och 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
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
implementeringen av denna algoritm ska se ut så här.,
för att veta om genomförandet av binär Sök Träd datastruktur, klicka här.