Thực hiện cây nhị phân trong câu hỏi C như được tìm thấy trong K & R

Question

Vì vậy, tôi đã đọc qua cuốn sổ RC K & và có câu hỏi .. trong Chương 6 về cấu trúc trên trang 140-141, có mã giống như thế này (tôi lấy ra một số trong những phần không liên quan nhiều hơn)

/* 
the program loops through a tree looking for some word 
if it finds the word itll incremenet the count by 1 
if it doesnt itll add a new node 
*/ 

struct node { 
    char *word; 
    int count; 
    struct node *left; 
    struct node *right; 
} 

main() { 
    struct node *root; 
    char word[1000]; 

    root = NULL; 
    while(getword(word, MAXWORD) != EOF) /* getword just grabs 1 word at a time from a file of words */ 
     if(isalpha(word[0])) /* isalpha checks to see if it is a valid word */ 
      root = addNode(root, word); 

    treeprint(root); /* prints the tree */ 
    return 0; 
} 

struct node *addNode(struct node *p, char *w) { 
    int cond; 

    if(p == NULL) { 
     p = malloc(sizeof(struct node)); /* allocates memory for the new node */ 
     p -> word = strdup(w); 
     p -> count = 1; 
     p -> left = p -> right = NULL; 
    } 

    else if ((cond = strcmp(w, p -> word)) == 0) 
     p -> count++; 

    else if(cond < 0) 
     p -> left = addNode(p -> left, w); 

    else 
     p -> right = addNode(p -> right, w); 

    return p; 
} 

Và sự nhầm lẫn của tôi là trong hàm main() tại gốc = addNode (root, word)

Nếu addNode trả về một con trỏ đến mới được bổ sung nút (hoặc nút mà từ đó là tại nếu nó đã int cây của mình), sẽ không phải là "mất" tất cả các dữ liệu trên cây? Không nên ở gốc như gốc của cây?

Cảm ơn!

Answer 1

root luôn là gốc của cây. root được chuyển làm thông số đầu tiên của addNode chỉ có malloc nếu đó là NULL, tức là khi lần đầu tiên root được chuyển. Trong các cuộc gọi sau này, cuộc gọi sẽ không thay đổi root, sẽ chỉ sửa đổi count, left hoặc right. Lưu ý rằng trong các cuộc gọi addNode đệ quy, p không được chuyển, thay vào đó là con trái hoặc phải được chuyển. Cố gắng đi qua cây bằng giấy và bút chì/bút và bạn sẽ nhận ra các nút được thêm vào như thế nào.

Answer 2

Sự hiểu lầm của bạn có trong hành vi của addNode. Nó không không trả về một con trỏ tới nút mới được thêm vào; thay vào đó, nó trả về một con trỏ tới nút được truyền vào, p (trừ khi đó là NULL).

Vì thời gian duy nhất root == NULL là khi từ đầu tiên được thêm vào, root sẽ có cùng giá trị từ điểm đó và được gán giá trị rất giống này nhiều lần. Đây chỉ là một cách thanh lịch để đối phó với cây trống, được đại diện bởi con trỏ NULL.

Hãy nhớ rằng mỗi cuộc gọi đệ quy của addNode có giá trị khác nhau cho p. Đây là cách biến cục bộ hoạt động; họ là địa phương để một lời gọi cụ thể của hàm, không phải cho toàn bộ hàm. Có lẽ điều này dẫn đến sự hiểu lầm của bạn về hành vi của chức năng.