dlaczego drzewo DOM jest przedsprzedażne, pierwsze przemieszczenie?

Question

dlaczego drzewo DOM jest od preorder, depth-first traversal?

Jakie są zalety tego wyboru projektu w porównaniu do innych przejść, takich jak BFT?

Właśnie patrząc DOM standard i znaleźć definicję poprzedzające i następujące:

Obiekt A poprzedzający obiektu B, jeśli A i B są w tym samym drzewie i A występuje przed B w drzewie zamówienie.

Obiekt A podąża za obiektem B, jeśli A i B znajdują się w tym samym drzewie , a A występuje po B w kolejności drzewa.

Podobnie jak większość paradygmatów programowania, platforma internetowa ma skończone struktury hierarchiczne , po prostu nazwane drzewa. Kolejność drzewek to w przedsprzedaży, pierwsze przemieszczenie głębi.

Answer 1

Przejście od początku do góry jest zwykle najłatwiejszym stylem przejścia, ponieważ można go wykonać rekursywnie lub z jawnym stosem; szerokość-pierwsza wymaga kolejki, która jest w pewnym sensie bardziej skomplikowaną strukturą danych. Ale myślę, że istnieje prostsza odpowiedź niż tradycja lub prostota: przeszukiwanie głębi drzewa (X) HTML powoduje, że węzły tekstowe są przemieszczane w porządku prezentacji.

Rozważ to względnie proste podtree HTML.

Albo w postaci surowej:

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

jako drzewo (pomijając spacje i atrybuty):

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

Głębokość pierwszego przemieszczenia:

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

wszerz trawers:

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

Answer 2

Głębokie pierwsze wyszukiwanie wymaga pamięci w porządku wysokości drzewa, ale wyszukiwanie wszerz wymaga pamięci w porządku liczności wierzchołków drzewa. Innymi słowy, szukanie w pierwszej kolejności jest świnią pamięci w porównaniu do pierwszego wyszukiwania w głębi.