- Forward


Tree Traversal
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Background
Back Forward
  • Tree:
    • A connected graph with no circuits
  • Structures for Trees:
    • Can use both contiguous and linked structures
Tree Traversal
Back Forward
  • Defined:
    • Moving through the vertices in a tree, following the edges
  • Trees of Interest:
    • Binary Trees
    • Other N-ary Trees
    • General Trees
Traversing Binary Trees
Back Forward
  • The Three Parts:
    • Traversal of a single node
    • Traversal of a left subtree
    • Traversal of a right subtree
  • Traversal Orders:
    • Preorder - traverse the root node, then the left subtree, then the right subtree
    • Inorder - traverse the left subtree, then the root node, then the right subtree
    • Postorder - traverse the left subtree, then the right subtree, then the root node
Traversing Binary Trees (cont.)
Back Forward

Pseudocode for Inorder Traversal

inOrder(current) { if (current != null) { inOrder(current's left) print(current's data) inOrder(current's right) } }
There's Always More to Learn
Back -