Encyclopedia > Inorder traversal

  Article Content

Inorder traversal

In Computer science, Inorder traversal is used in Data structures, and specifically, Trees and Binary Trees.

Programs that utilize tree strucutres need to process nodes[?] in a tree (represented as circles in below diagram). Nodes contain information about an object. For now, let's assume each node contains a letter. The arrows indicate a link between nodes.

InOrder Traversal is a type of tree traversal[?] algorithm. Inorder refers to when the root is processed inbetween to its two subtrees.

Steps to Inorder Traversal

Given a non-empty tree,

  1. Process the nodes in the left subtree with a recursive call
  2. Process the root
  3. Process the nodes in the right subtree with a recursive call

Given a binary tree PY:

The order would go D,B,G,E,A,C,F

Here is an example of InOrder in C++

 template <class Item>
 int inorder_print(const binary_tree_nodes<Item>* ptr)
 // ptr is a pointer to a node in a binary tree OR null
 // meaning empty tree.
 {
    if (ptr != NULL)
    {
        inorder_print( ptr->left() );
        std::cout << ptr->data() << std::endl;
        inorder_print( ptr->right() );
    }
    return 0;
 }

The same example in Haskell might look like

 data Tree a = ET | Node(a, Tree a, Tree a)

 inorder :: Tree a -> [a]
 inorder ET = []
 inorder (Node (x, left,right)) = (inorder left) ++ [x] ++ (inorder right)

Compare: Pre-order traversal, post-order traversal



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Great River, New York

... The racial makeup of the town is 98.12% White, 0.00% African American, 0.06% Native American, 0.58% Asian, 0.00% Pacific Islander, 0.26% from other races, and 0.97% from ...

 
 
 
This page was created in 37.6 ms