Mastering Algorithms with C

Implementation and Analysis of Binary Trees

Recall that each node of a binary tree consists of three parts: a data member and two pointers to its children. The structure BiTreeNode represents an individual node of a binary tree (see Example 9.1). As you would expect, this structure has three members that correspond to those just mentioned. The structure BiTree is the binary tree data structure (see Example 9.1). This structure consists of four members: size is the number of nodes in the tree, compare is a member not used by binary trees but by datatypes that will be derived later from binary trees, destroy is the encapsulated destroy function passed to bitree_init, and root is a pointer to the top of the node hierarchy.

Example 9.1. Header for the Binary Tree Abstract Datatype

/***************************************************************************** * * * ------------------------------- bitree.h ------------------------------- * * * *****************************************************************************/ #ifndef BITREE_H #define BITREE_H #include <stdlib.h> /***************************************************************************** * * * Define a structure for binary tree nodes. * * * *****************************************************************************/ typedef struct BiTreeNode_ { void *data; struct BiTreeNode_ *left; struct BiTreeNode_ *right; } BiTreeNode; /***************************************************************************** * * * Define a structure ...