Page 139 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Explanation

This program first creates a binary tree with a specified number of nodes with their

respective data values. It then takes the data value of the node to be deleted, obtains a
pointer to the node containing that data value, and obtains another pointer to the root of
the node to be deleted. Depending on whether the node to be deleted is a root node, a node
with two children a node with only one child, or a node with no children, it carries out the
manipulations as discussed in the section on deleting a node. After deleting the specifi ed
node, it returns the pointer to the root of the tree.
Input:
1. The number of nodes that the tree to be created should have
2. The data values of each node in the tree to be created
3. The data value in the node to be deleted

Output:
1. The data values of the nodes in the tree in inorder before deletion
2. The data values of the nodes in the tree in inorder after deletion
Question
Write a C program to count the number of non-leaf nodes of a binary tree.

6.5 Application of a Binary Search Tree

1. A prominent data structure used in many systems programming applications for
representing and managing dynamic sets.
2. Average case complexity of Search, Insert, and Delete Operations is O(log n), where n is the
number of nodes in the tree.
One of the applications of a binary search tree is the implementation of a dynamic dictionary.
A dictionary is an ordered list which is required to be searched frequently, and is also required
to be updated (insertions and deletions) frequently. Hence can be very well implemented using
a binary search tree, by making the entries of dictionary into the nodes of binary search tree.
A more efficient implementation of a dynamic dictionary involves considering a key to be a

sequence of characters, and instead of searching by comparison of entire keys, we use these
characters to determine a multi-way branch at each step, this will allow us to make a 26-way
branching according the first letter, followed by another branch according to the second letter

and so on.

A program to create a binary search tree, given a list of identifiers is given below:
char key[MAXLEN];
struct tnode
{
key name;
tnode *lchild;
tnode *rchild;
}
void btree()
{

134 LOVELY PROFESSIONAL UNIVERSITY