@@ -23,6 +23,7 @@ The latest released version is [`2.0.0`][release].
23 23
* [Parent](#parent)
24 24
* [Literal](#literal)
25 25
* [Glossary](#glossary)
26 +
* [Tree traversal](#tree-traversal)
26 27
* [Utilities](#utilities)
27 28
* [List of Utilities](#list-of-utilities)
28 29
* [References](#references)
@@ -304,6 +305,102 @@ Files are provided by the host environment and not defined by unist.
304 305 305 306
For example, see projects such as [**vfile**][vfile].
306 307 308 +
###### Preorder
309 + 310 +
In **preorder** (**NLR**) is [depth-first][traversal-depth] [tree
311 +
traversal][traversal] that performs the following steps for each node _N_:
312 + 313 +
1. **N**: visit _N_ itself
314 +
2. **L**: traverse [_head_][term-head] (then its _next sibling_, recursively
315 +
moving forward until reaching _tail_)
316 +
3. **R**: traverse [_tail_][term-tail]
317 + 318 +
###### Postorder
319 + 320 +
In **postorder** (**LRN**) is [depth-first][traversal-depth] [tree
321 +
traversal][traversal] that performs the following steps for each node _N_:
322 + 323 +
1. **L**: traverse [_head_][term-head] (then its _next sibling_, recursively
324 +
moving forward until reaching _tail_)
325 +
2. **R**: traverse [_tail_][term-tail]
326 +
3. **N**: visit _N_ itself
327 + 328 +
## Tree traversal
329 + 330 +
**Tree traversal** is a common task when working with a [_tree_][term-tree] to
331 +
search it.
332 +
Tree traversal is typically either _breadth-first_ or _depth-first_.
333 + 334 +
In the following examples, we’ll work with this tree:
335 + 336 +
```ascii
337 +
+---+
338 +
| A |
339 +
+-+-+
340 +
|
341 +
+-----+-----+
342 +
| |
343 +
+-+-+ +-+-+
344 +
| B | | F |
345 +
+-+-+ +-+-+
346 +
| |
347 +
+-----+--+--+ |
348 +
| | | |
349 +
+-+-+ +-+-+ +-+-+ +-+-+
350 +
| C | | D | | E | | G |
351 +
+---+ +---+ +---+ +---+
352 +
```
353 + 354 +
###### Breadth-first traversal
355 + 356 +
**Breadth-first traversal** is visiting a node and all its
357 +
[_siblings_][term-sibling] to broaden the search at that level, before
358 +
traversing [_children_][term-child].
359 + 360 +
For the syntax tree defined in the diagram, a breadth-first traversal first
361 +
searches the root of the tree (**A**), then its children (**B** and **F**), then
362 +
their children (**C**, **D**, **E**, and **G**).
363 + 364 +
###### Depth-first traversal
365 + 366 +
Alternatively, and more commonly, **depth-first traversal** is used.
367 +
The search is first deepened, by traversing [_children_][term-child], before
368 +
traversing [_siblings_][term-sibling].
369 + 370 +
For the syntax tree defined in the diagram, a depth-first traversal first
371 +
searches the root of the tree (**A**), then one of its children (**B** or
372 +
**F**), then their children (**C**, **D**, and **E**, or **G**).
373 + 374 +
For a given node _N_ with [_children_][term-child], a **depth-first traversal**
375 +
performs three steps, simplified to only binary trees (every node has
376 +
[_head_][term-head] and [_tail_][term-tail], but no other children):
377 + 378 +
* **N**: visit _N_ itself
379 +
* **L**: traverse [_head_][term-head]
380 +
* **R**: traverse [_tail_][term-tail]
381 + 382 +
These steps can be done in any order, but for non-binary trees, **L** and **R**
383 +
occur together.
384 +
If **L** is done before **R**, the traversal is called _left-to-right_
385 +
traversal, otherwise it is called _right-to-left_ traversal.
386 +
In the case of non-binary trees, the other children between _head_ and _tail_
387 +
are processed in that order as well, so for _left-to-right_ traversal, first
388 +
_head_ is traversed (**L**), then its _next sibling_ is traversed, etcetera,
389 +
until finally _tail_ (**R**) is traversed.
390 + 391 +
Because **L** and **R** occur together for non-binary trees, we can produce four
392 +
types of orders: NLR, NRL, LRN, RLN.
393 + 394 +
NLR and LRN (the two _left-to-right_ traversal options) are most commonly used
395 +
and respectively named [_preorder_][term-preorder] and
396 +
[_postorder_][term-postorder].
397 + 398 +
For the syntax tree defined in the diagram, _preorder_ and _postorder_ traversal
399 +
thus first search the root of the tree (**A**), then its head (**B**), then its
400 +
children from left-to-right (**C**, **D**, and then **E**).
401 +
After all [_descendants_][term-descendant] of **B** are traversed, its next
402 +
sibling (**F**) is traversed and then finally its only child (**G**).
403 + 307 404
## Utilities
308 405 309 406
**Utilities** are functions that work with nodes.
@@ -491,6 +588,10 @@ This work is licensed under a
491 588 492 589
[term-tree]: #tree
493 590 591 +
[term-preorder]: #preorder
592 + 593 +
[term-postorder]: #postorder
594 + 494 595
[term-child]: #child
495 596 496 597
[term-parent]: #parent-1
@@ -501,6 +602,10 @@ This work is licensed under a
501 602 502 603
[term-descendant]: #descendant
503 604 605 +
[term-head]: #head
606 + 607 +
[term-tail]: #tail
608 + 504 609
[term-generated]: #generated
505 610 506 611
[term-type]: #type
@@ -509,6 +614,10 @@ This work is licensed under a
509 614 510 615
[term-file]: #file
511 616 617 +
[traversal]: #tree-traversal
618 + 619 +
[traversal-depth]: #depth-first-traversal
620 + 512 621
[list-of-utilities]: #list-of-utilities
513 622 514 623
[webidl]: https://heycam.github.io/webidl/
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4