a) Write an algorithm for deletion of a node from a doubly-linked list.
b) What is a threaded binary tree ? Write an algorithm for non-recursive in-order traversal of a threaded binary tree.
a) Algorithm:
Let the node to be deleted is del.
1) If node to be deleted is head node, then change the head pointer to next current head.
2) Set next of previous to del, if previous to del exixts.
3) Set prev of next to del, if next to del exixts.
struct node {
int data;
struct node *next;
struct node *prev;
};
void deleteNode(struct node **head_ref, struct node *del) {
/* base case */
if(*head_ref == NULL || del == NULL)
return;
/* If node to be deleted is head node */
if(*head_ref == del)
*head_ref = del->next;
/* Change next only if node to be deleted is NOT the last node */
if(del->next != NULL)
del->next->prev = del->prev;
/* Change prev only if node to be deleted is NOT the first node */
if(del->prev != NULL)
del->prev->next = del->next;
/* Finally, free the memory occupied by del*/
free(del);
return;
}
b) A threaded binary tree is a binary tree variant that allows fast traversal: given a pointer to a node in a threaded tree, it is possible to cheaply find it in-order successor (and/or predecessor).
Threads are constructed using the following rules:
– A 0 rightChild field at node p is replaced by a pointer to the node that would be visited afterp when traversing the tree in inorder. Thatis, It is replaced by the inorder successor of p.
– A 0 leftChild link at node p is replaced by a pointer to the node that immediately precedes node p in inorder (i.e., it is replaced by the inorder predecessor of p).
"
a) Sort the following list using the Radix Sort :
189, 205, 986, 421, 97, 192, 535, 839, 562, 674
Define the ADT for stack. Show the implementation of the stack data structure using linked list.
Difference between Inspections and Walkthrough
Write a C program to find factorial(using recursion) of any no.
Distinguish between Decision table versus decision tree
What is WAP? Why it is used?
Difference between ISO and CMM standards.
Discuss the different stages of ‘Capability Maturity Model’.
