Lớp C++ STL std :: map thực hiện tra cứu O (log (n)) bằng cách sử dụng cây nhị phân. Nhưng với cây cối, nó không phải là ngay lập tức rõ ràng như thế nào một iterator sẽ làm việc. Toán tử ++ thực sự có ý nghĩa gì trong cấu trúc cây? Trong khi khái niệm "phần tử tiếp theo" có triển khai rõ ràng trong một mảng, đối với tôi, nó không quá rõ ràng trong một cái cây. Làm thế nào sẽ thực hiện một iterator cây?Làm thế nào để std :: bản đồ iterator làm việc?
Để truyền tải theo thứ tự (có thể hoạt động cho những người khác), nếu bạn có một nút cha-mẹ trong các nút của mình, bạn có thể thực hiện truyền tải không đệ quy. Bạn có thể lưu trữ hai con trỏ trong trình vòng lặp của mình: bạn cần một dấu hiệu cho thấy bạn đang ở đâu, và có thể bạn sẽ không cần đến một con trỏ "trước" để bạn có thể tìm ra hướng di chuyển hiện tại của bạn (tức là tôi cần phải đi vào cây con trái, hoặc tôi vừa trở về từ nó).
"Trước" sẽ có thể là là giống như "cha mẹ", nếu chúng tôi vừa nhập nút; "còn lại" nếu chúng ta quay lại từ cây con trái, "đúng" nếu chúng ta quay lại từ cây con phải, và "tự" nếu nút cuối cùng chúng ta quay trở lại là của chính chúng ta.
Việc triển khai có thể biết rằng con trỏ nút được căn chỉnh từ và lạm dụng các bit dưới của con trỏ nút để lưu trữ trạng thái, thay vì sử dụng con trỏ thứ hai. – MSalters
Tôi nghĩ rằng đây là những gì tôi cần. Về cơ bản tôi đang cố gắng tạo ra một iterator cho một lớp cây chung chung và điều này dường như làm việc cho các cây không có thứ tự n-ary. – Avi
Xem xét tập hợp tất cả các phần tử trong bản đồ không nhỏ hơn phần tử hiện tại cũng không phải là phần tử hiện tại. "Yếu tố tiếp theo" là phần tử từ tập hợp các phần tử đó nhỏ hơn tất cả các phần tử khác trong tập hợp đó.
Để sử dụng bản đồ, bạn phải có khóa. Và chìa khóa đó phải thực hiện thao tác "nhỏ hơn". Điều này xác định cách bản đồ được hình thành, sao cho các hoạt động tìm, thêm, xóa, tăng và giảm hiệu quả.
Thường thì bản đồ nội bộ sử dụng một loại cây nào đó.
Bạn có thể xem nguồn dưới dạng bộ khởi động: http://www.sgi.com/tech/stl/stl_map.h – amit
Nhìn vào [cây tìm kiếm nhị phân tự cân bằng] điển hình (http: // en.wikipedia.org/wiki/Red%E2%80%93black_tree). Thật dễ dàng để xem một thuật toán nhận được từ một nút nhất định đến nút lớn hơn tiếp theo bằng cách tìm đến đúng trẻ em hoặc đi lên và xuống cây. Thỉnh thoảng bạn phải nhảy nhiều lần, nhưng nó vẫn là thời gian không đổi được phân bổ (vì chiều cao của cây là logarit của số phần tử). –
Bài viết wikipedia này có thể trả lời một số câu hỏi của bạn: [Tree traversal] (http://en.wikipedia.org/wiki/Tree_traversal). Về cơ bản, phần tử "tiếp theo" có thể khác nhau tùy thuộc vào loại truyền tải bạn sử dụng. Trong trường hợp 'std :: map', cây được di chuyển theo thứ tự (từ phần tử nhỏ nhất đến lớn nhất). –