Binary Search Tree Destructor

Question

Làm việc để triển khai BST của riêng tôi trong C++ cho trải nghiệm xử lý các cấu trúc như vậy.

Tôi gặp sự cố khi triển khai trình phá hủy. Tôi tìm thấy trong các nghiên cứu của tôi, người ta không thể có một destructor đệ quy (do một lá cờ không cho phép destructor được gọi trên cùng một đối tượng sau khi đã được gọi), nhưng tôi không thực sự chắc chắn của bất kỳ cách khác để làm sạch thành công tất cả các nút trong cây.

Để bù lại, tôi đã tạo một hàm trợ giúp - tuy nhiên điều này sẽ ném ra một lỗi ngoài chưa được giải quyết trên dòng 'xóa n'. Có lời khuyên nào không?

Code:

void BinSearchTree::Clear(tNode* n) 
{ 
    if (n->left != NULL) 
     Clear(n->left); 
    if (n->right != NULL) 
     Clear(n->right); 
    delete n; 
    n = NULL; 
    size--; 
} 

Answer 1

Bạn có thể có một destructor đệ quy; những gì bạn không thể làm là xóa cùng một đối tượng hai lần.

Một cách điển hình để xóa một cây trong C++ có thể là một cái gì đó như thế này:

BinSearchTree::~BinSearchTree() 
{ 
    delete _rootNode; // will recursively delete all nodes below it as well 
} 

tNode::~tNode() 
{ 
    delete left; 
    delete right; 
} 

Về lỗi bên ngoài chưa được giải quyết - đó là lỗi ném khi bạn cố gắng để biên dịch/liên kết chương trình? Nếu có, có thể là do mã cho lớp tNode (và đặc biệt là phá hủy tNode, nếu bạn khai báo một) không tồn tại hoặc không được biên dịch vào dự án của bạn.

Answer 2

Chỉ cần sử dụng một hàm hủy. Có vẻ như vấn đề của bạn là bạn đang cố gắng gọi trực tiếp cho destructors, nhưng ngôn ngữ xử lý điều này cho bạn. Chúng được gọi là khi bạn rời khỏi phạm vi của đối tượng được phân bổ ngăn xếp hoặc khi bạn xóa một đối tượng.

Tất cả các bạn nên cần là thế này:

~BinSearchTree() { 
    delete left; 
    delete right; 
} 

delete sẽ gọi hàm hủy của họ.

Lưu ý: Nó hoàn toàn an toàn để delete NULL, nó has no effect.

Answer 3

Vấn đề là trong lớp bạn có thể khai báo rằng cấu trúc nút có một destructor tùy chỉnh, nhưng bạn không cung cấp nó tại thời điểm liên kết trình biên dịch phàn nàn một phần bị thiếu.

Nếu bạn không cần thêm bất kỳ mã tùy chỉnh nào trong trình phá hủy, bạn có thể loại bỏ trình phá hủy khỏi khai báo cấu trúc và chương trình của bạn sẽ biên dịch tốt.

Tuy nhiên, lưu ý rằng không có vấn đề gì để hủy hoại các nút con hỏng (xem câu trả lời của Brendan Long). Nếu bạn gặp vấn đề trong khi cố gắng mà vấn đề bạn phải đối mặt phải tôi cái gì khác.

Answer 4

Làm thế nào về việc tự động hóa nó:

class BinSearchTree 
{ 
    std::auto_ptr<tNode> left; 
    std::auto_ptr<tNode> right; 

    BinSearchTree(BinSearchTree const&); 
    BinSearchTree& operator=(BinSearchTree const&); // private 
}; 

Bây giờ hủy diệt là tự động. :-)

Answer 5

Câu trả lời trước đã chỉ ra rằng lỗi bên ngoài chưa được giải quyết có thể do một trình phá hủy tNode được khai báo nhưng không được xác định trong đơn vị dịch mà trình liên kết có thể thấy.

Tuy nhiên, bạn gặp lỗi thứ hai: Bạn có vẻ tin rằng cài đặt n thành null thực hiện điều gì đó không thực hiện. Giá trị con trỏ n được chuyển bởi giá trị, không phải bằng tham chiếu, chẳng hạn như thay đổi giá trị của nó (ví dụ:bằng cách gán NULL) không có hiệu lực sau khi hàm trả về.

Điều này có thể sẽ cung cấp cho bạn các lỗi khi bạn xóa cây và mong muốn con trỏ nút gốc đã được đặt thành NULL, khi nó vẫn là một con trỏ lơ lửng để giải phóng bộ nhớ. Kết quả sẽ là lỗi thời gian chạy, không phải lỗi liên kết của bạn.

void BinSearchTree::Clear(tNode **N) 
{ 
    tNode * n = *N; 
    if (n->left != NULL) 
     Clear(n->left); 
    if (n->right != NULL) 
     Clear(n->right); 
    delete n; 
    *N = NULL; 
    size--; 
} 

Sẽ làm những gì bạn mong đợi.

Answer 6

Bạn cũng có thể sử dụng đệ quy, bạn chỉ cần thay đổi tiêu đề chức năng để:

void remove(node*& root) 

và nó sẽ làm việc.