Cây N-ary trong C

Question

Đó sẽ là một cách thực hiện gọn gàng của một cây N-ary trong ngôn ngữ C?

Particulary, tôi muốn thực hiện một cây n-ary, không tự ballancing, với một số ràng buộc trẻ em trong mỗi nút, trong đó mỗi nút có bằng struct đã được xác định, như thế này ví dụ:

struct task { 
    char command[MAX_LENGTH]; 
    int required_time; 
}; 

Answer 1

là một đường chuyền đầu tiên, bạn chỉ đơn giản là có thể tạo ra một struct (chúng ta hãy gọi nó TreeNode) nắm giữ một nhiệm vụ , cũng như một loạt các con trỏ để TreeNode s. Tập hợp này có thể là một mảng (nếu N là cố định) hoặc danh sách được liên kết (nếu N là biến). Danh sách liên kết sẽ yêu cầu bạn khai báo thêm struct (chúng ta hãy gọi nó là ListNode) với một TreeNode con trỏ tới các con thực tế (một phần của cây), và một con trỏ đến ListNode tiếp theo trong danh sách (null nếu ở cuối danh sách).

Nó có thể giống như thế này:

struct task { 
    char command[MAX_LENGTH]; 
    int required_time; 
}; 

struct TreeNode; 

struct ListNode { 
    struct TreeNode * child; 
    struct ListNode * next; 
}; 

struct TreeNode { 
    struct task myTask; 
    struct ListNode myChildList; 
}; 

Answer 2

Bất kỳ cây n-phân có thể được biểu diễn như một cây nhị phân mà trong mỗi nút con trỏ trỏ trái cho đứa trẻ đầu tiên và điểm con trỏ quyền tiếp theo em trai.

 
      R      R 
     /| \      | 
      B C D      B -- C -- D 
     /\ |      |   | 
     E F G      E -- F G 

Vì vậy, trường hợp của bạn sẽ là:

struct task { 
    char command[MAX_LENGTH]; 
    int required_time; 
}; 

struct node { 
    struct task taskinfo; 
    struct node *firstchild; 
    struct node *nextsibling; 
}; 

Kỹ thuật này có ưu điểm là nhiều thuật toán là đơn giản để viết vì chúng có thể được thể hiện trên một cây nhị phân chứ không phải trên một cấu trúc dữ liệu phức tạp hơn .