| Linked List |
|
| Concept of Linked List |
|
| A linked list is one of the fundamental data structures, and can be used to implement other data structures. It consists of a sequence of nodes, each containing arbitrary data fields and one or two references ("links") pointing to the next and/or previous nodes. The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk, allowing the list of items to be traversed in a different order. A linked list is a self-referential datatype because it contains a pointer or link to another datum of the same type. Linked lists permit insertion and removal of nodes at any point in the list in constant time, but do not allow random access. Several different types of linked list exist: singly-linked lists, doubly-linked lists, and circularly-linked lists. |
|
| An array is represented in memory using sequential mapping, which has the property that elements are fixed distance apart. |
|
|
| But this has the following disadvantage: |
- It makes insertion or deletion at any arbitrary position in an array a costly operation, because this involves the movement of some of the existing elements.
- When we want to represent several lists by using arrays of varying size, either we have to represent each list using a separate array of maximum size or we have to represent each of the lists using one single array.
- The first one will lead to wastage of storage, and the second will involve a lot of data movement.
|
|
| So we have to use an alternative representation to overcome these disadvantages. One alternative is a linked representation. In a linked representation, it is not necessary that the elements be at a fixed distance apart. Instead, we can place elements anywhere in memory, but to make it a part of the same list, an element is required to be linked with a previous element of the list. This can be done by storing the address of the next element in the previous element itself. This requires that every element be capable of holding the data as well as the address of the next element. Thus every element must be a structure with a minimum of two fields, one for holding the data value, which we call a data field, and the other for holding the address of the next element, which we call link field. |
| Therefore, a linked list is a list of elements in which the elements of the list can be placed anywhere in memory, and these elements are linked with each other using an explicit link field, that is, by storing the address of the next element in the link field of the previous element. |
|
|
| Types of linked lists |
|
| Linearly-linked list |
|
| Singly-linked list |
| The simplest kind of linked list is a singly-linked list (or slist for short), which has one link per node. This link points to the next node in the list, or to a null value or empty list if it is the final node. |
| A singly-linked list containing two values: the value of the current node and a link to the next node. |
|
| Doubly-linked list |
| A more sophisticated kind of linked list is a doubly-linked list or two-way linked list. Each node has two links: one points to the previous node, or points to a null value or empty list if it is the first node; and one points to the next, or points to a null value or empty list if it is the final node. |
| A doubly-linked list containing three integer values: the value, the link forward to the next node, and the link backward to the previous node |
| In some very low level languages, Xor-linking offers a way to implement doubly-linked lists using a single word for both links, although the use of this technique is usually discouraged. |
|
|
| Circularly-linked list |
|
| In a circularly-linked list, the first and final nodes are linked together. This can be done for both singly and doubly linked lists. To traverse a circular linked list, you begin at any node and follow the list in either direction until you return to the original node. Viewed another way, circularly-linked lists can be seen as having no beginning or end. This type of list is most useful for managing buffers for data ingest, and in cases where you have one object in a list and wish to see all other objects in the list. |
|
| The pointer pointing to the whole list may be called the access pointer. A circularly-linked list containing three integer values. |
|
| Singly-circularly-linked list |
| In a singly-circularly-linked list, each node has one link, similar to an ordinary singly-linked list, except that the next link of the last node points back to the first node. As in a singly-linked list, new nodes can only be efficiently inserted after a node we already have a reference to. For this reason, it's usual to retain a reference to only the last element in a singly-circularly-linked list, as this allows quick insertion at the beginning, and also allows access to the first node through the last node's next pointer. |
|
| Doubly-circularly-linked list |
| In a doubly-circularly-linked list, each node has two links, similar to a doubly-linked list, except that the previous link of the first node points to the last node and the next link of the last node points to the first node. As in doubly-linked lists, insertions and removals can be done at any point with access to any nearby node. Although structurally a doubly-circularly-linked list has no beginning or end, an external access pointer may formally establish the pointed node to be the head node or the tail node, and maintain order just as well as a doubly-linked list with sentinel nodes. |
|
| Sentinel nodes |
| Linked lists sometimes have a special dummy or sentinel node at the beginning and/or at the end of the list, which is not used to store data. Its purpose is to simplify or speed up some operations, by ensuring that every data node always has a previous and/or next node, and that every list (even one that contains no data elements) always has a "first" and "last" node. Lisp has such a design - the special value nil is used to mark the end of a 'proper' singly-linked list, or chain of cons cells as they are called. A list does not have toend in nil, but a list that did not would be termed 'improper'. |
|
|
|
|
| Linked List |
|
| Inserting a Node |
|
| A linked list is a recursive data structure. A recursive data structure is a data structure that has the same form regardless of the size of the data. You can easily write recursive programs for such data structures. |
|
|
|
| Example |
| Program |
|
# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node *p, int n)
{
struct node *temp;
if(p==NULL)
{
p=(struct node *)malloc(sizeof(struct node));
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p-> data = n;
p-> link = NULL;
}
else
p->link = insert(p->link,n);/* the while loop replaced by
recursive call */
return (p);
void printlist ( struct node *p )
{
printf("The data values in the list are\n");
while (p!= NULL)
{
printf("%d\t",p-> data);
p = p-> link;
}
}
void main()
{
int n;
int x;
struct node *start = NULL ;
printf("Enter the nodes to be created \n");
scanf("%d",&n);
while ( n- > 0 )
{
printf( "Enter the data values to be placed in a node\n");
scanf("%d",&x);
start = insert ( start, x );
}
printf("The created list is\n");
printlist ( start );
}
|
|
|
|
|
|
| Explanation |
|
- This recursive version also uses a strategy of inserting a node in an existing list to create the list.
- An insert function is used to create the list. The insert function takes a pointer to an existing list as the first parameter, and a data value with which the new node is to be created as the second parameter. It creates the new node by using the data value, then appends it to the end of the list. It then returns a pointer to the first node of the list.
- Initially, the list is empty, so the pointer to the starting node is NULL. Therefore, when insert is called the first time, the new node created by the insert functionbecomes the start node.
- Subsequently, the insert function traverses the list by recursively calling itself.
- The recursion terminates when it creates a new node with the supplied data value and appends it to the end of the list.
|
|
| Points to Remember |
- A linked list has a recursive data structure.
- Writing recursive programs for such structures is programmatically convenient.
|
|
|
|
|
| Linked List |
|
| Sorting and Reversing Link List |
|
| Introduction |
|
| To sort a linked list, first we traverse the list searching for the node with a minimum data value. Then we remove that node and append it to another list which is initially empty. We repeat this process with the remaining list until the list becomes empty, and at the end, we return a pointer to the beginning of the list to which all the nodes are moved, as shown in image below: |
|
|
|
|
|
| Sorting of a linked list |
|
| To reverse a list, we maintain a pointer each to the previous and the next node, then we make the link field of the current node point to the previous, make the previous equal to the current, and the current equal to the next, as shown in A linked list showing the previous, current, and next nodes at some point during reversal process. |
|
|
|
|
| Therefore, the code needed to reverse the list is |
|
Prev = NULL;
While (curr != NULL)
{
Next = curr->link;
Curr -> link = prev;
Prev = curr;
Curr = next;
} |
|
|
| Program |
|
# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node *p, int n)
{
struct node *temp;
if(p==NULL)
{
p=(struct node *)malloc(sizeof(struct node));
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p-> link = NULL;
}
else
{
temp = p;
while (temp-> link!= NULL)
temp = temp-> link;
temp-> link = (struct node *)malloc(sizeof(struct node));
if(temp -> link == NULL)
{
printf("Error\n");
exit(0);
}
temp = temp-> link;
temp-> data = n;
temp-> link = null;
}
return(p);
}
void printlist ( struct node *p )
{
printf("The data values in the list are\n");
while (p!= NULL)
{
printf("%d\t",p-> data);
p = p-> link;
}
}
/* a function to sort reverse list */
struct node *reverse(struct node *p)
{
struct node *prev, *curr;
prev = NULL;
curr = p;
while (curr != NULL)
{
p = p-> link;
curr-> link = prev;
prev = curr;
curr = p;
return(prev);
}
/* a function to sort a list */
struct node *sortlist(struct node *p)
{
struct node *temp1,*temp2,*min,*prev,*q;
q = NULL;
while(p != NULL)
{
prev = NULL;
min = temp1 = p;
temp2 = p -> link;
while ( temp2 != NULL )
{
if(min -> data > temp2 -> data)
{
min = temp2;
prev = temp1;
}
temp1 = temp2;
temp2 = temp2-> link;
}
if(prev == NULL)
p = min -> link;
else
prev -> link = min -> link;
min -> link = NULL;
if( q == NULL)
q = min; /* moves the node with lowest data value in the list
pointed to by p to the list
pointed to by q as a first node*/
else
{
temp1 = q;
/* traverses the list pointed to by q to get pointer to its
last node */
while( temp1 -> link != NULL)
temp1 = temp1 -> link;
temp1 -> link = min; /* moves the node with lowest data value
in the list pointed to
by p to the list pointed to by q at the end of list pointed by
}
}
return (q);
}
void main()
{
int n;
int x;
struct node *start = NULL ;
printf("Enter the nodes to be created \n");
scanf("%d",&n);
while ( n- > 0 )
{
printf( "Enter the data values to be placed in a
node\n");
scanf("%d",&x);
start = insert ( start,x);
}
printf("The created list is\n");
printlist ( start );
start = sortlist(start);
printf("The sorted list is\n");
printlist ( start );
start = reverse(start);
printf("The reversed list is\n");
printlist ( start );
}
|
|
| Explanation |
| The working of the sorting function on an example list is shown below |
|
|
|
|
|
| Sorting of a linked list |
|
| The working of a reverse function is shown below |
|
|
|
|
|
| Output: |
|
|
|
|
|
|
|
|
| Linked List |
|
| Counting No. of Nodes in a List |
|
| Counting the number of nodes of a singly linked list requires maintaining a counter that isinitialized to 0 and incremented by 1 each time a node is encountered in the process of traversing a list from the start. |
| Here is a complete program that counts the number of nodes in a singly linked chain p, where p is a pointer to the first node in the list. |
|
|
| Program |
|
# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node *, int);
int nodecount(struct node*);
void printlist ( struct node * );
struct node *insert(struct node *p, int n)
{
struct node *temp;
if(p==NULL)
{
p=(struct node *)malloc(sizeof(struct node));
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p-> data = n;
p-> link = NULL;
}
else
{
temp = p;
while (temp-> link!= NULL)
temp = temp-> link;
temp-> link = (struct node *)malloc(sizeof(struct node));
if(temp -> link == NULL)
{
printf("Error\n");
exit(0);
}
temp = temp-> link;
temp-> data = n;
temp-> link = NULL;
}
return (p);
}
void printlist ( struct node *p )
{
printf("The data values in the list are\n");
while (p!= NULL)
{
printf("%d\t",p-> data);
p = p-> link;
}
}
/* A function to count the number of nodes in a singly linked list */
int nodecount (struct node *p )
{
int count=0;
while (p != NULL)
{
count ++;
p = p->link;
}
return(count);
}
void main()
{
int n;
struct node *start = NULL ;
printf("Enter the nodes to be created \n");
scanf("%d",&n);
while ( n-- > 0 )
{
printf( "Enter the data values to be placed in a node\n");
scanf("%d",&x);
start = insert ( start,x);
}
printf("The created list is\n");
printlist ( start );
n = nodecount(start);
printf("The number of nodes in a list are: %d\n",n);
}
|
|
| Output: |
|
|
|
|
|
|
|
| Linked List |
|
| Deleting a Node from Link List |
|
| To delete a node, first we determine the node number to be deleted (this is based on the assumption that the nodes of the list are numbered serially from 1 to n). The list is thentraversed to get a pointer to the node whose number is given, as well as a pointer to a node that appears before the node to be deleted. Then the link field of the node that appears before the node to be deleted is made to point to the node that appears after the node to be deleted, and the node to be deleted is freed. Image 1 & 2 show the list before and after deletion, respectively. |
|
|
| Program |
|
# include <stdio.h>
# include <stdlib.h>
struct node *delet ( struct node *, int );
int length ( struct node * );
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node *p, int n)
{
struct node *temp;
if(p==NULL)
{
p=(struct node *)malloc(sizeof(struct node));
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p-> data = n;
p-> link = NULL;
}
else
{
temp = p;
while (temp-> link != NULL)
temp = temp-> link;
temp-> link = (struct node *)malloc(sizeof(struct node));
if(temp -> link == NULL)
{
printf("Error\n");
exit(0);
}
temp = temp-> link;
temp-> data = n;
temp-> link = NULL;
}
return (p);
}
void printlist ( struct node *p )
{
printf("The data values in the list are\n");
while (p!= NULL)
{
printf("%d\t",p-> data);
p = p-> link;
}
}
int main()
{
int n;
int x;
struct node *start = NULL;
printf("Enter the nodes to be created \n");
scanf("%d",&n);
while (( n--) > 0 )
{
printf( "Enter the data values to be placed in a node\n");
scanf("%d",&x);
start = insert ( start, x );
}
printf("\nThe list before deletion id\n");
printlist ( start );
printf("%\n Enter the node no \n");
scanf ( " %d",&n);
start = delet (start , n );
printf("\nThe list after deletion is\n");
printlist ( start );
printf("\n");
return 0;
}
/* a function to delete the specified node*/
struct node *delet ( struct node *p, int node_no )
{
struct node *prev, *curr ;
int i;
if (p == NULL )
{
printf("There is no node to be deleted \n");
}
else
{
if ( node_no > length (p))
{
printf("Error\n");
}
else
{
prev = NULL;
curr = p;
i = 1 ;
while ( i < node_no )
{
prev = curr;
curr = curr-> link;
i = i+1;
}
if ( prev == NULL )
{
p = curr -> link;
free ( curr );
}
else
{
prev -> link = curr -> link ;
free ( curr );
}
}
}
return(p);
}
/* a function to compute the length of a linked list */
int length ( struct node *p )
{
int count = 0 ;
while ( p != NULL )
{
count++;
p = p->link;
}
return ( count ) ;
}
|
|
|
| Explanation |
|
|
|
|
|
| Output: |
|
|
|
|
|
|
|
| Linked List |
|
| Doubly Link List |
|
| A more sophisticated kind of linked list is a doubly-linked list or two-way linked list. Each node has two links: one points to the previous node, or points to a null value or empty listif it is the first node; and one points to the next, or points to a null value or empty list if it is the final node. |
|
|
|
|
|
|
| The following are problems with singly linked lists: |
|
| A singly linked list allows traversal of the list in only one direction. Deleting a node from a list requires keeping track of the previous node, that is, the node whose link points to the node to be deleted. If the link in any node gets corrupted, the remaining nodes of the list become unusable. |
|
| These problems of singly linked lists can be overcome by adding one more link to each node, which points to the previous node. When such a link is added to every node of a list, the corresponding linked list is called a doubly linked list. Therefore, a doubly linked list is a linked list in which every node contains two links, called left link and right link, respectively. The left link of the node points to the previous node, whereas the right points to the next node. Like a singly linked list, a doubly linked list can also be a chain or it may be circular with or without a header node. If it is a chain, the left link of the first node and the right link of the last node will be NULL, as shown in image below: |
|
|
|
|
|
| If it is a circular list without a header node, the right link of the last node points to the first node. The left link of the first node points to the last node, as shown in image below |
|
|
|
|
|
| If it is a circular list with a header node, the left link of the first node and the right link of the last node point to the header node. The right link of the header node points to the first node and the left link of the header node points to the last node of the list, as shown in image below: |
|
|
|
|
| Therefore, the following representation is required to be used for the nodes of a doubly linked list. |
struct dnode
{
int data;
struct dnode *left,*right;
}; |
|
|
| Program |
|
| A program for building and printing the elements of a doubly linked list follows: |
|
# include <stdio.h>
# include <stdlib.h>
struct dnode
{
int data;
struct dnode *left, *right;
};
struct dnode *insert(struct dnode *p, struct dnode **q, int n)
{
struct dnode *temp;
/* if the existing list is empty then insert a new node as the starting node */
if(p==NULL)
{
p=(struct dnode *)malloc(sizeof(struct dnode));
/* creates new node data value passed as parameter */
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p->data = n;
p-> left = p->right =NULL;
*q =p;
}
else
{
temp = (struct dnode *)malloc(sizeof(struct dnode));
/* creates new node using data value passed as parameter and puts its address in the temp */
if(temp == NULL)
{
printf("Error\n");
exit(0);
}
temp->data = n;
temp->left = (*q);
temp->right = NULL;
(*q)->right = temp;
(*q) = temp;
}
return (p);
}
void printfor( struct dnode *p )
{
printf("The data values in the list in the forward order are:\n");
while (p!= NULL)
{
printf("%d\t",p-> data);
p = p->right;
}
}
void printrev( struct dnode *p )
{
printf("The data values in the list in the reverse order are:\n");
while (p!= NULL)
{
printf("%d\t",p->data);
p = p->left;
}
}
int main()
{
int n;
int x;
struct dnode *start = NULL ;
struct dnode *end = NULL;
printf("\n");
printf("\nEnter the nodes to be created \t:");
scanf("%d",&n);
while ( n-- > 0 )
{
printf( "\nEnter the data values to be placed in a node\t");
scanf("%d",&x);
start = insert ( start, &end,x );
}
printf("\nThe created list is\n");
printfor ( start );
printf("\n");
printrev(end);
printf("\n");
return 0;
}
|
|
|
| Explanation |
|
- This program uses a strategy of inserting a node in an existing list to create it. For this, an insert function is used. The insert function takes a pointer to an existing list as the first parameter.
- The pointer to the last node of a list is the second parameter. A data value with which the new node is to be created is the third parameter. This creates a new node using the data value, appends it to the end of the list, and returns a pointer to the first node of the list. Initially, the list is empty, so the pointer to the start node isNULL. When insert is called the first time, the new node created by the insert becomes the start node.
- Subsequently, insert creates a new node that stores the pointer to the created node in a temporary pointer. Then the left link of the node pointed to by the temporary pointer becomes the last node of the existing list, and the right link points to NULL. After that, it updates the value of the end pointer to make it point to this newly appended node.
- The main function reads the value of the number of nodes in the list, and calls insert that many times by going in a while loop, in order to get a doubly linked listwith the specified number of nodes created.
|
|
| Output: |
|
|
|
|
|
|
|
| Tree |
|
| Concept of Tree |
|
| Definition of Tree |
|
| A tree is a widely-used data structure that emulates a tree structure with a set of linked nodes. |
|
| A tree is a set of one or more nodes T such that: |
| there is a specially designated node called a root The remaining nodes are partitioned into n disjointed set of nodes T1, T2,…,Tn, each of which is a tree. |
|
|
|
|
| Trees are used to impose a hierarchical structure on a collection of data items. For example, we need to impose a hierarchical structure on a collection of data items while preparing organizational charts and geneologies to represent the syntactic structure of a source program in compilers. So the study of trees as one of the data structures is important. |
|
|
| Degree of a Node of a Tree |
|
| The degree of a node of a tree is the number of subtrees having this node as a root. In other words, the degree is the number of descendants of a node. If the degree is zero, it is called a terminal or leaf node of a tree. |
|
| Degree of a Tree |
| The degree of a tree is defined as the maximum of degree of the nodes of the tree, that is, degree of tree = max (degree(node i) for I = 1 to n) |
|
| Level of a Node |
| We define the level of the node by taking the level of the root node as 1, and incrementing it by 1 as we move from the root towards the subtrees. So the level of all the descendants of the root nodes will be 2. The level of their descendants will be 3, and so on. We then define the depth of the tree to be the maximum value of the level of the node of the tree. |
|
|
|
|
|
| Tree |
|
| Binary Tree |
|
| 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 special case of tree as defined in the preceding section, in which no node of a tree can have a degree of more than 2. Therefore, a binary tree is a set of zero or more nodes T such that: |
| there is a specially designated node called the root of the tree the remaining nodes are partitioned into two disjointed sets, T1 and T2, each of which is a binary tree. T1 is called the left subtree and T2 is called right subtree, or vice-versa. |
|
|
| Types of Binary Tree |
|
|
- A rooted binary tree is a rooted tree in which every node has at most two children.
- A full binary tree, or proper binary tree, is a tree in which every node has zero or two children.
- A perfect binary tree (sometimes complete binary tree) is a full binary tree in which all leaves are at the same depth.
- A complete binary tree is a tree with n levels, where for each level d <= n - 1, the number of existing nodes at level d is equal to 2d. This means all possible nodes exist at these levels. An additional requirement for a complete binary tree is that for the nth level, while every node does not have to exist, the nodes that do exist must fill from left to right. (This is ambiguous with perfect binary tree.)
- A balanced binary tree is where the depth of all the leaves differs by at most 1.
- A rooted complete binary tree can be identified with a free magma.
- An almost complete binary tree is a tree in which each node that has a right child also has a left child. Having a left child does not require a node to have a right child. Stated alternately, an almost complete binary tree is a tree where for a right child, there is always a left child, but for a left child there may not be a right child.
- A degenerate tree is a tree where for each parent node, there is only one associated child node. This means that in a performance measurement, the tree will behave like a linked list data structure.
- The number of nodes n in a perfect binary tree can be found using this formula: n = 2h + 1 − 1 where h is the height of the tree.
- The number of leaf nodes n in a perfect binary tree can be found using this formula:n = 2h where h is the height of the tree.
|
|
|
| Representation of a Binary Tree |
|
| If a binary tree is a complete binary tree, it can be represented using an array capable of holding n elements where n is the number of nodes in a complete binary tree. If the tree is an array of n elements, we can store the data values of the ith node of a complete binary tree with n nodes at an index i in an array tree. That means we can map node i to the ith index in the array, and the parent of node i will get mapped at an index i/2, whereas the left child of node i gets mapped at an index 2i and the right child gets mapped at an index 2i + 1. For example, a complete binary tree with depth k = 3, having the number of nodes n = 5, can be represented using an array of 5 as shown in image below: |
|
|
|
|
| An array representation of a binary tree is not suitable for frequent insertions and deletions, even though no storage is wasted if the binary tree is a complete binary tree. It makes insertion and deletion in a tree costly. Therefore, instead of using an array representation, we can use a linked representation, in which every node is represented as a structure with three fields: one for holding data, one for linking it with the left subtree, and the third for linking it with right subtree as shown here: |
|
|
|
| We can create such a structure using the following C declaration: |
struct tnode
{
int data
struct tnode *lchild,*rchild;
}; |
|
| A tree representation that uses this node structure is shown below: |
|
|
|
|
|
|
|
| Tree |
|
| Binary Tree Traversal |
|
|
| Order of Traversal of Binary Tree |
|
| The following are the possible orders in which a binary tree can be traversed: |
LDR
LRD
DLR
RDL
RLD
DRL |
|
|
| Where L stands for traversing the left subtree, R stands for traversing the right subtree, and D stands for processing the data of the node. Therefore, the order LDR is the order of traversal in which we start with the root node, visit the left subtree, process the data of the root node, and then visit the right subtree. Since the left and right subtrees are also the binary trees, the same procedure is used recursively while visiting the left and right subtrees. |
|
| The order LDR is called as inorder; the order LRD is called as postorder; and the order DLR is called as preorder. The remaining three orders are not used. If the processing that we do with the data in the node of tree during the traversal is simply printing the data value, then the output generated for a tree is given in image below, using inorder, preorder andpostorder as shown. |
|
|
|
|
|
| If an expression is represented as a binary tree, the inorder traversal of the tree gives us an infix expression, whereas the postorder traversal gives us a postfix expression as shown below: |
|
|
|
A binary tree of an expression along with its inorder and postorder.
|
|
|
|
| Tree |
|
| Searching Binary Tree |
|
| A Binary Search Tree is a binary tree that may be empty, and every node must contain an identifier. An identifier of any node in the left subtree is less than the identifier of the root. An identifier of any node in the right subtree is greater than the identifier of the root. Both the left subtree and right subtree are binary search trees. |
|
|
|
|
|
| The Binary Search Tree is basically a binary tree, and therefore it can be traversed ininorder, preorder, and postorder. If we traverse a binary search tree in inorder and print the identifiers contained in the nodes of the tree, we get a sorted list of identifiers in ascending order. |
|
| A Binary Search Tree is an important search structure. For example, consider the problem of searching a list. If a list is ordered, searching becomes faster if we use a contiguous list and perform a binary search. But if we need to make changes in the list, such as inserting new entries and deleting old entries, using a contiguous list would be much slower, because insertion and deletion in a contiguous list requires moving many of the entries every time. So we may think of using a linked list because it permits insertions and deletions to be carried out by adjusting only a few pointers. But in an n-linked list, there is no way to move through the list other than one node at a time, permitting only sequential access. Binary trees provide an excellent solution to this problem. By making the entries of an ordered list into the nodes of a binary search tree, we find that we can search for a key in O(n logn) steps. |
|
|
| The Program |
|
| The following program shows how to build a binary tree in a C program. It uses dynamic memory allocation, pointers and recursion. A binary tree is a very useful data-structure, since it allows efficient insertion, searching and deletion in a sorted list. As such a tree is essentially a recursively defined structure, recursive programming is the natural and efficient way to handle it. |
|
- tree
- empty
- node left-branch right-branch
|
|
#include<stdlib.h>
#include<stdio.h>
struct tree_el {
int val;
struct tree_el * right, * left;
};
typedef struct tree_el node;
void insert(node ** tree, node * item) {
if(!(*tree)) {
*tree = item;
return;
}
if(item->val<(*tree)->val)
insert(&(*tree)->left, item);
else if(item->val>(*tree)->val)
insert(&(*tree)->right, item);
}
void printout(node * tree) {
if(tree->left) printout(tree->left);
printf("%d\n",tree->val);
if(tree->right) printout(tree->right);
}
void main() {
node * curr, * root;
int i;
root = NULL;
for(i=1;i<=10;i++) {
curr = (node *)malloc(sizeof(node));
curr->left = curr->right = NULL;
curr->val = rand();
insert(&root, curr);
}
printout(root);
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 comments: