Entry

Datastructure: Tree: Binary: Traversal: How to walk a binary tree level order? (=breadth first)

Oct 26th, 2003 16:37
Knud van Eeden,

----------------------------------------------------------------------
--- Knud van Eeden --- 27 October 2003 - 01:28 am --------------------

Datastructure: Tree: Binary: Traversal: How to walk a binary tree 
level order? (=breadth first)

---

A breadth first traversal, as the name indicates, visits all the nodes
on the same horizontal level first, then preceeds until the next level.

---

It marks the starting node as visited and then adds all nodes which can
be reached from that node to a queue and marks them also as as visited.

---

Then it takes the first node out of the queue and repeats the procedure
adding all unvisited nodes to the queue and marking them as visited.

---

With this method first all nodes with a path length of 1 to the
starting node are visited.

Then all nodes with a path length of 2 to the starting node

and so on.

---

[Internet: source: http://www.informatik.uni-
siegen.de/db/singleAnim.php3?lang=en&anim=graph_dfsbfs.en]

---
---

Internet: see also:

---

Datastructure: Tree: Binary: Traversal: Walk: Order: How to walk in 
order a binary tree?
http://www.faqts.com/knowledge_base/view.phtml/aid/25844/fid/1266

----------------------------------------------------------------------