Share
Så langt har vi sett på datastrukturer som organiserer data på en lineær måte. Lenkede lister inneholder data fra en enkelt startknutepunkt til en enkelt avslutningsknute. Arrays holder data i sammenhengende, endimensjonale blokker.
I denne delen vil vi se hvordan å legge til en ekstra dimensjon vil tillate oss å introdusere en ny datastruktur: treet. Spesielt vil vi se på en type tre kjent som et binært søketre. Binære søketrær tar den generelle trestrukturen og bruker et sett med enkle regler som definerer treets struktur.
Før vi lærer om disse reglene, la oss lære hva et tre er.
Et tre er en datastruktur hvor hver knute har null eller flere barn. For eksempel kan vi ha et tre slik:
En organisatorisk trestruktur I dette treet kan vi se organisasjonsstrukturen i en bedrift. Blokkene representerer personer eller divisjoner i selskapet, og linjene representerer rapporterende relasjoner. Et tre er en svært effektiv, logisk måte å presentere og lagre denne informasjonen på.
Træret som vises i forrige figur er et generelt tre. Det representerer foreldre / barns relasjoner, men det er ingen regler for strukturen. Konsernsjef har en direkte rapport, men kan like lett ha ingen eller tjue. I figuren er Salg vist til venstre for Markedsføring, men den ordren har ingen betydning. Faktisk er den eneste observerbare begrensningen at hver knute har høyst ett foreldre (og den øverste node, styret, har ingen forelder).
Et binært søketre bruker samme grunnstruktur som det generelle treet vist i siste figur, men med tillegg av noen få regler. Disse reglene er:
La oss se på et tre som er bygget ved hjelp av disse reglene:
Binært søketre Legg merke til hvordan begrensningene vi oppgav, håndheves i diagrammet. Hver verdi til venstre for rotnoden (åtte) har en verdi mindre enn åtte, og hver verdi til høyre er større enn eller lik rotnoden. Denne regelen gjelder rekursivt ved hver knute underveis.
Med dette treet i tankene, la oss tenke på trinnene som gikk inn i å bygge den. Da prosessen startet, var treet tomt og deretter ble en verdi, åtte, lagt til. Fordi det var den første verdien, ble den satt i rot (ultimate foreldre) posisjon.
Vi vet ikke den nøyaktige rekkefølgen som resten av knutepunktene ble lagt til, men jeg presenterer en mulig bane. Verdier vil bli lagt til ved hjelp av en metode som heter Legg til som aksepterer verdien.
BinaryTree tree = new BinaryTree (); tree.Add (8); tree.Add (4); tree.Add (2); tree.Add (3); tree.Add (10); tree.Add (6); tree.Add (7);
La oss gå gjennom de første elementene.
Åtte ble lagt først og ble roten. Deretter ble fire lagt til. Siden fire er mindre enn åtte, må den gå til venstre for åtte som per regel nummer to. Siden åtte har ingen barn på venstre side, blir fire det nærmeste venstre barn på åtte.
To legges til neste. to er mindre enn åtte, så går det til venstre. Det er allerede en node til venstre for åtte, så sammenligningslogikken utføres igjen. to er mindre enn fire, og fire har ingen venstre barn, så to blir det venstre barn på fire.
Tre blir lagt til neste og går til venstre for åtte og fire. Sammenlignet med de to nodene, er det større, så tre er lagt til høyre for to som per regel nummer tre.
Denne syklusen for å sammenligne verdier på hver knute og deretter kontrollere hvert barn igjen og igjen til riktig spor er funnet, gjentas for hver verdi til den endelige trestrukturen er opprettet.
De BinaryTreeNode representerer en enkelt knutepunkt i treet. Den inneholder referanser til venstre og høyre barn (null hvis det ikke finnes), nodeverdien, og IComparable.CompareTo metode som gjør det mulig å sammenligne nodverdiene for å bestemme om verdien skal gå til venstre eller høyre for gjeldende knutepunkt. Dette er hele BinaryTreeNode klassen - som du kan se, er det veldig enkelt.
klasse BinaryTreeNode: IComparable hvor TNode: IComparable public BinaryTreeNode (TNode verdi) Value = value; offentlig BinaryTreeNode venstre get; sett; offentlig BinaryTreeNode Right get; sett; offentlig TNode verdi get; privat sett; /// /// Sammenligner nåværende node til den angitte verdien. /// /// Nodenverdi for å sammenligne med /// 1 hvis forekomsten er større enn /// den angitte verdien, -1 hvis mindre eller 0 hvis lik. offentlig int SammenlignTo (TNode andre) return Value.CompareTo (andre);
De BinærTre klassen gir de grunnleggende metodene du trenger for å manipulere treet: Legg til, Fjerne, en inneholder metode for å avgjøre om et element eksisterer i treet, flere traversal og oppsummeringsmetoder (disse er metoder som gjør at vi kan telle noder i treet i ulike veldefinerte ordrer), og det normale Telle og Klar fremgangsmåter.
For å initialisere treet, er det a BinaryTreeNode referanse som representerer hodet (rot) node av treet, og det er et heltall som holder oversikt over hvor mange elementer som er i treet.
offentlig klasse BinaryTree: IEnumerable hvor T: Inkompatible private BinaryTreeNode _head; privat int _count; offentlig tomrom Legg til (T-verdi) kaste ny NotImplementedException (); offentlig bool Inneholder (T-verdi) kaste ny NotImplementedException (); offentlig bool Fjern (T verdi) kaste ny NotImplementedException (); offentlig ugyldig PreOrderTraversal (Handlingshandling) kaste ny NotImplementedException (); offentlig ugyldig PostOrderTraversal (Handling handling) kaste ny NotImplementedException (); offentlig ugyldig InOrderTraversal (Handlingshandling) kaste ny NotImplementedException (); offentlig IEnumerator GetEnumerator () kaste ny NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () kaste nye NotImplementedException (); offentlig tomretting Clear () kaste ny NotImplementedException (); offentlig int count get;
| Oppførsel | Legger til den angitte verdien til riktig sted i treet. |
| Opptreden | O (log n) i gjennomsnitt; O (n) i verste fall. |
Å legge til en node på treet er ikke veldig komplisert og blir enda enklere når problemet forenkles til en rekursiv algoritme. Det er to saker som må vurderes:
I det første tilfellet fordeler vi bare den nye noden og legger den til treet. I andre tilfelle sammenligner vi verdien til nodens verdi. Hvis verdien vi prøver å legge til er mindre enn nodens verdi, gjentas algoritmen for nodens venstre barn. Ellers gjentas det for nodens rette barn.
offentlig tomrom Legg til (T-verdi) // Sak 1: Træret er tomt. Fordel hodet. hvis (_head == null) _head = ny BinaryTreeNode (verdi); // Sak 2: Træret er ikke tomt, så rekursivt // Finn riktig sted for å sette inn noden. ellers AddTo (_head, value); _count ++; // Rekursiv add-algoritme. privat tomt AddTo (BinaryTreeNode node, T-verdi) // Sak 1: Verdien er mindre enn gjeldende nodeverdi hvis (value.CompareTo (node.Value) < 0) // If there is no left child, make this the new left, if (node.Left == null) node.Left = new BinaryTreeNode(value); else // else add it to the left node. AddTo(node.Left, value); // Case 2: Value is equal to or greater than the current value. else // If there is no right, add it to the right, if (node.Right == null) node.Right = new BinaryTreeNode(value); else // else add it to the right node. AddTo(node.Right, value);
| Oppførsel | Fjerner første nore funnet med den angitte verdien. |
| Opptreden | O (log n) i gjennomsnitt; O (n) i verste fall. |
Å fjerne en verdi fra treet er en begrepsmessig enkel operasjon som blir overraskende komplisert i praksis.
På et høyt nivå er operasjonen enkel:
Det første trinnet er enkelt, og som vi ser, oppnås med samme mekanisme som Inneholder-metoden bruker. Når noden som skal fjernes, er identifisert, kan operasjonen imidlertid ta en av tre baner diktert av tilstanden til treet rundt noden som skal fjernes. De tre tilstandene er beskrevet i de følgende tre tilfellene.
Case One: Koden som skal fjernes, har ikke noe riktig barn.
Sak 1 Knuten som skal fjernes, har ikke rett barn I dette tilfellet kan fjerningsoperasjonen ganske enkelt flytte det venstre barnet, hvis det er en, inn i stedet for den fjernede noden. Det resulterende treet ville se slik ut:
Case 1 - Tree tilstand etter fjerning Sak 2: Koden som skal fjernes har et rett barn som i sin tur ikke har igjen barn.
Sak 2 Knuten som skal fjernes, har et rett barn som ikke har igjen barn I dette tilfellet ønsker vi å flytte den fjernede nodens rette barn (seks) inn i stedet for den fjernede noden. Det resulterende treet vil se slik ut:
Tree tilstand etter fjerning Case Three: Koden som skal fjernes har et rett barn som igjen har et venstre barn.
Sak 3 - Noden som skal fjernes har et rett barn som har et venstre barn I dette tilfellet må det venstre barnets venstre barn i det fjerde knutepunktet sitte på plass.
La oss ta et minutt å tenke på hvorfor dette er sant. Det er to fakta som vi vet om subtreet som begynner med at noden blir fjernet (for eksempel under-treet hvis rot er noden med verdien fem).
Vi må legge inn en verdi i den slettede nodens spor som er mindre enn eller lik hver knute til høyre. For å gjøre det, må vi få den minste verdien på høyre side. Derfor trenger vi rett barns venstreknutepunkt.
Etter fjerning av knutepunktet vil treet se slik ut:
Case 3 - Tree etter noden fjerning Nå som vi forstår de tre fjerne scenariene, la oss se på koden for å få det til å skje.
En ting å merke seg: The FindWithParent metode (se Inneholder avsnittet) returnerer noden som skal fjernes, så vel som foreldren til noden som fjernes. Dette gjøres fordi når noden er fjernet, må vi oppdatere forelderens Venstre eller Ikke sant egenskap for å peke på den nye noden.
Vi kunne unngå å gjøre dette hvis alle noder holdt en referanse til foreldrene deres, men det ville introdusere per-node minne overhead og bokføring kostnader som bare trengs i dette ene tilfellet.
offentlig bool Fjern (T verdi) BinaryTreeNode nåværende, forelder; // Finn noden som skal fjernes. nåværende = FindWithParent (verdi, foreldre); hvis (nåværende == null) return false; _telle--; // Sak 1: Hvis nåværende ikke har riktig barn, erstatter dagens venstre gjeldende. hvis (current.Right == null) hvis (foreldre == null) _head = current.Left; else int result = parent.CompareTo (nåværende.Value); hvis (resultat> 0) // Hvis foreldreverdi er større enn nåværende verdi, // gjør gjeldende venstre barn et venstre barn av foreldre. foreldre.Left = nåværende.Left; annet hvis (resultat < 0) // If parent value is less than current value, // make the current left child a right child of parent. parent.Right = current.Left; // Case 2: If current's right child has no left child, current's right child // replaces current. else if (current.Right.Left == null) current.Right.Left = current.Left; if (parent == null) _head = current.Right; else int result = parent.CompareTo(current.Value); if (result > 0) // Hvis foreldreverdi er større enn nåværende verdi, // gjør gjeldende rett barn et foreldres venstre barn. parent.Left = current.Right; annet hvis (resultat < 0) // If parent value is less than current value, // make the current right child a right child of parent. parent.Right = current.Right; // Case 3: If current's right child has a left child, replace current with current's // right child's left-most child. else // Find the right's left-most child. BinaryTreeNode leftmost = current.Right.Left; BinaryTreeNode leftmostParent = current.Right; while (leftmost.Left != null) leftmostParent = leftmost; leftmost = leftmost.Left; // The parent's left subtree becomes the leftmost's right subtree. leftmostParent.Left = leftmost.Right; // Assign leftmost's left and right to current's left and right children. leftmost.Left = current.Left; leftmost.Right = current.Right; if (parent == null) _head = leftmost; else int result = parent.CompareTo(current.Value); if (result > 0) // Hvis foreldreverdi er større enn nåværende verdi, // gjør venstre overfor foreldrenes venstre barn. parent.Left = leftmost; annet hvis (resultat < 0) // If parent value is less than current value, // make leftmost the parent's right child. parent.Right = leftmost; return true;
| Oppførsel | Returnerer sant hvis treet inneholder den angitte verdien. Ellers returnerer den falsk. |
| Opptreden | O (log n) i gjennomsnitt; O (n) i verste fall. |
inneholder forsvarer til FindWithParent, som utfører en enkel trevandringsalgoritme som utfører følgende trinn, starter ved hodeteknoten:
Siden inneholder returnerer a boolean, Den returnerte verdien bestemmes av hvorvidt FindWithParent returnerer en ikke-null BinaryTreeNode (ekte) eller null-en (falsk).
De FindWithParent Metoden brukes også av Fjern-metoden. Ut-parameteren, forelder, brukes ikke av inneholder.
offentlig bool Inneholder (T-verdi) // Utsette til nodesøk-hjelperfunksjonen. BinaryTreeNode foreldre; return FindWithParent (verdi, foreldre)! = null; /// /// Finn og returnerer den første noden som inneholder den angitte verdien. Hvis verdien /// ikke er funnet, returnerer den null. Returnerer også foreldren til den funnet noden (eller null) /// som brukes i Fjern. /// privat BinaryTreeNode FindWithParent (T-verdi, ut BinaryTreeNode forelder) // Nå, prøv å finne data i treet. BinaryTreeNode nåværende = _head; foreldre = null; // Mens vi ikke har en kamp ... mens (nåværende! = Null) int result = current.CompareTo (value); hvis (resultat> 0) // Hvis verdien er mindre enn gjeldende, gå til venstre. foreldre = nåværende; nåværende = nåværende.Left; annet hvis (resultat < 0) // If the value is more than current, go right. parent = current; current = current.Right; else // We have a match! break; return current;
| Oppførsel | Returnerer antall verdier i treet (0 hvis det er tomt). |
| Opptreden | O (1) |
Tellefeltet økes med Legg til metode og dekrementert av Fjerne metode.
offentlig intall Count get return _count;
| Oppførsel | Fjerner alle noder fra treet. |
| Opptreden | O (1) |
offentlig tomretting Clear () _head = null; _count = 0;
Tree-traverser er algoritmer som tillater behandling av hver verdi i treet i en veldefinert rekkefølge. For hver av de diskuterte algoritmer vil følgende tre bli brukt som prøveinngang.
Eksemplene som følger alle aksepterer en Handling parameter. Denne parameteren definerer handlingen som vil bli brukt på hver knute som den behandles av traversal.
Ordningsdelen for hver traversal vil indikere rekkefølgen der det følgende treet skulle krysse.
Eksemplet treet for traversal bestilling resultater | Oppførsel | Utfører den angitte handlingen på hver verdi i forhåndsbestilling (se beskrivelsen som følger). |
| Opptreden | På) |
| Rekkefølge | 4, 2, 1, 3, 5, 7, 6, 8 |
Preorder-traversen behandler gjeldende knutepunkt før du flytter til venstre og deretter høyre barn. Ved å starte ved rotnoden, fire, utføres handlingen med verdien fire. Deretter behandles venstre knutepunkt og alle sine barn, etterfulgt av høyre knutepunkt og alle sine barn.
En vanlig bruk av preorder-traversal ville være å lage en kopi av treet som inneholdt ikke bare de samme nodeverdiene, men også det samme hierarkiet.
offentlig ugyldig PreOrderTraversal (Handlingshandling) PreOrderTraversal (action, _head); privat void PreOrderTraversal (Handlingshandling, BinaryTreeNode node) if (node! = null) action (node.Value); PreOrderTraversal (action, node.Left); PreOrderTraversal (action, node.Right);
| Oppførsel | Utfører den angitte handlingen på hver verdi i postorder (se beskrivelsen som følger). |
| Opptreden | På) |
| Rekkefølge | 1, 3, 2, 6, 8, 7, 5, 4 |
Postorder-traversen besøker venstre og høyre barn på noden rekursivt, og utfører deretter handlingen på gjeldende knutepunkt etter at barna er ferdige.
Postorder-traverser brukes ofte til å slette et helt tre, for eksempel i programmeringsspråk hvor hver knute må frigjøres, eller for å slette subtre. Dette er tilfellet fordi rotnoden er behandlet (slettet) sist og barna behandles på en måte som vil redusere mengden arbeid som Fjerne algoritmen må utføres.
Offentlig tomgang PostOrderTraversal (Handlingshandling) PostOrderTraversal (action, _head); privat void PostOrderTraversal (Handlingshandling, BinaryTreeNode node) if (node! = null) PostOrderTraversal (action, node.Left); PostOrderTraversal (action, node.Right); handling (node.Value);
| Oppførsel | Utfører den angitte handlingen på hver verdi i i rekkefølge (se beskrivelsen som følger). |
| Opptreden | På) |
| Rekkefølge | 1, 2, 3, 4, 5, 6, 7, 8 |
Inorder-traversal behandler nodene i sorteringsordren - i det forrige eksempelet vil nodene sorteres i numerisk rekkefølge fra minste til største. Det gjør dette ved å finne den minste (venstre) node og deretter behandle den før du behandler de større (høyre) noder.
Inorder traversals brukes når som helst noder må behandles i sort-rekkefølge.
Eksemplet som følger viser to forskjellige metoder for å utføre en inorder-traversal. Den første implementerer en rekursiv tilnærming som utfører en tilbakeringing for hver krysset knutepunkt. Den andre fjerner rekursjonen ved bruk av Stack data strukturen og returnerer en IEnumerator å tillate direkte opptelling.
Offentlig tomgang InOrderTraversal (Handlingshandling) InOrderTraversal (action, _head); privat tomt InOrderTraversal (Handlingshandling, BinaryTreeNode node) if (node! = null) InOrderTraversal (action, node.Left); handling (node.Value); InOrderTraversal (action, node.Right); offentlig IEnumerator InOrderTraversal () // Dette er en ikke-rekursiv algoritme ved hjelp av en stabel for å demonstrere fjerning // rekursjon. hvis (_head! = null) // Lagre noder vi har hoppet over i denne stakken (unngår rekursjon). Stack> stack = new Stack> (); BinaryTreeNode nåværende = _head; // Når vi fjerner rekursjon, må vi følge med på om // vi skal gå til venstre node eller høyre noder neste. bool goLeftNext = true; // Start med å skyve hodet på stakken. stack.Push (strøm); mens (stack.Count> 0) // Hvis vi er på vei til venstre ... hvis (goLeftNext) // Skyv alt, men venstreknutepunktet til stakken. // Vi gir mest etter denne blokken. mens (nåværende.Left! = null) stack.Push (nåværende); nåværende = nåværende.Left; // Inorder er igjen-> yield-> right. yield return current.Value; // Hvis vi kan gå rett, gjør det. if (current.Right! = null) current = current.Right; // Når vi har gått rett en gang, må vi starte // gå igjen igjen. goLeftNext = true; ellers // Hvis vi ikke kan gå rett, må vi hoppe over foreldrenummeret // slik at vi kan behandle det og deretter gå til høyre node. nåværende = stack.Pop (); goLeftNext = false;
| Oppførsel | Returnerer en oppregner som opplistes ved hjelp av InOrder-traversalgoritmen. |
| Opptreden | O (1) for å returnere taleren. Oppsummering av alle elementene er O (n). |
offentlig IEnumerator GetEnumerator () return InOrderTraversal (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () return GetEnumerator ();
Accentsconagua