Tags:    c#

Iteration gennem et binært træ

Når vi arbejder med lineære strukturer, som for eksempel en liste eller tabel (også kaldet array), så er der få åbenlyse iterationsmuligheder. Vi kan for eksempel starte med listens første element og så besøge alle elementerne i den rækkefølge de holdes i i listen. Vi kan også starte med listens sidste element og iterere den modsatte vej.

Nu og her arbejder vi dog ikke med lister eller tabeller, men med træer, og her er der ikke umiddelbart nogen åbenlyse iterationsmuligheder. Men hvis vi lægger hovedet i blød, og kigger lidt på træstrukturen, så kan vi godt finde frem til fire konsistente måder hvorpå vi kan iterere gennem strukturen på.

Lad os kigge på disse fire iterationsmuligheder. Udtrykstræet fra afsnittet "Hvorfor?" bruges til at illustrere de forskellige iterationer.

Preorder
I denne metoder besøges et element efterfulgt af elementerne i dets venstre undertræ. Vores udtrykstræs elementer bliver derfor besøgt i følgende rækkefølge: =, a, +, b, *, +, c, 1, 4.

Inorder
I denne metode besgøes først et elements venstre undertræ, derefter selve elementet, og derefter elementets højre undertræ. Vores udtrykstræs ellementer bliver besøgt i følgende rækkefølge: a, =, b, +, c, +, 1, *, 4. Dette svarer til det oprindelige udtryk blot uden paranteser. Dette er måden hvorpå man vil indtaste udtrykket på de fleste standard lommeregnere (blot skal man selvfølelig lige huske paranteserne).

Postorder
Her starter vi med at besøge et elements venstre undertræ, efterfulgt af dets højre undertræ, og til sidst selve elementet. I vores eksempel bliver det til følgende rækkefølge: a, b, c, 1, +, 4, *, +, =. Dette er måden hvorpå man vil indtaste vores oprindelig udtryk på en såkaldt RPN (reverse polisn notation) lommeregner som især kendes hos HPs lommeregnere.

Levelorder
I denne metoder besøges alle elementer på niveau i først, og derefter besøger vi elementerne på niveaui + 1. I vores eksempel bliver det derfor til følgende rækkefølge: =, a, +, b, *, +, 4, c, 1.

Vi vil nu kode de tre første iterationsmetoder (den fjerde følger nemt heraf, og lades være op til læseren).
For at iterere gennem vores træ kalder beder vi bare om en iterator fra træets rod. På lignende vis kan man starte en iteration fra et hvilket som helst undertræ.

Da vores træ implementerer IEnumerable skal vi implementere en GetEnumerator metode. Da vi ender med fire forskellige iteratorer må vi i denne metode træffe et valg for hvilken iterator der skal returneres. Derudoer vil vi tilføje fire specifikke metoder der kan bruges til at få fat i en iterator af eget valgt.

Vi starter med at kode preorder enumereringen.

Vi skal tilføje følgende metode til træ-klassen:

 public IEnumerator<T> GetPreOrderEnumerator()
         {
             return this.root.GetPreOrderEnumerator();
         }

Og til element-klassen:

 public IEnumerator<T> GetPreOrderEnumerator()
         {
             return new PreOrderEnumerator<T>(this);
         }

Koden er her:

 using System;
 using System.Collections;
 using System.Collections.Generic;
 
 namespace Trees
 {
     internal class PreOrderEnumerator<T> : IEnumerator<T>
     {
         private readonly BinaryTreeNode<T> root;
         private readonly Stack<BinaryTreeNode<T>> unvisitedNodes;
 
         public PreOrderEnumerator(BinaryTreeNode<T> root)
         {
             this.root = root;
             this.unvisitedNodes = new Stack<BinaryTreeNode<T>>();
             this.Reset();
         }
 
         // We don't need a Dispose method so we implement it explicitly so it is hidden from the public
         // interface.
         void IDisposable.Dispose()
         {
         }
 
         public bool MoveNext()
         {
             if (this.unvisitedNodes.Count > 0)
             {
                 var old = this.unvisitedNodes.Pop();
                 this.Current = old.Value;
 
                 // This ordering is important - this is what makes it a preorder traversal.
                 if (old.Right != null)
                 {
                     this.unvisitedNodes.Push(old.Right);
                 }
 
                 if (old.Left != null)
                 {
                     this.unvisitedNodes.Push(old.Left);
                 }
 
 
 
 
 
 
 
                 return true;
             }
 
             return false;
         }
 
         public void Reset()
         {
             this.unvisitedNodes.Clear();
             if (this.root != null)
             {
                 this.unvisitedNodes.Push(root);
             }
         }
 
         public T Current { get; private set; }
 
         object IEnumerator.Current
         {
             get { return this.Current; }
         }
     }
 }

Læg mærke til, at jeg har implementeret Dispose() eksplicit, så den kan gemmes fra den offentlige grænseflade, da vi ikke har bruge denne metode her.

Køretidskompleksiteten er O(n), da hvert element bliver lagt på og fjernet fra stakken én gang.

Lad os så kigge på implementeringen af inorder iterationen. Igen skal vi lige tilføje en metode til BinaryTree klassen:

 public IEnumerator<T> GetInOrderEnumerator()
 {
    return this.root.GetInOrderEnumerator();
 }

Og i klassen BinaryTreeNode<T> tilføjer vi følgende metode:

 public IEnumerator<T> GetInOrderEnumerator()
 {
    return new InOrderEnumerator<T>(this);
 }

Selve InOrderEnumerator<T> kommer her:

 using System;
 using System.Collections;
 using System.Collections.Generic;
 
 namespace Trees
 {
     internal class InOrderEnumerator<T> : IEnumerator<T>
     {
         private readonly BinaryTreeNode<T> root;
         private readonly Stack<BinaryTreeNode<T>> unvisitedNodes;
 
         public InOrderEnumerator(BinaryTreeNode<T> root)
         {
             this.root = root;
             this.unvisitedNodes = new Stack<BinaryTreeNode<T>>();
             this.Reset();
         }
 
         void IDisposable.Dispose()
         {
         }
 
         public bool MoveNext()
         {
             if (this.unvisitedNodes.Count > 0)
             {
                 var start = this.unvisitedNodes.Pop();
                 this.Current = start.Value;
 
                 if (start.Right != null)
                 {
                     var node = start.Right;
 
                     while (node != null)
                     {
                         this.unvisitedNodes.Push(node);
                         node = node.Left;
                     }
                 }
 
                 return true;
             }
 
             return false;
         }
 
         public void Reset()
         {
             this.unvisitedNodes.Clear();
             var node = root;
             while (node != null)
             {
                 this.unvisitedNodes.Push(node);
                 node = node.Left;
             }
         }
 
         public T Current { get; private set; }
 
         object IEnumerator.Current
         {
             get { return this.Current; }
         }
     }
 }

På grund af den måde inorder iterationen fungerer på, er vi tvunget til at starte med (i vores Reset metode) at putte alle elementerne fra roden og ned til dens venstremest afkom på stakken. Herfra arbejder vi os gennem træet, ved at undersøge om den nuværende knude har et højre undertræ (som ikke er blevet besøgt endnu), og såfremt det er tilfældet puttes det på stakken. Hvis ikke, bevæger vi os videre gennem træet ved at poppe et element af stakken.
Inorder er én af de mest almindelige metoder til at iterere gennem et træ på, hvorfor det er et godt bud på hvad der returneres af GetEnumerator. Jeg har dog en forkærlighed for RPN og derfor vælger jeg at lade GetEnumerator returnere en postorder enumerator. Derfor ændres BinaryTreeNode<T>-klassens metod GetEnumerator() til:

 public IEnumerator<T> GetEnumerator()
 {
   return new PostOrderEnumerator<T>(this);
 }

Vi tilføjer dog også følgende til samme klasse:

 public IEnumerator<T> GetPostOrderEnumerator()
 {
    return new PostOrderEnumerator<T>(this);
 }

Til klassen BinaryTree tilføjes:

 public IEnumerator<T> GetPostOrderEnumerator()
 {
    return this.root.GetPostOrderEnumerator();
 }

Og her kommer så selve enuemratoren:

 using System;
 using System.Collections;
 using System.Collections.Generic;
 
 namespace Trees
 {
     internal class PostOrderEnumerator<T> : IEnumerator<T>
     {
         private readonly BinaryTreeNode<T> root;
         private readonly Stack<BinaryTreeNode<T>> parentsOfCurrentlyVisitedNodes;
 
         public PostOrderEnumerator(BinaryTreeNode<T> root)
         {
             this.root = root;
             this.parentsOfCurrentlyVisitedNodes = new Stack<BinaryTreeNode<T>>();
             this.Reset();
         }
 
         void IDisposable.Dispose()
         {
         }
 
         public bool MoveNext()
         {
             if (this.parentsOfCurrentlyVisitedNodes.Count > 0)
             {
                 var node = this.parentsOfCurrentlyVisitedNodes.Pop();
                 this.Current = node.Value;
 
                 if (this.parentsOfCurrentlyVisitedNodes.Count > 0)
                 {
                     var parent = this.parentsOfCurrentlyVisitedNodes.Peek();
                     if (node == parent.Left)
                     {
                         node = parent.Right;
 
                         while (node != null)
                         {
                             this.parentsOfCurrentlyVisitedNodes.Push(node);
                             node = node.Left ?? node.Right;
                         }
                     } 
                 }
 
                 return true;
             }
 
             return false;
         }
 
         public void Reset()
         {
             this.parentsOfCurrentlyVisitedNodes.Clear();
 
             var node = root;
 
             while (node != null)
             {
                 this.parentsOfCurrentlyVisitedNodes.Push(node);
                 node = node.Left ?? node.Right;
             }
         }
 
         public T Current
         {
             get; private set;
 
         }
 
         object IEnumerator.Current
         {
             get { return this.Current; }
         }
     }
 }

Her indeholder vores stak de elementer som er forældre til de elementer som vi på et givet tidspunkt er ved at undersøge. Ellers er koden ligetil.

Jeg vil lade implementatioen af "level order" enumeratoren være op til læseren.

Det skal også bemærkes, at da træer er rekursive strukturer kan disse enuemratorer også implementeres ved brug af rekursion.

Tilføjelser

Vi har nu en fungerende implementation af et binært træ. Men der er masser at ekstra ting vi kunne tilføje. Hvad med f.eks. en metode de returnerer dybden af et element i træet? Eller en metoder der kan fortælle en om der er tale om et fuldt træ? Der er masse af muligheder.

Litteratur og videre læsning

Wikipedia har en god artikel om de forskellige iterationsmetoder der er i et træ.

En klassiker om datastrukturer og algoritmer er "Introduction to Algorithms" af Cormen et al. Derudover har Baileys "Java Structures" nogle spændende kapitler, bogen har dog nogle år på bagen hvorfor Java- koden ikke følger de moderne Java SDKs og idiomer.

Hvad synes du om denne artikel? Giv din mening til kende ved at stemme via pilene til venstre og/eller lægge en kommentar herunder.

Del også gerne artiklen med dine Facebook venner:  

Karma barometer (30 dage)

IT jobs | Kontakt | Om Udvikleren.dk | Om karma | IT nyheds arkiv | Annoncering

X