564 Programming and Data Structures
Explanation As usual, the arrays are declared by using arr[], inl[], in2[], in3[], in4[] and in5[], each
having a length of 5. By using len gth (); function, the length of each key is calculated and the keys are
placed in the appropriate index. The number which is to be searched is input through the keyboard.
Here, snum variable is declared. Its length is calculated by using le n g t h () ; and by knowing the
length it is searched in the hash table.
SUMMARY
The following concepts are described in this chapter.
1) 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.
2) A binary tree is a fixed set of nodes. It may be empty or divided into three disjoint subsets. The
first subset is called the root of the tree. It contains a single element. The other two subsets are
called right and left subtrees of the main tree.
3) Types of binary tree: (a) strictly binary tree, (b) complete binary tree, (c) extended binary tree.
4) Like a list, a binary tree is also implemented in two ways: static implementation using arrays
and dynamic implementation using pointers (linked list).
5) The binary tree can be traversed in three w a y s: inorder, preorder and postorder.
6) A binary search tree is a binary tree in which each node of the tree contains a value larger than
all nodes of its left subtree and smaller than all nodes of its right subtree.
7) Searching and insertion operations are related with each other in a binary search tree. Before
performing insertion operation, the location where the element is to be inserted is to be identified.
8) Hashing techniques are described with program implementation. Different techniques such as
division, length dependent and mid-square methods are elaborated.
EXERCISES
A) Answer the following questions.
1) Explain trees and binary trees.
2) Explain types of binary trees.
3) How are binary tree represented?
4) Explain different types of traversing trees.
5) What is a binary search tree?
6) Explain hashing technique.
7) Explain how insertion and deletion operations are done with a binary search tree.
8) Write an algorithm for DFS of a spanning tree.
9) What is a spanning tree? Write BFS algorithm for a spanning tree.
10) What are the differences between arrays and linked lists?
11) List the steps of operation of length dependent hashing searching method.
12) Describe the operation of hashing technique with division method.
Non-Linear Data Structure 565
13) Give the algorithm of mid-square hashing technique.
14) What is meant by folding an element? How is an element searched using this method?
Describe it.
B) Select the appropriate option for each of the following questions.
1) Every tree structure must contain
a) a root node
b) either left or right branch with a root node
c) both left and right branches with a root
d) all of the above
2) When every no-leaf node in a binary tree has filled left and right subtrees, the tree is called
a) strictly binary tree b) complete binary tree
c) binary search tree d) none of the above
3) The last node of a binary tree contains two branches. Such a tree is called
a) strictly binary tree b) complete binary tree
c) extended binary tree d) none of the above
4) The following sequence of traversing is called
Go to the root
Traverse the left subtree
Traverse the right subtrees
a) inorder b) postorder
c) preorder d) pre-post order
C) Attempt the following programs.
1) Write a program to create tree structure, perform insert and delete operations.
2) Write a program to traverse the binary search tree with different traversal methods such as
inorder, preorder and postorder.
3) Construct a binary tree for the following data:
Inorder: FE ACDGHBI
Postorder: EFCDHIBG A
4) What are the differences between a tree and a graph? Explain DFS and BFS algorithms.
5) Write C functions to insert a value into the linked list:
(i) at the beginning, (ii) at the end, (iii) after nth location.
6) Construct the binary tree for the following:
Preorder: AEFDJHIGBC
Inorder: FEAHJIDBGC
7) Write a C program to insert nodes into a binary tree and to traverse in preorder.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.