tree course

Book #1

Contents

Tree course

To browse a graph, we first construct a tree covering of the latter. We will then speak of tree traversal.

Width course

In the course in width, one traverses by increasing depth at the root.

Path Width(Graph G, Vertex s): {f = CreerFile (); f. thread (s); mark (s);
  as long as no f.empty () s = f. to thread (); display (s);
      for any neighbor t of s in G
           if t unmarked DO f.thread (t); mark (t);
           end if
      end for
  end while       
 }

In-depth course: prefix

The in-depth journey are recursive paths. In prefix traversal, we always traverse the left subtree before processing the right subtree.

Route Prefix(Graph G): {
  if (G == NULL) return; display (root); PathPrefix (left); RoutePrefix (right); }

In-depth tour: infix

The in-depth infix route consists of going as far to the left as possible, and displaying the branches from left to right. This is equivalent to displaying the diagonals / from bottom to top.

 CourseInfix(Graph G): {
  if (G == NULL) return; PathPrefix (left); display (root); RoutePrefix (right); }

In-depth walk: postfixe

This is a traversal of the diagonals \ from top to bottom.

 Postfix(Graph G): {
  if (G == NULL) return; PathPrefix (left); RoutePrefix (right); display (root); }