Tree - Order

Data System Architecture

About

The term tree order describes how a tree is traversed.

It can also be a graph data structures, selecting an arbitrary node as the root.

Type

h
        /  |  \
      /    |   \
    d      e    g
   /|\          |
  / | \         f
 a  b  c

The traversals are classified by the order in which the nodes are visited:

  • breadth-first order (hdegabcf). known also as breadht-first search 1) - All the nodes of depth 0 are returned, then depth 1, then 2, and so on.
  • closest-first order (degcfab)
  • depth-first order
    • pre-order left (h d a b c e g f),
    • pre-order right (h g f e d c b a)
    • post-order left (a b c d e f g h),

Not for a tree (directed algorithm)

Example

Java

/* Node is an object of your implementation with a getChildren function */
TreeTraverser<Node> traverser = new TreeTraverser<Node>() {
    @Override
    public Iterable<Task> children(Object node) {
        return node.getChildren();
    }
};
Node root = ....

Then you can iterate over the tree with a for loop:

  • in breadth-first order
for (Task task : traverser.breadthFirstTraversal(root)) { ... }
  • in Preorder
for (Task task : traverser.preOrderTraversal(root)) { ... }
  • in postorder
for (Task task : traverser.postOrderTraversal(root)) { ... }

Documentation / Reference





Discover More
Data System Architecture
Topological Order

Topological order is a tree order algorithm. Topologically is the mathematical term for dependency-first order. For the following tree, a Topological order would be h d e g a b c f
Data System Architecture
Tree - (Traversal|Search)

In computer science, tree traversal (also known as tree search) refers to the process of visiting (examining and/or updating) each node in a tree data structure, exactly once, in a systematic way. Tree...
Data System Architecture
Tree - Depth-First Search (DFS)

Depth-First Search is a tree traversal in a depth-frist order. ie The search tree is deepened as much as possible on each child before going to the next sibling. At node N, in any order: (L) Recursively...



Share this page:
Follow us:
Task Runner