Could someone direct me to some tutorial on Tree Data Structures using C. I tried googling but most implementations are for C++ or Java.If someone can point me to some online tutorials that are in C it would be great.
Thanks..
23 Answers
Generic tree-traversal methods: (see right sidebar for a huge list of algorithms to choose from).
Some tutorials:
2Here's a bit of tutorial code from a couple of decades ago. In fact, it's been lying around so long, I don't remember where it came from or who wrote it (could have been me, but I'm really not sure). Theoretically it's a bit non-portable, using strdup, which isn't part of the standard library, though most compilers have/supply it.
/* Warning: untested code with no error checking included. */ #include <stdio.h> #include <stdlib.h> #include <string.h> /* A tree node. Holds pointers to left and right sub-trees, and some data (a string). */ typedef struct node { struct node *left; struct node *right; char *string; } node; node *root; /* pointers automatically initialized to NULL */ int insert(const char *string, node *root) { /* Add a string to the tree. Keeps in order, ignores dupes. */ int num = strcmp(root->string, string); node *temp; for(;;) { if ( 0 == num) /* duplicate string - ignore it. */ return 1; else if (-1 == num) { /* create new node, insert as right sub-tree. */ if ( NULL == root -> right ) { temp = malloc(sizeof(node)); temp -> left = NULL; temp -> right = NULL; temp -> string = strdup(string); return 2; } else root = root -> right; } else if ( NULL == root ->left ) { /* create new node, insert as left sub-tree. */ temp = malloc(sizeof(node)); temp -> left = NULL; temp -> right = NULL; temp -> string = strdup(string); return 2; } else root = root -> left; } } void print(node *root) { /* in-order traversal -- first process left sub-tree. */ if ( root -> left != NULL ) print(root->left); /* then process current node. */ fputs(root->string, stdout); /* then process right sub-tree */ if ( root->right != NULL ) print(root->right); } int main() { char line[100]; /* Let user enter some data. Enter an EOF (e.g., ctrl-D or F6) when done. */ while ( fgets(line, 100, stdin)) insert(line, root); /* print out the data, in order */ print(root); return 0; } #include <stdio.h> #include <stdlib.h> struct binary_node { struct binary_node *left; struct binary_node *right; int value; }; typedef struct binary_node NODE; int search(NODE *temp, int data) { int found = 0; #if 0 while (temp == NULL) { if (temp->value == data) { found = 1; break; } else if (temp->value > data) temp = temp->left; else if (temp->value < data) temp = temp->right; } return found; #endif if (temp == NULL) return 0; else if (temp->value == value) return 1; else if (temp->value > data) return search(temp->left, data); else if (temp->value < data) } NODE *del(NODE *root, int val) { if (root = NULL) return ; if (val < root->val) root->left = delete(root->left, val); else if (val > root->val) root->right = delete(root->right, val); else { if (root->left == NULL && root->right == NULL) { temp = root; free(temp); root = NULL; } else if (root->left == NULL) { temp = root; root = root->right; free(temp); } else if (root->right == NULL) { temp = root; root = root->left; free(temp); } else { temp = min(root->right); root->data = temp->data; root->right = delete(root->right, temp->data); } } return root; } NODE *insert_node(NODE *node, int val) { if (*node == NULL) { node = (NODE *) malloc (sizeof(NODE)); node->left = NULL; node->right = NULL; node->value = val; } if (node->value > val) node->left = insert_node(node->left, val); else if (node->value < val) node->right = insert_node(node->right, val); else printf("Discarding the data as it already exists in node\n"); return node; } } int main() { NODE *root = NULL; root = insert_node(root, 50); insert_node(root, 4); insert_node(root, 14); insert_node(root, 44); insert_node(root, 24); insert_node(root, 34); insert_node(root, 74); insert_node(root, 54); insert_node(root, 64); print_order(&root); search(&root, 34); del(&root); return 0; } 
