Hướng dẫn cấu trúc dữ liệu cây trong C

Question

Ai đó có thể hướng dẫn tôi đến một số hướng dẫn về Cấu trúc dữ liệu cây bằng C. Tôi đã thử googling nhưng hầu hết các triển khai đều dành cho C++ hoặc Java.Nếu ai đó có thể chỉ cho tôi một số hướng dẫn trực tuyến có trong C sẽ rất tuyệt.

Cảm ơn ..

Answer 1

Generic phương pháp cây traversal: http://en.wikipedia.org/wiki/Tree_traversal (xem bên phù hợp với một danh sách lớn của các thuật toán để lựa chọn).

Một số hướng dẫn:

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

Answer 2

Dưới đây là một chút mã hướng dẫn từ một vài thập kỷ trước đây. Trong thực tế, nó đã được nằm xung quanh quá lâu, tôi không nhớ nó đến từ đâu hoặc những người đã viết nó (có thể đã được tôi, nhưng tôi thực sự không chắc chắn). Về mặt lý thuyết nó là một chút không di động, sử dụng strdup, mà không phải là một phần của thư viện chuẩn, mặc dù hầu hết các trình biên dịch có/cung cấp nó.

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