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 youd like but its 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.