Binary Tree
A look at binary trees
a binary tree is an ordered data structure that has the bigger value on the right
and the lesser value on the left. An 'int' binary tree would look like an upside
down tree with the root at the top and the leaves at the bottom, hence calling it
a binary "tree". Here is a graphical representation of it:
 | | | | |
15
/
13 25
/ /
7 14 20 32
and so on...
|
| |
|
now lets take a look at actual code.
the datastructure for all lists internally contains some sort of data storing routine,
as this is the basis of a list in general. Internally, a binary tree and many other types
of lists use what is called a node.
What is a node?
a 'node' is basically a struct or class datastructure that internally contains an
instance of itself. In a way, a node is a recursive datastructure.
| | | | |
struct Node
{
ItemType data;
Node* left; // the left side ('smaller values')
Node* right; // the right side ('larger values')
}
|
| |
|
looking at the above node, the members of the node struct are:
- ItemType data - the data to store in the node. could be any type (lets typedef for now).
- Node* left - a pointer to the left side (note its type, this is a pointer to another node).
- Node* right - a pointer to the righ side (also note the type)
what makes this so interesting is that it contains an instance of itself as a part of its data
structure. going back to the definition of a node, you will notice that a node is a Tree that
contains one or two 'Tree(s)' and data.
so what does this have to do with binary tree?
the thing is that internally a binary tree is a container class that uses node to store its
data. so the node is basically the whole blue print of the binary tree.
now lets look at the actual binary tree class. We will call this BinTree, and for
syle preference, we'll prefix the class name with 'C' for class.
| | | | |
class CBinaryTree
{
private:
// Note: for style reasons, i like to prefix all of my private member variables
// with underscores (_) or m and underscore (m_).
Node* _root; // the begining of the node (also known as root)
// private member functions
void _destroy(Node* leaf);
void _insert(ItemType key, Node* tree);
Node* _search(ItemType key, Node* tree);
public:
|
| |
|
Please Rate this Code: