Trees
Terminology
Binary Tree
Each node can have 0, 1, or
2 children, but no more than 2 children.
|
class BinaryTree { public: ... private: struct Node { int key; Info info; Node* left; Node* right; }; Node* root; }; |
|
A method to count the
nodes in a binary tree.
class BinaryTree
{
public:
int Count() const;
private:
int Count( /* in */ Node* ptr ) const;
};
int
BinaryTree::Count() const
{
Count( root );
}
int
BinaryTree::Count( /* in */ Node* ptr ) const
{
if ( ptr == NULL )
return 0;
else
return 1 + Count( ptr->left) +
Count( ptr->right);
}
A method to determine the
height of a binary tree.
class BinaryTree
{
public:
int Height() const;
private:
int Height( /* in */ Node* ptr ) const;
};
int
BinaryTree::Height() const
{
Height( root );
}
int BinaryTree::Height(
/* in */ Node* ptr ) const
{
if ( ptr == NULL )
return 0;
else
return 1 + max( Height( ptr->left),
Height( ptr->right) );
}
where max(i,j)
is defined as:
int max( /* in */ i,
/* in */ j )
{
return i > j ? i : j;
}
A method that mirror
images a binary tree
class BinaryTree
{
public:
void MirrorImage();
private:
void MirrorImage( /* in */ Node* ptr );
};
int
BinaryTree::MirrorImage()
{
MirrorImage( root );
}
int
BinaryTree::MirrorImage( /* in */ Node* ptr )
{
if ( ptr != NULL )
{
Node* swapPtr = ptr->left;
ptr->left = ptr->right;
ptr->right = swapPtr;
MirrorImage( ptr->left );
MirrorImage( ptr->right );
}