What is Binary Tree?
A binary tree is a tree data structure
in which each node has at most two children. Typically the child nodes are
called left and right. One common use of binary trees is binary search trees;
another is binary heaps.
A Binary Tree is a finite set
of elements that is either empty or is partitioned into three disjoint subsets.
The first subset contains a single element called the Root of the tree. The
other two subsets are themselves Binary Trees, called the left and right
subtrees of the original tree. Binary Tree. A node of a Binary Tree can have at
most two Branches.
Graph theorists typically use the
following definition: A binary tree is a connected acyclic graph such that the
degree of each vertex is no more than 3. It can be shown that in any binary
tree, there are exactly two more nodes of degree one than there are of degree
three, but there can be any number of nodes of degree two. A rooted binary tree
is such a graph that has one of its vertices of degree no more than 2 singled
out as the root.
With the root thus chosen, each vertex
will have a uniquely defined parent, and up to two children; however, so far
there is insufficient information to distinguish a left or right child. If we
drop the connectedness requirement, allowing multiple connected components in
the graph, we call such a structure a forest.
Another way of defining binary trees is
a recursive definition of directed graphs. A binary tree is either:
(i) A single vertex.
(ii) A graph formed by taking two
binary trees, adding a vertex, and adding an edge directed from the new vertex
to the root of each binary tree.
This also does not establish the order
of children, but does fix a specific root node.
Another Definition of a binary tree is
The simplest form of a tree is a binary
tree. A binary tree consists of
a. a
node (called the root node) and
b. left
and right sub-trees.
Both the sub-trees are themselves
binary trees.
 |
| Binary Tree |
Types of binary tree
1. A
binary tree is a rooted tree in which every node has at most two children.
2. A
full binary tree is a tree in which every node has zero or two children.
3. A
perfect binary tree is a complete binary tree in which leaves (vertices with
zero children) are at the same depth (distance from the root, also called
height).Sometimes the perfect binary tree is called the complete binary tree.
Some others define a complete binary tree to be a full binary tree in which all
leaves are at depth n or n-1 for some n. In order for a tree to be a complete
binary tree, all the children on the last level must occupy the leftmost spots
consecutively, with no spot left unoccupied in between any 2. For example, if 2
nodes on the bottomost level each occupy a spot with an empty spot between the
2 of them, but the rest of the children nodes are tightly wedged together with
no spots in between, then the whole tree CANNOT be a binary tree due to the
empty spot.
Representing binary Trees in memory
Binary trees can be constructed from
programming language primitives in several ways. In a language with records and
references, binary trees are typically constructed by having a tree node
structure that contains some data and references to its left child and its
right child. Sometimes it also contains a reference to its unique parent. If a
node has fewer than two children, some of the child pointers may be set to a
special null value, or to a special sentinel node.
Binary trees can also be stored in
arrays, and if the tree is a complete binary tree, this method wastes no space.
In this compact arrangement, if a node has index i, its children are found
at indices 2*i and 2*i+1, This method benefits from more compact storage and
better locality of reference, particularly during a preorder traversal.
However, it requires contiguous memory, is expensive to grow, and wastes space
for a tree.
 |
| A Binary Tree |
The size of array for sequential
representation of tree is given by 2d+1 where d is the depth of the tree. The
depth of tree in figure 6.6 is 3. So, the tree requires 23+1 = 16 elements
sized array. The following array named tree gives the nodes of the tree stored
in array.
1 2
3 4 5
6 7 8
9 10 11
12 13 14
15 16
A
|
B
|
D
|
C
|
E
|
H
|
F
|
G
|
I
|
No comments:
Post a Comment