Tutorial for Tree Data Structure in C
Could someone direct me to some tutorial on Tree Data Structures using C. I tried googling bu开发者_高级运维t 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..
Generic tree-traversal methods: http://en.wikipedia.org/wiki/Tree_traversal (see right sidebar for a huge list of algorithms to choose from).
Some tutorials:
- http://randu.org/tutorials/c/ads.php
- http://www.ehow.com/how_2056293_create-binary-tree-c.html
Here'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;
}
精彩评论