.. This file is part of the OpenDSA eTextbook project. See .. http://opendsa.org for more details. .. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and .. distributed under an MIT open source license. .. avmetadata:: :title: Binary Tree Traversals :author: Cliff Shaffer :institution: Virginia Tech :requires: binary tree terminology; recursion :satisfies: binary tree traversal :topic: Binary Trees :keyword: Inorder Traversal; Preorder Traversal; Postorder Traversal :naturallanguage: en :programminglanguage: Java :description: Presents the standard binary tree traversals. Also discusses the pros and cons of various ways to implement these traversals recursively. Binary Tree Traversals ====================== Binary Tree Traversals ---------------------- Often we wish to process a binary tree by "visiting" each of its nodes, each time performing a specific action such as printing the contents of the node. Any process for visiting all of the nodes in some order is called a :term:`traversal`. Any traversal that lists every node in the tree exactly once is called an :term:`enumeration` of the tree's nodes. Some applications do not require that the nodes be visited in any particular order as long as each node is visited precisely once. For other applications, nodes must be visited in an order that preserves some relationship. Preorder Traversal ~~~~~~~~~~~~~~~~~~ For example, we might wish to make sure that we visit any given node *before* we visit its children. This is called a :term:`preorder traversal`. One good time to use a preorder traversal is if we want to build a tree by copying another. It would be simplest to create a node before we create its children. .. _BinTravExample: .. inlineav:: BinExampCON dgm :links: AV/Binary/BinExampCON.css :scripts: AV/Binary/BinExampCON.js :align: center :keyword: Binary Tree Traversals; Preorder Traversal A binary tree for traversal examples. .. topic:: Example The preorder enumeration for the tree of Figure :num:`Figure #BinTravExample` is **A B D C E G F H I**. The first node printed is the root. Then all nodes of the left subtree are printed (in preorder) before any node of the right subtree. .. inlineav:: preorderCON ss :long_name: Preorder Traversal Slideshow :links: AV/Binary/BTCON.css :scripts: AV/Binary/preorderCON.js :output: show :keyword: Binary Tree Traversals; Preorder Traversal Postorder Traversal ~~~~~~~~~~~~~~~~~~~ Alternatively, we might wish to visit each node only *after* we visit its children (and their subtrees). For example, imagine that we are working in a language without garbage collection, like C++. If we want to delete a tree, we need to call the destructor on each of its nodes. We have to delete the children of a node A before we delete A, because otherwise we would no longer be able to access the children! But to do that requires that the children's children be deleted first, and so on. This is called a :term:`postorder traversal`. .. topic:: Example The postorder enumeration for the tree of Figure :num:`Figure #BinTravExample` is **D B G E H I F C A**. .. inlineav:: postorderCON ss :long_name: Postorder Traversal Slideshow :links: AV/Binary/BTCON.css :scripts: AV/Binary/postorderCON.js :output: show :keyword: Binary Tree Traversals; Postorder Traversal Inorder Traversal ~~~~~~~~~~~~~~~~~ An :term:`inorder traversal` first visits the left child (including its entire subtree), then visits the node, and finally visits the right child (including its entire subtree). The :ref:`binary search tree ` makes use of this traversal to print all nodes in ascending order of value. .. topic:: Example The inorder enumeration for the tree of Figure :num:`Figure #BinTravExample` is **B D A G E C H F I**. .. inlineav:: inorderCON ss :long_name: Inorder Traversal Slideshow :links: AV/Binary/BTCON.css :scripts: AV/Binary/inorderCON.js :output: show :keyword: Binary Tree Traversals; Inorder Traversal Implementation ~~~~~~~~~~~~~~ Now we will discuss some implementations for the traversals, but we need to define a node ADT to work with. Just as a linked list is composed of a collection of link objects, a tree is composed of a collection of node objects. Here is an ADT for binary tree nodes, called ``BinNode``. This class will be used by some of the binary tree structures presented later. Member functions are provided that set or return the element value, return a pointer to the left child, return a pointer to the right child, or indicate whether the node is a leaf. .. codeinclude:: Binary/BinNode :tag: BinNode A traversal routine is naturally written as a recursive function. Its input parameter is a pointer to a node which we will call ``rt`` because each node can be viewed as the root of a some subtree. The initial call to the traversal function passes in a pointer to the root node of the tree. The traversal function visits ``rt`` and its children (if any) in the desired order. For example, a preorder traversal specifies that ``rt`` be visited before its children. This can easily be implemented as follows. .. codeinclude:: Binary/Preorder :tag: preorder Function ``preorder`` first checks that the tree is not empty (if it is, then the traversal is done and ``preorder`` simply returns). Otherwise, ``preorder`` makes a call to ``visit``, which processes the root node (i.e., prints the value or performs whatever computation as required by the application). Function ``preorder`` is then called recursively on the left subtree, which will visit all nodes in that subtree. Finally, ``preorder`` is called on the right subtree, visiting all nodes in the right subtree. Postorder and inorder traversals are similar. They simply change the order in which the node and its children are visited, as appropriate. .. avembed:: AV/Binary/btTravPreorderPRO.html pe :long_name: Binary Tree Preorder Traversal Exercise :keyword: Binary Tree Traversals; Preorder Traversal Postorder Traversal Practice ---------------------------- .. avembed:: AV/Binary/btTravPostorderPRO.html pe :long_name: Binary Tree Postorder Traversal Exercise :keyword: Binary Tree Traversals; Postorder Traversal Inorder Traversal Practice -------------------------- .. avembed:: AV/Binary/btTravInorderPRO.html pe :long_name: Binary Tree Inorder Traversal Exercise :keyword: Binary Tree Traversals; Inorder Traversal Summary Questions ----------------- .. avembed:: Exercises/Binary/TravSumm.html ka :long_name: Tree Traversal Summary Questions :keyword: Binary Tree Traversals