UTEP

TUTORIAL TOPIC 12.10

What is a binary tree?

 

A binary is a hierarchical structure which can have two branches maximum. It is a linked list that incorporates a binary search strategy.

A binary tree is intended to approximate the speed of a binary search while allowing us to dynamically allocate records and store them non-contiguously.

Here is a sample of a binary tree...

The terminology used in these trees is the following:

 

Parent : Is the one that always has a dependant.

Children : Is the dependant of the parent which is on top.

 

A binary tree is a tree that may have no nodes (empty tree) or if there are nodes, the following rules apply.

· There is a root node.

· Each node, except the root, must have only 1 parent.

· Each node may have at most 2 children called the left child and the right child.

For a node in a binary tree, the node beginning with its left child and below is its left sub-tree. The node beginning with its right child and below is its right sub-tree. Notice that a binary tree can have no nodes, let's define the depth of the empty tree as-1. The depth or height of a node is the depth of the parent plus 1 with the root node having depth of zero. In a full binary tree, every leaf node has the same depth. In a complete binary tree, the levels above the deepest represent a full tree, and the nodes at the deepest level are arranged in order beginning at the left most position. The following are examples of full and complete binary trees. All full binary trees are also complete.

In English, Binary trees are used to make programmer’s  lives easier. The good thing is that it helps out in the search process. The bad thing is that it may take a long time to do the search and to code.