Algorithms Notes – Binary Trees

720px-binary_search_tree-svg1

A binary tree.

Def: Let T be a tree such that no node in T has more than two children. T is referred to as a binary tree.

A binary tree effectively consists of a root r and two subtrees T_{L} and T_{R}, any (or both) of which could be empty.

Since we already know the maximum number of children each node in a binary tree can have, we can implement it in a way that is very simple in comparison to the implementation of a general tree. Just store pointers for the two children in every node.

 

struct Tree_Node
{
    Element_Type Element;
    Tree_Node* Left_Child;
    Tree_Node* Right_Child;
};

Def: Let T be a binary tree such that each node has either zero or exactly two children. T is called a full binary tree.

Full Binary Tree

Full Binary Tree

Def: Let T be a binary tree such that every level of T except for possibly the last is completely filled and all nodes are as far-left as possible. T is called a complete binary tree.

Complete Binary Tree

Complete Binary Tree

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s