• Choose a category
• All
• Classic-Fiction

By Root 1369 0

to the node at the top of the subtree about to be traversed. On the initial call to each function, we also pass into list an empty linked list already initialized with list_init. For each of the traversals, nodes are placed into the list in the order they are encountered. When the initial call in the recursion returns, list contains the preorder, inorder, or postorder listing of the nodes, as appropriate. Notice how a recursive implementation of these traversals nicely models the definitions presented earlier in the chapter.

Example 9.3. Implementation of Functions for Traversing a Binary Tree

/*****************************************************************************

* *

* ------------------------------ traverse.c ------------------------------ *

* *

*****************************************************************************/

#include "list.h"

#include "traverse.h"

/*****************************************************************************

* *

* ------------------------------- preorder ------------------------------- *

* *

*****************************************************************************/

int preorder(const BiTreeNode *node, List *list) {

/*****************************************************************************

* *

* Load the list with a preorder listing of the tree. *

* *

*****************************************************************************/

if (!bitree_is_eob(node)) {

if (list_ins_next(list, list_tail(list), bitree_data(node)) != 0)

return -1;

if (!bitree_is_eob(bitree_left(node)))

if (preorder(bitree_left(node), list) != 0)

return -1;

if (!bitree_is_eob(bitree_right(node)))

if (preorder(bitree_right(node), list) != 0)

return -1;

}

return 0;

}

/*****************************************************************************

* *

* -------------------------------- inorder ------------------------------- *

* *

*****************************************************************************/

int inorder(const BiTreeNode *node, List *list) {

/*****************************************************************************

* *

* Load the list with an inorder listing of the tree. *

* *

*****************************************************************************/

if (!bitree_is_eob(node)) {

if (!bitree_is_eob(bitree_left(node)))

if (inorder(bitree_left(node), list) != 0)

return -1;

if (list_ins_next(list, list_tail(list), bitree_data(node)) != 0)

return -1;

if (!bitree_is_eob(bitree_right(node)))

if (inorder(bitree_right(node), list) != 0)

return -1;

}

return 0;

}

/*****************************************************************************

* *

* ------------------------------- postorder ------------------------------ *

* *

*****************************************************************************/

int postorder(const BiTreeNode *node, List *list) {

/*****************************************************************************

* *

* Load the list with a postorder listing of the tree. *

* *

*****************************************************************************/

if (!bitree_is_eob(node)) {

if (!bitree_is_eob(bitree_left(node)))

if (postorder(bitree_left(node), list) != 0)

return -1;

if (!bitree_is_eob(bitree_right(node)))

if (postorder(bitree_right(node), list) != 0)

return -1;

if (list_ins_next(list, list_tail(list), bitree_data(node)) != 0)

return -1;

}

return 0;

}

Description of Binary Search Trees

Binary search trees are binary trees organized specifically for searching. To search for a node in a binary search tree, we start at the root of the tree and descend level by level until we find the node we are looking for. When we encounter a node greater than the desired node, we follow its left pointer. When we encounter a node that is less, we follow its right pointer. For example, to locate 15 in the tree of Figure 9.7, start at the root and move to the left since 15 is less than 20, then to the right since 15 is greater than 09, at which point we