CHAPTER OUTLINE
15.1 Trees
15.2 Binary Trees
15.3 Types of Binary Tree
15.4 Binary T ree Representation
15.5 T raversing Binary T rees
15.6
Binary SearchTree
15.7
Insertion and Deletion Operations
15.8
HashingTechnology
Exercises
15.1 TREES
A tree is a predetermined non-empty set of items in which one element is called the root and the
remaining items are divided into n>=0 disjoint subsets, each of which can be a tree itself. Every item in
the tree is called a node. Every node in a tree can act as a root and can have zero or more branches
(subtrees). Fig. 15.1 shows the tree.
Fig. 15.1 Sample trees
15.2 BINARY TREES
A linked list is an efficient data structure as it saves memory. The main drawback of a linked list is that
it is linear. Every node has information of only the preceding or the following node. Hence, accessing
532 Programming and Data Structures
can only be done in a sequential manner. The binary tree is advantageous as it is a hierarchical data
structure.
A binary tree is a fixed set of nodes. It may be empty or divided into three disjoint subsets. The first
subset is called root of the tree. It contains a single element. The other two subsets are called right and
left subtrees of the main tree. The left and right branches can be vacant. Fig. 15.2 indicates a binary tree.
As shown in Fig. 15.2, the tree is formed with nine nodes named with alphabets. The first node at the
top is called the root, that is, A. Nodes B and C are its left and right subtrees, respectively. If there is no
subtree, it means an empty subtree. For example, node D does not have a right subtree and node C has
no left subtree.
The root of the binary tree is A. Node B can be either left or right subtree.
Hence, A is called the father of B. B is called the left or right son of A. A node without branches is
called a leaf. For example, E, G, J and H are leaves.
Fig. 15.3 Hierarchical structure of a tree
The hierarchical structure of a tree is illustrated in Fig. 15.3. From this figure, Node A can be called the
grandparent of G and H, because they are the children of C. Nodes B and C are brothers because their
root is same, A. In computer science, the tree data structure is represented with a root at the top and
leaves at the bottom.
The direction from leaves to root is called up and its reverse is called down. Traversing from leaves
to the root is called 'climbing' and its opposite is called 'descending/
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.