Twitter
Definition of a binary tree
A binary tree is a hierarchical structure in which every node can have up to two children. For each of the children, the node is considered as the parent. The children are considered siblings of each other. Consider the image below:
Binary Tree
This tree has A as it’s root node. H and B are the children of the root node A. H is the parent of nodes G and I. The height of this tree is 4 levels. F, E and D are called the leaves of this tree because they are nodes which do not have children.
Creation of a binary tree
A binary tree can be created using a self-referential structure similar to a linked list but with two pointers, one for the left node and one for the right node as shown:
typedef struct BiTreeNode_{
void* data;
struct BiTreeNode_* left;
struct BiTreeNode_* right;
}BiTreeNode;
Uses of a binary tree
- For maintaining the directory structure in an operating system.
- For organizing data in a database system because binary trees can be optimized for fast searching.
- In compilers where they are used for creating expression trees which are used for computing an expression.
- In artificial intelligence, where a large number of decision paths need to be considered such as for chess computations.
- In the creation of a binary search tree which is a very efficient data structure for searching elements.
Download an Implementation of a binary tree
In the next post, we will see the different traversal methods available to traverse a binary tree.
Related Posts:
Tags: programs
This is a rather confusing example to use for a description of a binary tree. I understand that it is lifted from the Wikipedia article on “Binary Tree”, but still. First, there are two nodes labeled 2 and two nodes labeled 5, it is not necessarily obvious which nodes are being referred to when you say that ’2′ is a root and ’5′ is a leaf, especially since no further definition of ‘root’ is given. Secondly, your definition of a leaf is incorrect. Leaves are nodes that have no children, regardless of the level at which they appear. The second, non-root ’2′ is also a leaf in this example.
[Reply]
Kevin Reply:
January 14th, 2010 at 6:06 pm
Thank you for your observation and comment. It helped me correct my mistake and be more careful in future posts especially when reading images.
[Reply]