Binary trees

Number of children is always two.

Ordered binary trees

All nodes left of a given node, n, are <= n; all nodes right of n are > n.

Traversal

Pre-order:

- visit root
- go left
- go right

In-order:

- go left
- visit root
- go right

Post-order:

- go left
- go right
- visit root

Level-order (breadth first search) (needs a queue)

- enqueue root in q
- while q is not empty
- n = q.dequeue()
- visit n
- if n.left, enqueue(n.left)
- if n.right, enqueue(n.right)

Of course, rather than using recursion, you can replace the call stack with an actual stack, and then mark the nodes as visited or not.

## No comments:

Post a Comment