18 files changed, 1056 insertions, 0 deletions

diff --git a/c/dataStructure/408/fibo_1.c b/c/dataStructure/408/fibo_1.c
new file mode 100755
index 0000000..26cb3b2
--- /dev/null
+++ b/c/dataStructure/408/fibo_1.c
@@ -0,0 +1,29 @@
+#include<stdio.h>
+
+int fibo(int n)
+{
+    int res, a = 0, b = 1;
+
+    for (int i = 1; i <= n; i++)
+    {
+        if (i <= 1)
+            res = 1;
+        else
+        {
+            res = a + b;
+            a = b;
+            b = res;
+        }
+    }
+
+    return res;
+}
+
+int main(void)
+{
+    for (int i = 1; i <= 10; i++)
+        printf("%3d",fibo(i));
+    putchar('\n');
+
+    return 0;
+}
diff --git a/c/dataStructure/408/graph/Makefile b/c/dataStructure/408/graph/Makefile
new file mode 100755
index 0000000..d3565e8
--- /dev/null
+++ b/c/dataStructure/408/graph/Makefile
@@ -0,0 +1,18 @@
+CC = gcc
+FLGS = -Wall -Werror -g
+SRCS = *.c queue/queue.c
+OPT = graph
+
+all: link run clean
+
+link:
+	$(CC) $(SRCS) $(FLGS) -o $(OPT)
+
+run:
+	./$(OPT)
+
+gdb: link
+	gdb ./$(OPT)
+
+clean:
+	rm $(OPT)
diff --git a/c/dataStructure/408/graph/dgraph.c b/c/dataStructure/408/graph/dgraph.c
new file mode 100755
index 0000000..499fc0d
--- /dev/null
+++ b/c/dataStructure/408/graph/dgraph.c
@@ -0,0 +1,164 @@
+#include "graph.h"
+
+/* Thdse functions can use for both direct or undirect graph,
+ * only be affected by argument 'directed' we give
+ */
+
+void retreat(char * str)
+{
+    fprintf(stderr,"%s\n",str);
+    exit(EXIT_FAILURE);
+}
+
+void initializeGraph(graph * g, bool directed)
+{
+    int i;  /* counter */
+
+    g->nvertices = 0;
+    g->nedges = 0;
+    g->directed = directed;
+
+    for (i = 1; i <= MAXV; i++)
+        g->degree[i] = 0;
+    
+    for (i = 1; i <= MAXV; i++)
+        g->edges[i] = NULL;
+}
+
+/* x, y is a pair of vertices */
+void insertEdge(graph * g, int x, int y, bool directed)
+{
+    edgeNode * p;       /* temporary pointer */
+
+    p = (edgeNode *) malloc (sizeof(edgeNode));
+    if (!p)
+        retreat("Error allocate memory p");
+    
+    p->weight = 0;
+    p->y = y;
+
+    p->next = g->edges[x];      /* insert at head */
+    g->edges[x] = p;
+
+    g->degree[x]++;
+
+    if (!directed)
+        insertEdge(g,y,x,true);         /* add another one for undirected */
+    else
+        g->nedges++;
+}
+
+void readGraph(graph * g, bool directed)
+{
+    int i;      /* counter */
+    int m;      /* number of edges */
+    int x, y;   /* vertices in edge (x, y) / <x, y> */
+
+    printf("Enter number of vertices and edges: ");
+    scanf ("%d%d", &(g->nvertices), &m);    /* read number of vertices and edges */
+
+    printf("Enter two vertices consist one edge: ");
+    for (i = 1; i <= m; i++)
+    {
+        scanf("%d %d", &x, &y);             /* readindex and vertex */
+        insertEdge(g,x,y,directed);         /* this is the one to make a graph */
+    }
+}
+
+void printGraph(graph * g)
+{
+    int i;          /* counter */
+    edgeNode * p;   /* temporary pointer */
+
+    for (i = 1; i <= g->nvertices; i++)
+    {
+        printf("%d: ",i);
+        p = g->edges[i];
+        while (p)
+        {
+            printf(" %d", p->y);
+            p = p->next;
+        }
+        putchar('\n');
+    }
+}
+
+void purgeGraph(graph * g)
+{
+    int i;          /* counter */
+    edgeNode * p, * q;   /* temporary pointer */
+
+    for (i = 1; i < g->nvertices; i++)
+    {
+        p = g->edges[i];
+        while (p)
+        {
+            q = p;
+            p = p->next;
+            free(q);
+        }
+    }
+}
+
+void initializeSearch(graph * g)
+{
+    int i;
+
+//    time = 0;
+
+    for (i = 0; i <= g->nvertices; i++)
+    {
+        g->processed[i] = false;
+        g->discovered[i] = false;
+        g->parent[i] = -1;
+    }
+}
+
+void processVertexEarly(int v)
+{
+    printf("processed vertex %d\n",v);
+}
+void processVertexLate(int v)
+{
+}
+void processEdge(int v, int y)
+{
+    printf("Process edge (%d,%d)\n",v,y);
+}
+
+void bfs(graph * g, int start)
+{
+    queue q;    /* queue of vertices to visit */
+    int v;      /* current vertex */
+    int y;      /* successor vertex */
+    edgeNode * p; /* temporary pointer */
+
+    initializeSearch(g);
+
+    initQueue(&q);
+    enQueue(&q,start);
+    g->discovered[start] = true;
+
+    while (!emptyQueue(&q))
+    {
+        v = deQueue(&q);
+        processVertexEarly(v);
+        g->processed[v] = true;
+        p = g->edges[v];
+
+        while (p)
+        {
+            y = p->y;
+            if (!g->processed[y] || g->directed)
+                processEdge(v,y);
+            if (!g->discovered[y])
+            {
+                enQueue(&q,y);
+                g->discovered[y] = true;
+                g->parent[y] = v;
+            }
+            p = p->next;
+        }
+        processVertexLate(v);
+    }
+}
diff --git a/c/dataStructure/408/graph/graph.h b/c/dataStructure/408/graph/graph.h
new file mode 100755
index 0000000..98b18bb
--- /dev/null
+++ b/c/dataStructure/408/graph/graph.h
@@ -0,0 +1,45 @@
+#ifndef _GRAPH_H
+#define _GRAPH_H
+
+/*
+ * We can use this header for both
+ * directed graph or undirected graph
+ * by toggle boolean flag 'directed'
+ * in graph structure.
+ */
+
+#include<stdio.h>
+#include<stdbool.h>
+#include<stdlib.h>
+#include "queue/queue.h"
+
+#define MAXV 5  /* maximum number of vertices */
+
+typedef struct edgenode {
+    int y;      /* adjacency info */
+    int weight; /* edge weight if any */
+    struct edgenode * next;    /* next edge in list */
+} edgeNode;
+
+/* graph nodes start by 1 */
+typedef struct {
+    edgeNode * edges[MAXV + 1];     /* adjacency info */
+    int degree[MAXV + 1];            /* outdegree of each vertex */
+    int nvertices;                  /* number of vertices in graph */
+    int nedges;                     /* number of edges in graph */
+    bool directed;                   /* is the graph directed? */
+    bool discovered[MAXV + 1];
+    bool processed[MAXV + 1];
+    int parent[MAXV + 1];
+} graph;
+
+void retreat         (char * str);
+void initializeGraph(graph * g, bool directed);
+void readGraph      (graph * g, bool directed);
+void insertEdge     (graph * g, int x, int y, bool directed);
+void printGraph     (graph * g);
+void purgeGraph     (graph * g);
+void initializeSearch(graph * g);
+void bfs(graph * g, int start);
+
+#endif
diff --git a/c/dataStructure/408/graph/main.c b/c/dataStructure/408/graph/main.c
new file mode 100755
index 0000000..6219969
--- /dev/null
+++ b/c/dataStructure/408/graph/main.c
@@ -0,0 +1,17 @@
+#include "graph.h"
+
+int main(void)
+{
+    graph gh;
+    bool directed = true;
+    initializeGraph(&gh,directed);
+
+    readGraph(&gh,directed);
+
+    printGraph(&gh);
+    bfs(&gh, 1);
+
+    purgeGraph(&gh);
+
+    return 0;
+}
diff --git a/c/dataStructure/408/graph/queue/qtest.c b/c/dataStructure/408/graph/queue/qtest.c
new file mode 100755
index 0000000..61e01f2
--- /dev/null
+++ b/c/dataStructure/408/graph/queue/qtest.c
@@ -0,0 +1,21 @@
+#include "queue.h"
+
+int main(void)
+{
+    queue q;
+
+    initQueue(&q);
+    enQueue(&q,10);
+    enQueue(&q,12);
+    printQueue(&q);
+    printf("deQueue1: %d\n",deQueue(&q));
+    printf("deQueue2: %d\n",deQueue(&q));
+    enQueue(&q,14);
+    printHead(&q);
+    printQueue(&q);
+    purgeQueue(&q);
+    if(emptyQueue(&q))
+        puts("Empty Queue");
+
+    return 0;
+}
diff --git a/c/dataStructure/408/graph/queue/queue.c b/c/dataStructure/408/graph/queue/queue.c
new file mode 100755
index 0000000..673c595
--- /dev/null
+++ b/c/dataStructure/408/graph/queue/queue.c
@@ -0,0 +1,78 @@
+#include "queue.h"
+
+void initQueue(Queue q)
+{
+    q->qhead = NULL;
+    q->qtail = NULL;
+}
+
+void enQueue(Queue q, int y)
+{
+    elem * tmp = (elem*)malloc(sizeof(elem));
+
+    if (!tmp)
+        retreat("fail to enQueue");
+    tmp->y = y;
+    tmp->next = NULL;
+
+    if (!q->qtail)
+    {
+        q->qtail = tmp;
+        q->qhead = tmp;
+    }
+    else
+    {
+        q->qtail->next = tmp;
+        q->qtail = tmp;
+    }
+}
+
+int deQueue(Queue q)
+{
+    bool flag = false;
+    if (!q->qhead)
+        retreat("Empty queue");
+    if (q->qhead == q->qtail)
+        flag = true;
+    elem * tmp = q->qhead;
+    int p = tmp->y;
+    q->qhead = tmp->next;
+    free(tmp);
+    if (flag)
+        q->qtail = q->qhead;
+    return p;
+}
+
+bool emptyQueue(Queue q)
+{
+    if (q->qhead)
+        return false;
+    return true;
+}
+
+void purgeQueue(Queue q)
+{
+    elem * tmp;
+    while (q->qhead)
+    {
+        tmp = q->qhead;
+        q->qhead = tmp->next;
+        free(tmp);
+    }
+}
+
+void printHead(Queue q)
+{
+    printf("Queue head is %d\n", q->qhead->y);
+}
+
+void printQueue(Queue q)
+{
+    elem * tmp = q->qhead;
+    while (tmp)
+    {
+        printf("%d  ",tmp->y);
+        tmp = tmp->next;
+    }
+    printf("\n");
+}
diff --git a/c/dataStructure/408/graph/queue/queue.h b/c/dataStructure/408/graph/queue/queue.h
new file mode 100755
index 0000000..145e598
--- /dev/null
+++ b/c/dataStructure/408/graph/queue/queue.h
@@ -0,0 +1,26 @@
+#ifndef _QUEUE_H
+#define _QUEUE_H
+
+#include "../graph.h"
+
+typedef struct elem {
+    int y;
+    struct elem * next;
+} elem;
+
+typedef struct queue {
+    elem * qhead;
+    elem * qtail;
+} queue;
+
+typedef queue * Queue;
+
+void initQueue(Queue q);
+void enQueue(Queue q, int y);
+int  deQueue(Queue q);
+void purgeQueue(Queue q);
+bool emptyQueue(Queue q);
+void printHead(Queue q);
+void printQueue(Queue q);
+
+#endif
diff --git a/c/dataStructure/408/list/Makefile b/c/dataStructure/408/list/Makefile
new file mode 100755
index 0000000..0b76bbc
--- /dev/null
+++ b/c/dataStructure/408/list/Makefile
@@ -0,0 +1,24 @@
+CC = gcc
+
+FLGS = -Wall -Werror -g
+
+SSRCS = main.c sqlist.c
+LSRCS = main.c lklist.c
+
+OPT = ./list
+
+ALL: link run clean
+
+link:
+	$(CC) $(LSRCS) $(FLGS) -o $(OPT)
+list:
+	$(CC) $(SSRCS) $(FLGS) -o $(OPT)
+
+run:
+	$(OPT)
+
+gdb: $(OPT)
+	gdb $(OPT)
+
+clean:
+	rm $(OPT)
diff --git a/c/dataStructure/408/list/list.h b/c/dataStructure/408/list/list.h
new file mode 100755
index 0000000..811c62d
--- /dev/null
+++ b/c/dataStructure/408/list/list.h
@@ -0,0 +1,69 @@
+/*
+ * In order to use one header file for both
+ * sequence list and linked list, I used linked list style 
+ * this may cause inconvenient when inplementing sequence list
+ */
+
+#ifndef _LIST_H
+#define _LIST_H
+
+#include<stdio.h>
+#include<stdlib.h>
+#include<stdbool.h>
+
+#define MAX 50
+
+typedef struct seq {
+    int * data;
+    int length;
+    int maxSize;
+} Seq;
+typedef Seq * sqList;
+
+typedef struct link {
+    int elem;
+    struct link * next;
+} Link;
+typedef Link * linkList;
+
+typedef struct list {
+    sqList sql;
+    linkList lin;
+} List;
+
+/* initialize list
+ * exit with code EXIT_FAILURE if initialize fail,
+ * otherwise nothing return */
+void initList(List * L);
+
+/* return number of current elements
+ * if list does not exist, return -1 */
+int lengthList(List * L);
+
+/* find location of the element
+ * if element exists, return location
+ * else return false */
+bool locateElem(List * L, int * i, int e);
+
+/* find element at given location
+ * if location is bigger/smaller than length/0
+ * return false
+ * else return location */
+bool getElem(List * L, int i, int * e);
+
+/* insert element at given location
+ * if location is bigger than length, insert at last
+ * if location is 0 or negative, return false */
+bool insertElem(List * L, int i, int e);
+
+/* if location is bigger than length,
+ * or is smaller than 1,
+ * return false */
+bool deleteElem(List * L, int i, int * e);
+void printList (List * L);
+
+/* check if list exist and have no element */
+bool emptyList (List * L);
+void deleteList(List * L);
+
+#endif
diff --git a/c/dataStructure/408/list/lklist.c b/c/dataStructure/408/list/lklist.c
new file mode 100755
index 0000000..c2112b1
--- /dev/null
+++ b/c/dataStructure/408/list/lklist.c
@@ -0,0 +1,174 @@
+#include "list.h"
+
+/*      Fundamental      */
+void initList(List * L)
+{
+    L->lin = NULL;
+}
+
+int lengthList(List * L)
+{
+    linkList tmp = L->lin;
+    int i = 0;
+    while (tmp)
+    {
+        i++;
+        tmp = tmp->next;
+    }
+
+    return i;
+}
+
+bool locateElem(List * L, int * i, int e)
+{
+    linkList tmp = L->lin;
+    *i = 1;
+    while (tmp)
+    {
+        if (tmp->elem != e)
+        {
+            (*i)++;
+            tmp = tmp->next;
+        }
+        else
+            return true;
+    }
+    return false;
+}
+
+bool getElem(List * L, int i, int * e)
+{
+    linkList tmp = L->lin;
+
+    for (int j = 1; j < i; j++)
+        if(tmp->next)
+            tmp = tmp->next;
+        else
+        {
+            fprintf(stderr,"Location is out of range\n");
+            return false;
+        }
+    *e = tmp->elem;
+    return true;
+}
+
+bool insertElem(List * L, int i, int e)
+{
+    if (i <= 0)
+    {
+        fprintf(stderr,"Invalid location!\n");
+        return false;
+    }
+    linkList scan = L->lin;
+    linkList new = (Link *) malloc (sizeof(Link));
+
+    new->elem = e;
+    new->next = NULL;
+
+    if (!L->lin)
+    {
+        L->lin = new;
+        return true;
+    }
+    else
+    {
+        if (i == 1)
+        {
+            new->next = scan;
+            L->lin = new;
+        }
+        else
+        {
+            int j = 2;
+            while (j++ < i && scan->next)
+                scan = scan->next;
+            if (!scan->next && --j < i)
+                printf("Location is beyond the list length, Append element\n");
+            new->next = scan->next;
+            scan->next = new;
+        }
+    }
+    return true;
+}
+
+bool deleteElem(List * L, int i, int  * e)
+{
+    linkList tmp = L->lin;
+    if (i == 1)
+    {
+        *e = tmp->elem;
+        L->lin = L->lin->next;
+        free(tmp);
+        return true;
+    }
+    int j = 2;      // we need the one before the one needs delete
+    while (j++ < i && tmp->next)
+        tmp = tmp->next;
+    if (!tmp->next)
+    {
+        fprintf(stderr,"location out of range\n");
+        return false;
+    }
+
+    *e = tmp->next->elem;
+    if (tmp->next)
+    {
+        linkList t = tmp->next;
+        tmp->next = t->next;
+        free(t);
+    }
+    else
+        free(tmp);
+    return true;
+}
+
+void printList(List * L)
+{
+    linkList tmp = L->lin;
+
+    while (tmp)
+    {
+        printf("%d  ",tmp->elem);
+        tmp = tmp->next;
+    }
+    putchar('\n');
+}
+
+void deleteList(List * L)
+{
+    linkList tmp = L->lin;
+    linkList del;
+    while (tmp)
+    {
+        del = tmp->next;
+        free(tmp);
+        tmp = del;
+    }
+}
+
+/*      Homework      */
+void deleteX(linkList * L, int e)
+{
+    linkList tmp = *L;
+
+    if (!tmp->next)
+        return;
+    else
+    {
+        if (tmp->elem == e)
+        {
+            (*L) = (*L)->next;
+            free(tmp);
+            deleteX(&(*L)->next,e);
+        }
+        else if (tmp->next->elem == e)
+        {
+            linkList p = tmp->next;
+            tmp->next = p->next;
+            free(p);
+            deleteX(&tmp,e);
+        }
+        else
+            deleteX(&tmp->next,e);
+    }
+}
diff --git a/c/dataStructure/408/list/main.c b/c/dataStructure/408/list/main.c
new file mode 100755
index 0000000..34e4030
--- /dev/null
+++ b/c/dataStructure/408/list/main.c
@@ -0,0 +1,41 @@
+#include "list.h"
+
+int deleteMin(List * L);
+void reverse(List * L);
+//void deleteX(List * L, int e);
+void deleteX(linkList * L, int e);
+void loopLeftN(List * L, int n);
+int main(void)
+{
+    List U;
+    initList(&U);
+
+    for (int i = 1; i <= 10; i++)
+        insertElem(&U,i,i*2);
+    int p;
+    printList(&U);
+//    loopLeftN(&U,3);
+//    printList(&U);
+    getElem(&U,8,&p);
+    printf("%d\n",p);
+    locateElem(&U,&p,10);
+    printf("%d\n",p);
+    deleteElem(&U,3,&p);
+    printf("%d\n",p);
+    insertElem(&U,7,p);
+    insertElem(&U,7,p);
+    insertElem(&U,7,p);
+    insertElem(&U,7,p);
+    insertElem(&U,7,p);
+    printList(&U);
+    deleteX(&U.lin,p);
+    deleteX(&U.lin,2);
+    deleteX(&U.lin,20);
+    printList(&U);
+//    reverse(&U);
+//    printList(&U);
+
+    deleteList(&U);
+
+    return 0;
+}
diff --git a/c/dataStructure/408/list/sqlist.c b/c/dataStructure/408/list/sqlist.c
new file mode 100755
index 0000000..05893b4
--- /dev/null
+++ b/c/dataStructure/408/list/sqlist.c
@@ -0,0 +1,201 @@
+#include "list.h"
+
+/* Fundamental */
+void initList(List * L)
+{
+
+    // create new list
+    L->sql = (Seq *) calloc (1,sizeof(Seq));
+    if (!L->sql)
+    {
+        fprintf(stderr,"create list fail\n");
+        exit(EXIT_FAILURE);
+    }
+
+    sqList tmp = L->sql;
+    // allocate memory
+    tmp->data = (int *) calloc (MAX, sizeof(int));
+    if (!tmp->data)
+    {
+        fprintf(stderr,"allocate memory fail\n");
+        exit(EXIT_FAILURE);
+    }
+
+    tmp->length = 0;
+    tmp->maxSize = MAX;
+}
+
+int lengthList(List * L)
+{
+    return L->sql->length;
+}
+
+bool locateElem(List * L, int * i, int e)
+{
+    sqList tmp = L->sql;
+    for (int j = 0; j < tmp->length; j++)
+        if (tmp->data[j] == e)
+        {
+            *i = j + 1;
+            return true;
+        }
+    return false;
+}
+
+bool getElem(List * L, int i, int * e)
+{
+    sqList tmp = L->sql;
+    if (i < 1 || i > tmp->length)
+    {
+        fprintf(stderr,"Out of range\n");
+        return false;
+    }
+    *e = tmp->data[i-1];
+
+    return true;
+}
+
+bool insertElem(List * L, int i, int e)
+{
+    sqList tmp = L->sql;
+    if (i < 1 || i > tmp->length+1)
+    {
+        fprintf(stderr, "Out of range\n");
+        return false;
+    }
+    if (tmp->length == tmp->maxSize)
+    {
+        fprintf(stderr, "List full\n");
+        return false;
+    }
+    for (int j = tmp->length; j >= i; j--)
+        tmp->data[j] = tmp->data[j-1];
+    tmp->data[i-1] = e;
+    tmp->length++;
+
+    return true;
+}
+
+bool deleteElem(List * L, int i, int * e)
+{
+    sqList tmp = L->sql;
+    if (i < 1 || i > tmp->length)
+    {
+        fprintf(stderr,"Out of range\n");
+        return false;
+    }
+    *e = tmp->data[i-1];
+
+    for (int j = i; j < tmp->length; j++)
+        tmp->data[j-1] = tmp->data[j];
+    tmp->length--;
+    return true;
+}
+
+void printList(List * L)
+{
+    sqList tmp = L->sql;
+    for (int i = 0; i < tmp->length; i++)
+        printf("%d  ",tmp->data[i]);
+    putchar('\n');
+}
+
+bool emptyList(List * L)
+{
+    sqList tmp = L->sql;
+    if (tmp->length == 0)
+        return true;
+    return false;
+}
+
+void deleteList(List * L)
+{
+    free(L->sql->data);
+    free(L->sql);
+}
+
+/* homework */
+// 1
+int deleteMin(List * L)
+{
+    sqList tmp = L->sql;
+    
+    if (tmp->length == 0)
+    {
+        fprintf(stderr,"list is empty\n");
+        exit(1);
+    }
+    int min = tmp->data[0], index = 0;
+
+    for (int i = 1; i < tmp->length; i++)
+        if (min > tmp->data[i])
+        {
+            min = tmp->data[i];
+            index = i;
+        }
+    tmp->length--;
+    for (int i = index; i < tmp->length; i++)
+        tmp->data[i] = tmp->data[i+1];
+    return min;
+}
+
+// 2
+void reverse(List * L)
+{
+    sqList tmp = L->sql;
+    for (int i = 0; i < tmp->length/2; i++)
+    {
+        int t = tmp->data[i];
+        tmp->data[i] = tmp->data[tmp->length-1-i];
+        tmp->data[tmp->length-1-i] = t;
+    }
+}
+
+// 3
+void deleteX(List * L, int e)
+{
+    sqList tmp = L->sql;
+    int n = 0, index = -1, i;
+
+    for (i = 0; i < tmp->length; i++)
+    {
+        if (tmp->data[i] == e)
+            n++;
+        if (tmp->data[i] == e && index == -1)
+            index = i;      // get first element's index
+    }
+
+    for (i = index; i + n < tmp->length; i++)
+        tmp->data[i] = tmp->data[i+n];
+    tmp->length -= n;
+}
+
+// 10
+// helper
+void rev(sqList q, int low, int high)
+{
+    for (int i = low; i < (low+high)/2; i++)
+    {
+        int n = i - low;
+        int tmp = q->data[i];
+        q->data[i] = q->data[high-1-n];
+        q->data[high-1-n] = tmp;
+    }
+}
+
+// question answer
+void loopLeftN(List * L, int n){
+    sqList tmp = L->sql;
+    rev(tmp,0,n);
+    rev(tmp,n,tmp->length);
+    rev(tmp,0,tmp->length);
+}
+// extra
+void loopRightN(List * L, int n)
+{
+    sqList tmp = L->sql;
+    n = tmp->length - n;
+    rev(tmp,0,n);
+    rev(tmp,n,tmp->length);
+    rev(tmp,0,tmp->length);
+}
diff --git a/c/dataStructure/408/tree/Makefile b/c/dataStructure/408/tree/Makefile
new file mode 100755
index 0000000..85ea9c1
--- /dev/null
+++ b/c/dataStructure/408/tree/Makefile
@@ -0,0 +1,17 @@
+CC = gcc
+SRC = *.c
+FLGS = -Wall -Werror -g
+OPT = ./tree
+
+ALL: link run clean
+
+link:
+	@$(CC) $(SRC) $(FLGS) -o $(OPT)
+run:
+	$(OPT)
+
+gdb: link
+	gdb $(OPT)
+
+clean:
+	@rm $(OPT)
diff --git a/c/dataStructure/408/tree/main.c b/c/dataStructure/408/tree/main.c
new file mode 100755
index 0000000..c879362
--- /dev/null
+++ b/c/dataStructure/408/tree/main.c
@@ -0,0 +1,26 @@
+#include "tree.h"
+
+int main(void)
+{
+    Tree tree;
+
+    initTree(&tree);
+
+    printf("the size of tree now is %d\n",tree.size);
+
+    insertTree(&tree,3);
+    insertTree(&tree,4);
+    insertTree(&tree,2);
+    insertTree(&tree,1);
+
+    printTree(tree.root);
+    putchar('\n');
+
+    printf("the size of tree now is %d\n",tree.size);
+
+    freeTree(&tree);
+
+    printf("the size of tree now is %d\n",tree.size);
+
+    return 0;
+}
diff --git a/c/dataStructure/408/tree/tree b/c/dataStructure/408/tree/tree
new file mode 100755
index 0000000..1e50b63
--- /dev/null
+++ b/c/dataStructure/408/tree/tree
diff --git a/c/dataStructure/408/tree/tree.c b/c/dataStructure/408/tree/tree.c
new file mode 100755
index 0000000..26dc81e
--- /dev/null
+++ b/c/dataStructure/408/tree/tree.c
@@ -0,0 +1,83 @@
+#include "tree.h"
+
+void initTree(Tree * T)
+{
+    T->root = NULL;
+    T->size = 0;
+}
+
+// insertTree helper
+static Node * createNode(int e)
+{
+    Node * tmp = (Node *) malloc (sizeof(Node));
+    if (!tmp)
+    {
+        fprintf(stderr,"Node creation failed!\n");
+        exit(EXIT_FAILURE);
+    }
+
+    tmp->data = e;
+    tmp->lchild = NULL;
+    tmp->rchild = NULL;
+
+    return tmp;
+}
+
+static void insertNode(Node * root, Node * new)
+{
+    if (root->data > new->data)
+    {
+        if (!root->lchild)
+            root->lchild = new;
+        else
+            insertNode(root->lchild,new);
+    }
+    else if (root->data < new->data)
+    {
+        if (!root->rchild)
+            root->rchild = new;
+        else
+            insertNode(root->lchild,new);
+    }
+    else
+        fprintf(stderr,"Binary tree can't hold two identical element.\n");
+}
+
+bool insertTree(Tree * T, int e)
+{
+    Node * tmp = createNode(e);
+
+    if (T->size == 0)
+        T->root = tmp;
+    else
+        insertNode(T->root,tmp);
+    T->size++;
+
+    return true;
+}
+
+void printTree(Node * root)
+{
+    if (root->lchild)
+        printTree(root->lchild);
+    if (root->rchild)
+        printTree(root->rchild);
+    printf("%d  ",root->data);
+}
+
+// freeTree helper
+void freeNode(Node * root)
+{
+    Node * tmp = root;
+    if (tmp->lchild)
+        freeNode(tmp->lchild);
+    if (tmp->rchild)
+        freeNode(tmp->rchild);
+    free(tmp);
+}
+
+void freeTree(Tree * T)
+{
+    freeNode(T->root);
+    T->size = 0;
+}
diff --git a/c/dataStructure/408/tree/tree.h b/c/dataStructure/408/tree/tree.h
new file mode 100755
index 0000000..659d7ef
--- /dev/null
+++ b/c/dataStructure/408/tree/tree.h
@@ -0,0 +1,23 @@
+#ifndef _TREE_H
+#define _TREE_H
+
+#include<stdio.h>
+#include<stdlib.h>
+#include<stdbool.h>
+
+typedef struct node {
+    int data;
+    struct node * lchild, * rchild;
+} Node;
+
+typedef struct {
+    Node * root;
+    int size;
+} Tree;
+
+void initTree(Tree * T);
+bool insertTree(Tree * T, int e);
+void printTree(Node * root);
+void freeTree(Tree * T);
+
+#endif