perché è il preorder per albero DOM o per attraversamento in profondità?

Question

perché DOM albero oder preorder, depth-first traversal?

Quali sono i vantaggi di questa scelta di design rispetto ad altri attraversamenti come il BFT?

Stavo guardando in DOM standard e ho trovato la definizione di precedenti e seguenti:

Un oggetto A è che precede un oggetto B se A e B sono nello stesso albero e A viene prima di B nella struttura ad albero ordine.

Un oggetto A segue un oggetto B se A e B si trovano nello stesso albero e A arriva dopo B nell'ordine dell'albero.

Proprio come la maggior parte dei paradigmi di programmazione, la piattaforma Web ha strutture albero gerarchiche finite , alberi con nome semplice. L'ordine dell'albero è preorder, deep-first traversal.

Answer 1

L'attraversamento di profondità è generalmente lo stile di attraversamento più semplice, poiché è possibile farlo in modo ricorsivo o con uno stack esplicito; la larghezza richiede una coda che, in un certo senso, è una struttura dati più complicata. Ma penso che ci sia una risposta più semplice rispetto alla tradizione o alla semplicità: l'attraversamento di ricerca di profondità di un albero (X) HTML risulta nei nodi di testo che vengono attraversati nell'ordine di presentazione.

Considerare questo relativamente sottostruttura HTML semplice.

Oppure, in forma grezza:

<p>Consider this <emph>relatively</emph> simple <a href="...">HTML</a> subtree</p> 

Come un albero (lasciando fuori gli spazi e gli attributi):

     <P> 
         | 
     +-----------+----+----+-----+------+    
______|______ __|___ ___|__ _|_ ___|___ 
Consider this <EMPH> simple <A> subtree 
        |    | 
       ____|_____  __|__ 
       relatively   HTML 

profondità prima traversata:

<P>, Consider this, <EMPH>, relatively, simple, <A>, HTML, subtree 

in ampiezza traverso:

<P>, Consider this, <EMPH>, simple, <A>, subtree, relatively, HTML 

Answer 2

Una ricerca in profondità richiede una memoria dell'ordine dell'altezza dell'albero, ma una ricerca in larghezza richiede una memoria dell'ordine della cardinalità dei vertici dell'albero. In altre parole, la ricerca in ampiezza è una memoria rispetto alla ricerca in profondità.