|  Startsida |  Hårdvara |  Nätverk |  Programmering |  Programvara |  Felsökning |  System |   
Programmering
  • C /C + + -programmering
  • Computer Programspråk
  • Delphi Programmering
  • Java Programming
  • JavaScript programmering
  • PHP /MySQL Programmering
  • perl Programmering
  • python Programming
  • Ruby programmering
  • Visual Basics Programmering
  • * Dator Kunskap >> Programmering >> Computer Programspråk >> Content

    Hur man lagrar en binärt sökträd till en fil

    Ett ​​binärt sökträd är en datastruktur där register över uppgifter , som kallas "noder", har pekare till andra noder , som kallas " barn . " Detta ger noderna , när plottade ut , en form som liknar ett släktträd . Noder får sin plats i trädet baserat på om de skulle bedöma som större än eller mindre än andra noder . Vänster barn är alltid mindre än sina föräldrar , rätt barn alltid more.Binary sökträd är viktiga i datavetenskap , eftersom de kan vara både sorteras och sökt , i genomsnitt , i O ( n log n ) tid . Saker du behöver
    Compiler
    Befintlig binärt sökträd
    Visa fler instruktioner
    1

    Skapa en butik funktion som tar emot rotnoden . När du handskas med träd i datavetenskap , kommer den mest effektiva algoritmen nästan alltid vara rekursiv och lagra trädet till en fil blir inget undantag . Här är ett urval skelett av rekursiv butiken funktionen ( i Java ) . Public void butik ( Node n ) kastar IOException { ... }
    2

    skriva data på rotnod till fil . Detta kommer att använda " förbeställa traversering " ( Root , Vänster Barn , Höger barn ) att gå igenom alla noder i trädet , eftersom denna metod för traversering gör det lättast att rekonstruera trädet från beställning av noderna i filen . Den rekursiv funktion ser nu ut så här : public void butik ( Node n ) kastar IOException { write ( savefile , n ) ; } Store borde kalla sig med vänstern Barn : public void butik ( Node n ) kastar IOException { write ( savefile , n ) , butik ( n.left ) ;} store borde kalla sig med rätt Child : public void butik ( Node n ) kastar IOException { write ( savefile , n ) , butik ( n.left ) , butik ( n.right ) ; } Addera 3

    Dubbelkolla att funktionen passerar rekursiv checklista . För att undvika fel stackspill , alltid kontrollera att en rekursiv funktion uppfyller följande villkor : Har funktionen har en exit tillstånd ? Ja, så länge som trädet är inte av oändligt djup , så småningom det kommer att nå en nod som har varken en vänster eller höger barn och kommer exit.Does den varje upprepning av funktionen närma till utgången staten? Ja , förutsatt att trädet inte är rund och ingen nod har en av sina egna förfäder som en child.The funktion passerar checklistan .
    4

    Rekonstruera från filen . När det blir dags att ladda trädet tillbaka från filen , kommer du bara sätta varje nod i trädet som den laddas från filen med ditt vanliga insättning algoritm . Detta bör börja vid roten och arbeta sig nedåt med förbeställa traversering , placera den nya noden i det första tomma utrymme i vilket det kommer att passa . Detta bör rekonstruera trädet precis som det ursprungligen komponerades i O ( n log n ) i genomsnitt .

    Tidigare:

    nästa:
    relaterade artiklar
    ·Hur du använder ActiveX-kontroller i ASP Net
    ·Vad är Tk Format
    ·Windows Script Host Tutorial
    ·Hur Multiplicera Binära tal
    ·Hur man skapar en FLV Preloader i AS3
    ·Historien om Prolog Programming Language
    ·Hur hittar Curve Korsningar i Matlab
    ·Hur man gör en tudelad Horisontell Meny
    ·Hur man lagrar en binärt sökträd till en fil
    ·Hur man skriver Adsense annonser för Google
    Utvalda artiklarna
    ·Hur man använder datatyper i C + +
    ·Hur man sätter ett utropstecken i TWiki
    ·Hur man flyttar en fil pekare i C + +
    ·Hur man läser en DOC -fil med PHP
    ·Inaktivera en Java Undantag
    ·Hur skapa och ta bort en mapp med PHP
    ·Hur hittar man de dubbla poster i en tabell
    ·Hur Dölj kolumner med VBA
    ·Java IRC Bot Tutorial
    ·Hur man skriver en Line Switch Tangentkombination
    Copyright © Dator Kunskap http://www.dator.xyz