Thực hiện một trình lặp trên cây nhị phân (hoặc tùy ý) bằng cách sử dụng C++ 11

Question

Tôi muốn tạo một trình vòng lặp trên cây nhị phân để có thể sử dụng phạm vi dựa trên vòng lặp. Tôi hiểu rằng tôi nên thực hiện hàm start() và end() trước tiên.

Bắt đầu có lẽ nên trỏ đến thư mục gốc. Tuy nhiên, theo đặc tả, hàm end() trả về "phần tử theo phần tử hợp lệ cuối cùng". Yếu tố (nút) nào? Nó sẽ không được bất hợp pháp để trỏ đến một số "không hợp lệ" nơi?

Điều khác là toán tử ++. Cách tốt nhất để trả về phần tử "tiếp theo" trong cây là gì? Tôi chỉ cần một số lời khuyên để bắt đầu với chương trình này.

---

Tôi muốn mở rộng/tăng thêm câu hỏi của mình *. Điều gì sẽ xảy ra nếu tôi muốn lặp lại một cái cây với một vị thần tùy ý? Hãy để mỗi nút có một véc tơ của trẻ em và để bắt đầu() trỏ đến gốc "thực". Tôi có lẽ sẽ phải thực hiện một hàng đợi (cho bề rộng đầu tiên) bên trong lớp iterator để lưu trữ các unique_ptr của các nút, phải không? Sau đó, khi hàng đợi trống rỗng, tôi sẽ biết rằng tôi đã vượt qua tất cả các nút và do đó sẽ trả về TreeIterator (nullptr) khi oprator ++() được gọi. Nó có ý nghĩa không? Tôi muốn nó đơn giản nhất có thể và chỉ chuyển tiếp.

* Hoặc tôi có nên tạo một chuỗi mới không?

Answer 1

Trường hợp của bạn begin() nên trỏ đến khá nhiều phụ thuộc vào thứ tự mà bạn muốn đi qua cây của bạn. Sử dụng gốc có thể hợp lý, ví dụ, cho một chiều rộng đầu tiên đi bộ của cây. Các end() không thực sự ngồi trên một nút cây: vị trí này được truy cập và chỉ ra rằng kết thúc của chuỗi được đạt tới. Cho dù nó chỉ ra bất cứ điều gì liên quan đến cây phần nào phụ thuộc vào loại lặp mà bạn muốn hỗ trợ: khi chỉ hỗ trợ lặp đi lặp lại nó có thể chỉ ra kết thúc. Khi cũng hỗ trợ lặp đi lặp lại hai chiều, nó cần biết cách tìm nút ngay trước khi kết thúc.

Trong mọi trường hợp, địa điểm được trỏ đến không thực sự được truy cập và bạn cần một chỉ báo phù hợp. Đối với một iteration chuyển tiếp chỉ iterator end() chỉ có thể trả về một iterator trỏ đến null và khi bạn di chuyển từ nút cuối cùng bạn chỉ cần đặt con trỏ của iterator là null: equality so sánh hai con trỏ sẽ mang lại true, chỉ ra rằng bạn đã đạt đến kết thúc. Khi muốn hỗ trợ lặp đi lặp lại hai chiều, bạn sẽ cần một số loại bản ghi liên kết có thể được sử dụng để điều hướng đến nút trước đó nhưng không cần lưu trữ một giá trị.

Các bộ chứa liên quan được sắp xếp theo thứ tự (std::map<K, V>, std:set<V>, v.v.) được thực hiện nội bộ dưới dạng một số loại cây (ví dụ: Đỏ/Đen). Trình phát lặp begin() bắt đầu bằng nút ngoài cùng bên trái và trình biến lặp end() đề cập đến vị trí sau nút ngoài cùng bên phải.Các operator++() chỉ thấy nút bên cạnh phải của hiện tại:

• nếu iterator ngồi trên một nút không có nút con phải, nó đi dọc theo chuỗi của cha mẹ cho đến khi nó tìm thấy cha mẹ đạt con của nó qua nhánh trái của cây
• nếu nó nằm trên một nút có nút con bên phải, nó sẽ chuyển đến phần con và sau đó là chuỗi con trái của đứa trẻ này (nếu có) để tìm con ngoài cùng bên trái trong cây con bên phải .

Rõ ràng, nếu bạn không đi bộ cây từ trái sang phải mà đúng hơn, ví dụ: từ trên xuống dưới, bạn sẽ cần một thuật toán khác. Cách tiếp cận dễ nhất đối với tôi là vẽ một cây trên một mảnh giấy và xem cách đi đến nút tiếp theo.

Nếu bạn chưa triển khai cấu trúc dữ liệu bằng cách sử dụng trình vòng lặp của riêng mình, tôi khuyên bạn nên thử những thứ trên cấu trúc dữ liệu tuần tự đơn giản, ví dụ: danh sách: Rõ ràng cách tiếp cận nút tiếp theo và khi nào kết thúc đạt được. Một khi nguyên tắc lặp lại chung là rõ ràng, việc tạo ra một cây chỉ là vấn đề nhận được quyền điều hướng.

Answer 2

Một iterator cho một cây sẽ là nhiều hơn chỉ là một con trỏ, mặc dù nó có thể sẽ chứa một con trỏ:

struct TreeIterator { 
    TreeIterator(TreeNode *node_ptr) : node_ptr(node_ptr) { } 
    TreeIterator &operator++(); 
    TreeIterator operator++(int); 
    bool operator==(const TreeIterator &) const; 

    private: 
    TreeNode *node_ptr; 
}; 

TreeIterator begin(const Tree &tree) { ... } 
TreeIterator end(const Tree &tree) { ... } 

Bạn có thể làm cho bạn end() chức năng trả lại một cái gì đó đặc biệt, như TreeIterator(nullptr)

Điểm bắt đầu của bạn sẽ phụ thuộc vào loại truyền tải mà bạn muốn. Nếu bạn đang tiến hành lướt qua đầu tiên, thì bắt đầu từ gốc có ý nghĩa.

Answer 3

Xem SGI triển khai RBTree (đây là cơ sở cho std::set/std::map ... vùng chứa).

http://www.sgi.com/tech/stl/stl_tree.h

Bạn sẽ thấy rằng bắt đầu() là nút bên trái.

Bạn sẽ thấy rằng đầu() là nút "rỗng" đặc biệt tiêu đề là siêu gốc - nghĩa là gốc thực (chỉ được đặt trước nếu cây không trống) là nút con của nó.

operator ++ là chuyển đến đúng con và sau đó tìm nút con ngoài cùng bên trái này. Nếu đứa trẻ đó không tồn tại - chúng tôi đi đến cha mẹ bên trái của nút cha mẹ ngoài cùng bên phải. Như trong ví dụ này (đường màu đỏ là bỏ qua động thái, những màu xanh đầu là các bước nhất định lặp đi lặp lại):

Mã sao chép từ SGI:

void _M_increment() 
    { 
    if (_M_node->_M_right != 0) { 
     _M_node = _M_node->_M_right; 
     while (_M_node->_M_left != 0) 
     _M_node = _M_node->_M_left; 
    } 
    else { 
     _Base_ptr __y = _M_node->_M_parent; 
     while (_M_node == __y->_M_right) { 
     _M_node = __y; 
     __y = __y->_M_parent; 
     } 
     if (_M_node->_M_right != __y) 
     _M_node = __y; 
    } 
    } 

Khi một cây rỗng - begin() nằm ngoài cùng của tiêu đề - do đó, nó là tiêu đề chính - end() cũng là tiêu đề - vì vậy begin() == end(). Hãy nhớ - lược đồ lặp lại của bạn phải khớp với điều kiện này begin() == end() cho các cây trống.

Điều này có vẻ là lược đồ lặp lại rất thông minh.

Tất nhiên bạn có thể xác định sơ đồ của bạn - nhưng bài học kinh nghiệm là có nút đặc biệt cho mục đích end().