Mastering Algorithms With C - Kyle Loudon [84]
Complexity
O (1)
Name
bitree_size
Synopsis
int bitree_size(const BiTree *tree);
Return Value
Number of nodes in the tree.
Description
Macro that evaluates to the number of nodes in the binary tree specified by tree.
Complexity
O (1)
Name
bitree_root
Synopsis
BiTreeNode *bitree_root(const BiTree *tree);
Return Value
Node at the root of the tree.
Description
Macro that evaluates to the node at the root of the binary tree specified by tree.
Complexity
O (1)
Name
bitree_is_eob
Synopsis
int bitree_is_eob(const BiTreeNode *node);
Return Value
1 if the node marks the end of a branch, or otherwise.
Description
Macro that determines whether the node specified as node marks the end of a branch in a binary tree.
Complexity
O (1)
Name
bitree_is_leaf
Synopsis
int bitree_isleaf(const BiTreeNode *node);
Return Value
1 if the node is a leaf node, or otherwise.
Description
Macro that determines whether the node specified as node is a leaf node in a binary tree.
Complexity
O (1)
Name
bitree_data
Synopsis
void *bitree_data(const BiTreeNode *node);
Return Value
Data stored in the node.
Description
Macro that evaluates to the data stored in the node of a binary tree specified by node.
Complexity
O (1)
Name
bitree_left
Synopsis
BiTreeNode *bitree_left(const BiTreeNode *node);
Return Value
Left child of the specified node.
Description
Macro that evaluates to the node of a binary tree that is the left child of the node specified by node.
Complexity
O (1)
Name
bitree_right
Synopsis
BiTreeNode *bitree_right(const BiTreeNode *node);
Return Value
Right child of the specified node.
Description
Macro that evaluates to the node of a binary tree that is the right child of the node specified by node.
Complexity
O (1)
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 /***************************************************************************** * * * Define a structure for binary tree nodes. * * * *****************************************************************************/ typedef struct BiTreeNode_ { void *data; struct BiTreeNode_ *left; struct BiTreeNode_ *right; } BiTreeNode; /***************************************************************************** * * * Define a structure for binary trees. * * * *****************************************************************************/ typedef struct BiTree_ { int size; int (*compare)(const void *key1, const void *key2); void (*destroy)(void *data); BiTreeNode *root; } BiTree; /***************************************************************************** * * * --------------------------- Public Interface --------------------------- * * * *****************************************************************************/