Entry
Datastructure: Tree: Binary: Traversal: Walk: Order: How to walk in order a binary tree?
Feb 5th, 2005 11:59
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 24 October 2003 - 06:00 pm --------------------
Datastructure: Tree: Binary: Traversal: Walk: Order: How to walk in
order a binary tree?
---
You can walk a tree in general in 4 ways, by choosing a
different order of visiting:
1. Preorder
2. Inorder
3. Postorder
4. Levelorder (=Breadth first)
---
---
1. Preorder
means visit the ROOT, then the LEFT subtree, then the RIGHT subtree.
---
---
2. Inorder
means visit the LEFT subtree, then the ROOT, then the RIGHT subtree
---
---
3. Postorder
means visit the LEFT subtree, then the RIGHT subtree, then the ROOT
---
---
4. Levelorder (=Breadth first)
means visit on the same horizontal level first all childs, then you
proceed to the next horizontal level.
---
So it means you traverse the tree horizontally
(from left to right, or from right to left, and from top to bottom,
or from bottom to top).
So one goes from the first child to the last child on the same
horizontal level.
Then you go down one level and repeat this.
---
You use a queue if the tree is traversed by horizontal levels.
---
So first all nodes on level i are processed from left to right before
the first node of level i+1 is visited
---
So first on depth0 one goes:
to the root
Then on depth1 one goes:
to child1, then child2
Then on depth2 one goes:
to child11 and child12
then child21 and child22
Then on depth3 one goes:
to child111 and child121
to child112 and child122
then child211 and child221
then child212 and child222
and so on.
---
---
So there are at least the following totally 8 systematic ways to
traverse a binary tree:
1. Preorder
2. Inorder
3. Postorder
4. Levelorder
5. From left to right and top to bottom
6. From left to right and bottom to top
7. From right to left and top to bottom
8. From right to left and bottom to top
---
---
For example, the tree for '3 + 4 * 5'
*
|
+----+--+
| |
+ 5
|
+--+--+
| |
3 4
would give you the nodes in this order respectively:
1. Preorder: * + 3 4 5
2. Inorder: 3 + 4 * 5
3. Postorder: 3 4 + 5 *
4. Levelorder or breadth first: * + 5 3 4
---
---
Internet: see also:
---
Datastructure: Link: Overview: Can you give an overview of links?
http://www.faqts.com/knowledge_base/view.phtml/aid/32054/fid/1264
----------------------------------------------------------------------
