Binary Trees

A tree is a connection of Nodes which do not have a cyclical property, i.e. if you trace a path among them and do repeat you cannot make a path back to it. A binary tree is one in which the Nodes only have two links. There are a lot of terms for a tree, but when a definition and picture are given they will be more apparent.

Binary Tree

NULL, or a Node which holds a piece of data and two links called left and right, which point to other Nodes which are also trees.

Root

the top node of a tree

Leaf

the bottom nodes of a tree

Branches

the nodes inbetween the root and leaves

Subtree

a section of a tree

Parent

a node which points to other nodes

Child

a node which is pointed to be another

Ancestor

a node which is on a higher tier than other

Decendant

a node which is on a lower tier than others

Siblings

a node which is on the same tier as another

Height

the number of tiers a tree has, may or may have a zero offset

Depth

same as height

Full

a tree in which every node except the leaves point to two nodes

Complete

a tree in which the root and branches point to two nodes, and the links of the leaves are scew to the left

Here is a model of a binary tree which holds color to demonstrate the terms. The Root of this tree is Red. The leaves of the tree are Blue, Purple, and Green. The only branch in the tree is Yellow. This tree is of size three or two depending on how you count. Red is a parent of Yellow and Green. Yellow and Green are children of Red. Green has no children. Yellow is a parent of Blue and Purple. Blue and Purple are children of Red. Red is an ancestor of all other nodes. All nodes except Red are descendants of Red. Yelow's desendants are Blue and Purple. Green has no descendants. Red has no siblings. Yellow and Green are siblings. Purple and Blue are siblings. The nodes of Yellow, Blue, and Purple form the left subtree of Red. Green forms the right subtree of Red. If Green pointed to two nodes or Yellow pointed to no nodes, then the tree would be full. However this tree is complete.

Completeness is difficult term to describe but easy to show in models. Here is a picture of progressive larger complete trees.

Since a tree is basically a node it just has an altered definition. Adding and deletion are just the same, but there will be a specialized form of it latter. For now the only implementation are a size(), and height() function along with some printing. The prints will print the node in pre, in, and postfix traversals. In the example a prefix traversal would be Red, Yellow, Blue, and Green. A infix traversal would be Blue, Yellow, Purple, Red and Green. A postfix traversal would be Blue, Purple, Yellow, Green, Red. All of these functions are simple and done with recursion, and simple changes will effect the fuctions outcome. Also do not forget to check for NULL pointers before execution.

class BTNode
{
   public:
   BTNode(int i, BTNode* r=NULL, BTNode* l=NULL);
   
   static size(BTNode* root);   //same as before
   static height(BTNode* root);  //same as before

   static void prePrint(BTNode* root, ostream& os);
   static void inPrint(BTNode* root, ostream& os);
   static void postPrint(BTNode* root, ostream& os);
         
   
   private:
      int data;
      BTNode* left;
      BTNode* right;
};  

Performance

With the structure of the tree and how basic functions are implemented Big Oh is hard to caculation. From previous containers the order of the function is just the order of the largest operation group. In this tree however only simple operators and recursive calls are made. So unless the order of how the recursive calls are larger than constants then the order goes up. The worst case tree is when all the nodes either point left or right. In that case the tree is practicall just a linked list, so functions are linear, O(n). The best case is when the tree is "bushy" i.e. having the nodes balanced on both side and they fill the tree. In that case function calls are split in two everytime they are called. This gives a DIV 2 situation which is logarithmic, so the best case tree have O(log n) functions.

Prev -- Back to Portal -- Next