Chỉ định độ sâu cho mỗi nút

Question

Tôi đã đọc một số bài viết khác ở đây trông tương tự, nhưng không hoàn toàn trả lời được sự cố của tôi. Tôi đã được đưa ra một câu hỏi cho một nhiệm vụ gán tất cả các nút trong một cây nhị phân độ sâu tương ứng của nó. Tôi không thể hiểu được.

Để tham khảo này là mã của tôi:

struct treeNode { 
    int item; 
    int depth; 
    treeNode *left; 
    treeNode *right; 
}; 
typedef treeNode *Tree; 

int assignDepth(Tree &T, int depth) 
{ 
    if(T!=NULL) 
    { 
     depth = assignDepth(T->left, depth++); 
     T->depth = depth; 
     depth = assignDepth(T->right, depth++); 
    } 
    else //leaf 
     return depth--; 
} 

Tôi đã cố gắng chạy nó thông qua với bút và giấy và nó trông OK, nhưng bàn của tôi kỹ năng kiểm tra đang thiếu rõ ràng.

Bất kỳ ai cũng có thể chỉ cho tôi đúng hướng không? Đây là lần đầu tiên tôi sử dụng cây, và đệ quy không phải là điểm mạnh của tôi.

Trả lời:

void treecoords(Tree &T, int depth) 
{ 
    static int count = -1; //set to -1 so the precrement before assignment doesn't give the wrong values 
    if(T!=NULL) 
    { 
     treecoords(T->left, depth+1); //depth decrements automatically once this function call is removed from the stack 
     count++; 
     T->x = count; 
      T->y = depth; 
     treecoords(T->right, depth+1); 
    } 
} 

Answer 1

Bạn don' t cần

else //leaf 
    return depth--; 

Bạn cũng không muốn để tăng biến sâu, chỉ cần vượt qua độ sâu + 1 với interation tới.

Cũng không cần trả lại giá trị.

Hãy thử điều này:

void assignDepth(Tree T, int depth) 
{ 
    if(T!=NULL) 
    { 
     assignDepth(T->left, depth+1); 
     T->depth = depth; 
     assignDepth(T->right, depth+1); 
    } 
} 

Answer 2

Vâng, đối với người mới bắt đầu, bạn đang sử dụng sau tăng/giảm, bạn có thể có nghĩa là ++depth/--depth cho việc chuyển nhượng quyền và nghĩa khác trở lại;

Ngoài ra, tại sao truyền con trỏ làm biến tham chiếu?

Answer 3

int assignDepth(Tree &T, int depth) 

Bạn đã xác định Tree như một con trỏ đến một treeNode. Bạn không cần phải vượt qua nó bằng cách tham khảo. Bạn có thể sửa đổi nút được trỏ đến.

{ 
    if(T!=NULL) 
    { 
     depth = assignDepth(T->left, depth++); 

Các postfix ++ đảm bảo rằng bạn đang đi qua gốc depth xuống. Đó không phải là những gì bạn muốn. Tăng thêm depth trước đó, và quên trả về nó như là một kết quả hàm.

T->depth = depth; 

Điều này là ổn.

 depth = assignDepth(T->right, depth++); 

Tương tự như cuộc gọi đệ quy trước đây, ngoại trừ việc bạn không nên sửa đổi depth vì tất cả đã được tăng lên.

} 
    else //leaf 
     return depth--; 

Bạn không cần phải trả lại bất kỳ thông tin chi tiết nào (hoặc đó là yêu cầu không được nêu ra?).

} 

Cheers & h.,

Answer 4

1. Khi bạn đã đạt đến một nút lá, bạn không quan tâm đến chiều sâu của nó nữa, vì vậy giá trị trả về xuất hiện để thực hiện gì cả.

2. Trong hai báo cáo:

   depth = assignDepth(T->left, depth++); 
   // and 
   depth = assignDepth(T->right, depth++); 
   

Bạn có hành vi không xác định từ điều chỉnh depth hai lần mà không có một điểm tự can thiệp (mặc dù nó có vẻ như không nên có, có không một điểm chuỗi giữa bên phải và bên trái của bài tập).

Answer 5

1. Tại sao bạn quay lại khi nút là NULL. Theo đặc điểm kỹ thuật của bạn, bạn không cần phải trả lại bất kỳ độ sâu nào

2. Trong trường hợp khác, bạn chỉ cần tăng độ sâu và gửi đến cuộc gọi hàm. Sau đây là phiên bản của tôi về mã

   trống assignDepth (Tree & T, int chiều sâu) { if (T == NULL) trở lại; else { T-> depth = depth; nếu (T-> left! = NULL) gánDepth (T-> left, depth + 1); nếu (T-> right! = NULL) gánDepth (T-> phải, depth + 1); }}

Answer 6

Tôi có một thiết kế hơi phức tạp hơn với thay đổi loại Node và đã làm điều này, vì vậy tôi nghĩ rằng id cổ phiếu.

Nếu bạn có cây thay đổi theo loại Nút thành Nút (Nhị phân, Unary, v.v.), bạn nên đơn giản hóa phương pháp truyền thống để tránh các IF được nhúng khó kiểm tra loại Nút.

Hai Chức năng:

• 1: Từ root, chạy qua từng nút và kiểm tra khoảng cách của nó đến gốc bởi recursivly tự xưng và thêm 1 cho mỗi phụ huynh. Đặt mỗi nút một biến sâu để lưu trữ điều này.
• 2: Từ bộ hoàn chỉnh các Nút trên cây chạy kiểm tra MAX đối với mỗi độ sâu nút, số cao nhất sẽ bằng độ sâu của cây.

Xử lý theo cách này loại bỏ kiểm tra loại rõ ràng và chỉ cần đếm nút cho dù nó có một, hai hoặc một trăm trẻ em.

Hy vọng điều này sẽ giúp ai đó!