Xin hãy tử tế - đây là câu hỏi đầu tiên của tôi. =P

Về cơ bản đây là một dự án mùa hè mà tôi đang thực hiện trang wikipedia Danh sách cấu trúc dữ liệu trên. và cố gắng thực hiện chúng. Tôi đã học lớp C++ trong học kỳ trước và thấy nó rất thú vị, vì dự án cuối cùng của tôi là triển khai một đống nhị thức - điều này cũng rất thú vị. Có thể tôi là một người mọt sách nhưng tôi yêu thích cấu trúc dữ liệu.

Dù sao, đủ cốt truyện. Dự án diễn ra tốt đẹp và tôi bắt đầu với cây nhị phân. Để đi xa hơn, tôi cần tạo các vòng lặp để duyệt cây. Tôi đã quyết định tạo hai loại trình vòng lặp (các trình vòng lặp thông thường và const) cho mỗi phương thức truyền tải, tôi chỉ không biết làm thế nào. Tôi đã nghe nói về việc kế thừa từ các trình vòng lặp của STL và thậm chí sử dụng boost iterator_facade (có vẻ như là một lựa chọn tốt)

Tôi thậm chí còn chưa thử viết mã vòng lặp vì tôi không biết bắt đầu từ đâu, nhưng tôi đã đưa mã hiện tại của mình lên github. bạn có thể xem quađây .

Nếu bạn phản đối github, tôi sẽ dán định nghĩa lớp có liên quan. Việc triển khai các chức năng này không thực sự hữu ích, nhưng nếu bạn cần chúng vì lý do nào đó, vui lòng cho tôi biết. Ngoài ra, lớp nút có một con trỏ cha cho mục đích lặp lại.

#ifndef __TREES_HXX
#xác định __TREES_HXX
#include  // Đối với NULL
#include  // cho std::max

// Định nghĩa lớp nút. Các nút này được sử dụng cho mọi mục đích.
// cây chứa cấu trúc
// nút
// /\
// trái phải
// /\ /\
//
// v.v., về cơ bản là hai đứa trẻ.
mẫu 
nút lớp
{
  public:
    Dữ liệu T_;
    Nút* left_;
    Nút* phải_;
    Node* parent_; // Cần thiết cho các trình vòng lặp

    Nút rõ ràng(T const&);
    Nút(Nút const&);
};

mẫu 
lớp Cây nhị phân
{
  protected:
    typedef Node* node_t;
    size_t cây_size;

  public:
    typedef T value_type;

    rõ ràng BinaryTree();
    rõ ràng BinaryTree(T const&);
    ~Cây nhị phân();

    chèn node_t ảo(node_t&, T) = 0;
    tra cứu T& ảo(node_t const&, T const&) const = 0;
    nội tuyến ảo size_t size() const;
    độ sâu size_t ảo nội tuyến (node_t const&) const;
    bool nội tuyến trống() const;
    nội tuyến void clear(node_t);

    gốc nút_t;
};

Đây là phần mở rộng cây nhị phân cơ bản của lớp trừu tượng của chúng ta, về cơ bản nó (sẽ) là một BST. Để biết ví dụ về lý do tại sao tôi cần một trình vòng lặp, hãy xem định nghĩa của hàm find. Nó sẽ trả lại trình lặp về nút nơi tìm thấy nội dung.

/* Việc triển khai Cây nhị phân của chúng tôi đang được thực hiện
 * tệp này. Lớp nút nằm trong Trees.hxx
 * bởi vì nó được dự định là một lớp học chung.
 */

 #ifndef __BINARY_TREE_HXX
 #xác định __BINARY_TREE_HXX

 #include "Cây.hxx"


 mẫu 
 lớp BiTree : BinaryTree công khai
 {
   private:
     tên kiểu typedef BinaryTree::node_t node_t;

   public:
     tên kiểu typedef BinaryTree::value_type value_type;

     BiTree() : Cây nhị phân()
     {
     }

     BiTree(T const& data): BinaryTree(data)
     {
     }

     chèn node_t(node_t&, T);
     T& lookup(node_t const&, T const&) const; // Lưu ý: Điều này sẽ trả về một trình vòng lặp cho nút nơi tìm thấy nội dung
 };

Tôi nghĩ thế là xong - cảm ơn bạn đã dành thời gian! Hãy cho tôi biết nếu bạn cần thêm thông tin.

câu trả lời hay nhất

1. Vòng lặp béo so với vòng lặp nạc

Có hai cách có thể để thực hiện duyệt cây. Bạn có thể:

• Có những nút chỉ đơn giản trỏ đến "con" của chúng và các trình vòng lặp giữ ngăn xếp (vì vậy,vòng lặp chất béo)
• Các nút có các con trỏ cha (như của bạn) và các trình vòng lặp chỉ là các con trỏ tới một nút nhất định (Trình vòng lặp nhỏ gọn)

Đây là một sự đánh đổi trong thiết kế mà những người triển khai STL thường áp dụng một cách tinh gọn vì các trình vòng lặp (trong STL) được coi là rẻ để sao chép.

2. Trình lặp dễ dàng và Trình lặp từ đầu

Có một số cách khác để triển khai các trình vòng lặp:

• Bắt đầu lại từ đầu: bạn tự làm mọi thứ, bao gồm xác định typedef, nạp chồng tất cả toán tử, v.v...
• Đơn giản: bạn tự triển khai bằng Boost.Iterator với ít mã nhất có thể

Về cơ bản tôi đã kế thừa nó từstd::iteratorLà trường hợp "từ đầu" vì nó chỉ cung cấp 5 typedef ...

Việc bạn chọn cái này hay cái kia thực sự phụ thuộc vào tình huống của bạn:

• Vì mục đích học tập, tôi khuyên bạn nên áp dụng phương pháp "từ đầu" một vài lần
• Đối với mục đích sản xuất, tôi khuyên bạn nên sử dụng phương pháp "từ đầu" (kế thừa từ Boost không tiết kiệm nhiều, nhưng nó làm phức tạp các phiên gỡ lỗi/kết xuất bộ nhớ, ít nhất là đối với gdb, vì gdb hiển thị lớp cơ sở)
• Để kiểm tra nhanh, tôi khuyên dùng cách "dễ dàng"

Lưu ý rằng bạn có thể gặp phải một tình huống kỳ lạ khi trình vòng lặp của bạn thực sự không thể được xây dựng dựa trên Boost.Iterator, trong trường hợp đó bạn không có lựa chọn nào khác ngoài việc tự xây dựng nó.

3. Trình lặp const và không const

Đây có thể là điểm.

Nếu chỉ vì điều này thì đáng để xem xét Boost.Iterator khi chúng trình bày cách triển khaimộtKỹ thuật Iterator (khuôn mẫu), sẽ bao gồmHai loạiTình trạng. p>

Kiểm tra Bộ điều hợp vòng lặp TRONGVí dụ hướng dẫnphần:

mẫu 
lớp node_iter
  : tăng công khai::iterator_adaptor<
        node_iter // Xuất phát
      , Giá trị* // Cơ sở
      , boost::use_default // Giá trị
      , boost::forward_traversal_tag // CategoryOrTraversal
    >
{
 private:
    trình kích hoạt cấu trúc {}; // kiểu riêng tư tránh sử dụng sai

 public:
    nút_iter()
      : node_iter::iterator_adaptor_(0) {}

    node_iter rõ ràng(Value* p)
      : node_iter::iterator_adaptor_(p) {}

    /// !!! Điểm nổi bật !!!
    mẫu 
    nút_iter(
        node_iter const& other
      , tên kiểu boost::enable_if<
            boost::is_convertible
          , người kích hoạt
        >::type = kích hoạt()
    )
      : node_iter::iterator_adaptor_(other.base()) {}

 private:
    lớp bạn bè boost::iterator_core_access;
    void gia tăng() { this->base_reference() = this->base()->next() }
};

Hàm tạo thứ ba là lấy một cặpconstNhững điểm chính và không consttừ const Tự động chuyển đổi một trình vòng lặp thành một trình vòng lặp không constKhông thể chuyển đổi ngược lại.

Dù bạn làm gì, hãy sử dụng đi sử dụng lại cùng một kỹ thuật: tạo khuôn mẫu BaseIteratorhiện hữu Value và cung cấp hai định nghĩa kiểu:trình lặp typedef BaseIteratorVà typedef BaseIterator const_iterator .

Về C++, việc triển khai trình vòng lặp tùy chỉnh (dài) cho cây nhị phân, chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/6366684/