Create a C program which implements a Binary Search Tree Example of the structur
ID: 3827550 • Letter: C
Question
Create a C program which implements a Binary Search Tree
Example of the structure:
typedef struct node_struct {
int data;
struct node_struct * left;
struct node_struct * right;
} node;
Consisting of active internet connections detected by your computer. There are a number of ways to do this, but the easiest is to use a Unix utility called netstat. Note: this utility is also available on Windows if you do not have access to a Linux or Mac environment.
Example: ~$ netstat -l
Active Internet connections (only servers)
Proto Recv-Q Send-Q Local Address Foreign Address State
tcp 0 0 localhost:ipp *:* LISTEN
tcp6 0 0 ip6-localhost:ipp [::]:* LISTEN
udp 0 0 *:mdns *:*
udp 0 0 *:53225 *:*
udp 0 0 *:bootpc *:*
udp 0 0 *:ipp *:*
udp6 0 0 [::]:mdns [::]:*
udp6 0 0 [::]:57995 [::]:*
raw6 0 0 [::]:ipv6-icmp [::]:* 7
Active UNIX domain sockets (only servers)
Proto RefCnt Flags Type State I-Node Path
unix 2 [ ACC ] STREAM LISTENING 25249 /var/run/NetworkManager/private-dhcp
unix 2 [ ACC ] STREAM LISTENING 26731 /run/user/1000/systemd/private
unix 2 [ ACC ] SEQPACKET LISTENING 11017 /run/udev/control
unix 2 [ ACC ] STREAM LISTENING 26738 /run/user/1000/keyring/control
unix 2 [ ACC ] STREAM LISTENING 26814 /run/user/1000/keyring/ssh
unix 2 [ ACC ] STREAM LISTENING 25747 /run/user/1000/keyring/pkcs11
unix 2 [ ACC ] STREAM LISTENING 24651 /run/user/1000/pulse/native
unix 2 [ ACC ] STREAM LISTENING 27985 com.canonical.Unity.Master.Scope.files.T1406627567860
unix 2 [ ACC ] STREAM LISTENING 23959 @/tmp/.ICE-unix/3282
unix 2 [ ACC ] STREAM LISTENING 22815 @/tmp/.X11-unix/X0
unix 2 [ ACC ] STREAM LISTENING 26842 @/tmp/dbus-nJfsoJKk
unix 2 [ ACC ] STREAM LISTENING 11012 /run/systemd/private
unix 2 [ ACC ] STREAM LISTENING 11018 /run/systemd/journal/stdout
unix 2 [ ACC ] STREAM LISTENING 11021 /run/systemd/fsck.progress
unix 2 [ ACC ] STREAM LISTENING 28001 -com.canonical.Unity.Scope.files.T1407946325823
unix 2 [ ACC ] STREAM LISTENING 24925 com.canonical.Unity.Scope.applications.T1412500939537
unix 2 [ ACC ] STREAM LISTENING 19514 /var/run/cups/cups.sock
unix 2 [ ACC ] STREAM LISTENING 27984 com.canonical.Unity.Master.Scope.applications.T1406617406377
unix 2 [ ACC ] STREAM LISTENING 22816 /tmp/.X11-unix/X0
unix 2 [ ACC ] STREAM LISTENING 23960 /tmp/.ICE-unix/3282
unix 2 [ ACC ] STREAM LISTENING 34180 /tmp/OSL_PIPE_1000_SingleOfficeIPC_abae68bf719d75156fb5dc304a89cd31
unix 2 [ ACC ] STREAM LISTENING 26767 @/com/ubuntu/upstart-session/1000/3060
unix 2 [ ACC ] STREAM LISTENING 25696 @/tmp/dbus-BS7XosvL1E
unix 2 [ ACC ] STREAM LISTENING 19515 /var/run/dbus/system_bus_socket
unix 2 [ ACC ] STREAM LISTENING 19516 /run/snapd.socket
unix 2 [ ACC ] STREAM LISTENING 19517 /run/acpid.socket
unix 2 [ ACC ] STREAM LISTENING 19518 /run/uuidd/request
unix 2 [ ACC ] STREAM LISTENING 18859 /var/run/avahi-daemon/socket
unix 2 [ ACC ] STREAM LISTENING 24926 com.canonical.Unity.Scope.scopes.T1412511618378
unix 2 [ ACC ] STREAM LISTENING 26968 @/tmp/dbus-zcBN8OtIUe
Insert the data into a structure with an attribute for each output column (out c program). The output of netstat is as follows:
Protocol, Recv-Queue size, Send-Queue size, Local Address, Foreign Address, State
So your struct should resemble the following (state can be an enum if you’d like but it’s not required):
struct netstat_data {
char* protocol;
int recv_q;
int send_q;
char* local_address;
char* foreign_address;
char* state;
};
Build the Binary Search Tree such that it is ordered by foreign address. It is a char* so even if you are comparing IP addresses (which consist mostly of integers) to hostnames (strings), you will get a valid result.
Remember that binary trees have a special property that keeps their nodes ordered. When you insert a new node, it must be inserted in the proper place so that the rest of the tree makes sense. So, every node contains a data field. For each node, the data field of its right child is greater than its data field. And the data field of its right child is less than its data field. Each node at most has two children.
Example:
All we need in the C program to do is take the list, sort it into a binary tree based off of its Foreign Address then do an In order traversal and allow you to add nodes.
Example of traversal code:
void inorder_traversal(NODE* root) {
if(root != NULL) {
inorder_traversal(root->left);
printf("value: %d ", root->data);
inorder_traversal(root->right);
}
}
For extra credit we can print out the depth of the tree, how many nodes are in the tree, make it a Red-Black Tree defined as a self-balancing trees which contain extra data (either red or black). The color allows insertion to preserve balance by alternating colors and it also guarantees searching in O(log n) time.
Also when doing the adding remember Make sure the current root exists (node != NULL) Remember each node is a subtree itself, so when you move down the tree, each node you visit becomes the root of that subtree.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
struct btnode
{
int value;
struct btnode *l;
struct btnode *r;
}*root = NULL, *temp = NULL, *t2, *t1;
void delete1();
void insert();
void delete();
void inorder(struct btnode *t);
void create();
void search(struct btnode *t);
void preorder(struct btnode *t);
void postorder(struct btnode *t);
void search1(struct btnode *t,int data);
int smallest(struct btnode *t);
int largest(struct btnode *t);
int flag = 1;
void main()
{
int ch;
printf(" OPERATIONS ---");
printf(" 1 - Insert an element into tree ");
printf("2 - Delete an element from the tree ");
printf("3 - Inorder Traversal ");
printf("4 - Preorder Traversal ");
printf("5 - Postorder Traversal ");
printf("6 - Exit ");
while(1)
{
printf(" Enter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
inorder(root);
break;
case 4:
preorder(root);
break;
case 5:
postorder(root);
break;
case 6:
exit(0);
default :
printf("Wrong choice, Please enter correct choice ");
break;
}
}
}
void insert()
{
create();
if (root == NULL)
root = temp;
else
search(root);
}
void create()
{
int data;
printf("Enter data of node to be inserted : ");
scanf("%d", &data);
temp = (struct btnode *)malloc(1*sizeof(struct btnode));
temp->value = data;
temp->l = temp->r = NULL;
}
void search(struct btnode *t)
{
if ((temp->value > t->value) && (t->r != NULL))
search(t->r);
else if ((temp->value > t->value) && (t->r == NULL))
t->r = temp;
else if ((temp->value < t->value) && (t->l != NULL))
search(t->l);
else if ((temp->value < t->value) && (t->l == NULL))
t->l = temp;
}
void inorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
if (t->l != NULL)
inorder(t->l);
printf("%d -> ", t->value);
if (t->r != NULL)
inorder(t->r);
}
void delete()
{
int data;
if (root == NULL)
{
printf("No elements in a tree to delete");
return;
}
printf("Enter the data to be deleted : ");
scanf("%d", &data);
t1 = root;
t2 = root;
search1(root, data);
}
void preorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
printf("%d -> ", t->value);
if (t->l != NULL)
preorder(t->l);
if (t->r != NULL)
preorder(t->r);
}
void postorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display ");
return;
}
if (t->l != NULL)
postorder(t->l);
if (t->r != NULL)
postorder(t->r);
printf("%d -> ", t->value);
}
void search1(struct btnode *t, int data)
{
if ((data>t->value))
{
t1 = t;
search1(t->r, data);
}
else if ((data < t->value))
{
t1 = t;
search1(t->l, data);
}
else if ((data==t->value))
{
delete1(t);
}
}
void delete1(struct btnode *t)
{
int k;
if ((t->l == NULL) && (t->r == NULL))
{
if (t1->l == t)
{
t1->l = NULL;
}
else
{
t1->r = NULL;
}
t = NULL;
free(t);
return;
}
else if ((t->r == NULL))
{
if (t1 == t)
{
root = t->l;
t1 = root;
}
else if (t1->l == t)
{
t1->l = t->l;
}
else
{
t1->r = t->l;
}
t = NULL;
free(t);
return;
}
else if (t->l == NULL)
{
if (t1 == t)
{
root = t->r;
t1 = root;
}
else if (t1->r == t)
t1->r = t->r;
else
t1->l = t->r;
t == NULL;
free(t);
return;
}
else if ((t->l != NULL) && (t->r != NULL))
{
t2 = root;
if (t->r != NULL)
{
k = smallest(t->r);
flag = 1;
}
else
{
k =largest(t->l);
flag = 2;
}
search1(root, k);
t->value = k;
}
}
int smallest(struct btnode *t)
{
t2 = t;
if (t->l != NULL)
{
t2 = t;
return(smallest(t->l));
}
else
return (t->value);
}
int largest(struct btnode *t)
{
if (t->r != NULL)
{
t2 = t;
return(largest(t->r));
}
else
return(t->value);
}