Esercitazione per struttura dei dati dell'albero in C

Question

Qualcuno potrebbe indirizzarmi ad un tutorial su Tree Data Structures usando C. Ho provato googling ma la maggior parte delle implementazioni sono per C++ o Java.Se qualcuno mi può indirizzare ad alcuni tutorial online che sono in C sarebbe bello.

Grazie ..

Answer 1

generici metodi albero-attraversamento: http://en.wikipedia.org/wiki/Tree_traversal (vedi barra laterale destra per una lista enorme di algoritmi tra cui scegliere).

Alcuni tutorial:

• http://randu.org/tutorials/c/ads.php
• http://www.ehow.com/how_2056293_create-binary-tree-c.html

Answer 2

Ecco un po 'di codice di tutorial da un paio di decenni fa. In effetti, è rimasto in giro così a lungo, non ricordo da dove venisse o chi lo ha scritto (avrei potuto essere io, ma non sono proprio sicuro). In teoria è un po 'non portatile, usando strdup, che non fa parte della libreria standard, sebbene la maggior parte dei compilatori lo abbia/fornisca.

/* 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; 
}