• BinaryTree

Binary Tree

The binary tree is a data structure that provides a combination of good searching & insertion time, convenient shape for many data manipulations and a nice implicit form that requires no pointer fields. The structure is formed up of data nodes, each node pointing to two children, usually referred to as the left child and the right child. The basic data structure will contain a data field, a right node and a left node. If the tree is used for searching at all, it will also usually contain a key field, and each node should maintain the property that the left child will contain a smaller key value and the right child will contain a larger key value than the current node (or vice versa). When this property is maintained in all the nodes in a binary tree, it becomes extremely easy to find nodes with a given key.

An example binary tree:

If you draw the tree on paper, you'll see it represents a binary expression - binary trees are often used, among other things, to manipulate and evaluate mathematical expressions. Another popular form of the binary tree is the implicit binary tree, in which the branching structure isn't explicitly stored.

An implicit binary tree:

In the implicit binary tree, you use a 1 based array to store all the information you need. Any given entry in the array is considered a node in the tree - you can calculate the offset of a given node's child like so:

l = k * 2
r = k * 2 + 1

Where k is the current node, l is the left child node and r is the right child node. The implicit binary tree given above is identical to the explicit binary tree in the first example. Implicit binary trees are valuable, used in algorithms such as HeapSort, but aren't as easily manipulated because nodes must stay in the same place in memory - splicing together trees is no longer so easy.

Related Data Structures

None yet.

Related Algorithms

None yet.

Sample Implementations

None yet.

Online Resources

None yet.