Tree traversal: Difference between revisions

Revision as of 08:18, 26 January 2023

Revision as of 09:13, 26 January 2023

Line 21:

| ''Post-order (node visited at position blue {{colorbull|#2A7FFF|round|size=180}})'':{{br}}     A, C, E, D, B, H, I, G, F.

}}]]

In ''depth-first search'' (DFS), the search tree is deepened as much as possible before going to the next sibling. In this, an algorithm traverses a graph by first going to the farthest point it can along each branch, then going back to the root node. The method relies on the stack data structure to remember which vertex it should proceed to next.

The two most common forms of DFS are:

# Recursive DFS

# Iterative DFS

To traverse binary trees with depth-first search, perform the following operations at each node:<ref>[http://www.cise.ufl.edu/~sahni/cop3530/slides/lec216.pdf ''Binary Tree Traversal Methods'']</ref><ref>{{cite web|url=http://www.programmerinterview.com/index.php/data-structures/preorder-traversal-algorithm/|title=Preorder Traversal Algorithm|access-date=2 May 2015}}</ref>

Line 328 ⟶ 323:

* [http://www.sitepoint.com/hierarchical-data-database/ Storing Hierarchical Data in a Database] with traversal examples in PHP

* [https://web.archive.org/web/20110606032941/http://dev.mysql.com/tech-resources/articles/hierarchical-data.html Managing Hierarchical Data in MySQL]

* [https://codingparks.com/tree-traversal-python-with-recursion/ Step-by-Step Guide: Tree Traversal Techniques and Recursive Implementation in Python with Code Examples.]

* [http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html Working with Graphs in MySQL]

* [https://favtutor.com/blogs/tree-traversal-python-with-recursion Sample code for recursive tree traversal in Python.]