Duyệt Cây Không Dùng đệ Quy Và Stack _Lập Trình C++ Căn Bản

Có thể bạn quan tâm

Duyệt cây không dùng đệ quy và stack _Lập trình C++ căn bản

June 08, 2017 *)Giới thiệu: - Những thao tác trên cây thường rất đa dạng, mỗi loại thao tác lại có những phương thức và cách thao tác khác nhau. Thường thì người ta sẽ dùng đệ quy để tránh sự dài dòng, rắc rối. Chính vì đó, trong các tài liệu học tập trên trường học người ta ít đề cập đến việc thao tác với cây mà KHÔNG cần dùng đệ quy. Vậy hôm nay mình xin giới thiệu với các bạn cách duyệt cây nhị phân tìm kiếm theo kiểu InOrder(duyệt LNR) để minh họa. Các kiểu duyệt khác (PreOrder, PostOrder,...) các bạn tự điều chỉnh lại cho phù hợp.*) Đối tượng hướng đến: - Các bạn đang học lập trình C++, cấu trúc dữ liệu và giải thuật, có kiến thức vững chắc về con trỏ, cây nhị phân. *) Nội dung: từ trước đến nay, khi tạo một cây thì chúng ta luôn thấy các nút lá có 2 con trỏ left và right là NULL(đây là dấu hiệu để nhận biết nó là nút lá(nói hơi thừa 😁😁😁😁)), ta sẽ lợi dụng các nút trống này để kết nối với các Node "tổ tiên" của nó. Những tác vụ này khiến các Node trên cây sẽ liên kết với nhau một cách chặt chẽ,các nút lá cũng có "con", mà "con" ở đây lại là "tổ tiên" của chính nó, nghe thật là rắc rối phải không nào? Nhưng tất nhiên việc kết nối như thế nào thì phải cần có một thuật toán tương đối khó (với những người như chúng ta, chứ mấy ông thánh thì không nói rồi😁😁😁😁), Thông qua thuật toán kết nối đó cùng với vòng lặp while, một chút khéo léo sử dụng câu lệnh if, chúng ta có thể xuất ra các giá trị trên từng Node theo một thứ tự nào đó trên cây nhị phân(ở đây đang đề cập cây nhị phân tìm kiếm). Sau đây là một bài toán minh họa, thêm các phần tử vào cây, nhập số 0 để kết thúc quá trình nhập, sau đó duyệt kiểu InOrder mà không cần đệ quy, không cần stack, mời các bạn tham khảo code sau: #include <iostream> using namespace std; struct Node{ int val; Node *left, *right; }; void add_node(Node* &root, int x){ if (root == NULL){ root = new Node; root->val = x; root->left = root->right = NULL; } else { if (x < root->val) add_node(root->left, x); else if (x > root->val) add_node(root->right, x); } } /* Function to traverse binary tree without recursion and without stack */ void lnr(Node *root) { Node*pre; Node*current=root; while (current) { if (!current->left) { cout << current->val << "\n"; current = current->right; } else { pre = current->left; while (pre->right&&pre->right != current) { pre = pre->right; } if (!pre->right) { pre->right = current; current = current->left; } else { cout << current->val << "\n"; pre->right = NULL; current = current->right; } } } } int height(Node* t){ if (t){ int l = height(t->left), r = height(t->right); return (l < r ? r : l) + 1; } return 0; } int main() { Node* root = NULL; while (true){ int x; cin >> x; if (x == 0) break; add_node(root, x); } lnr(root); return 0; }

Comments

Bài toán Upper Bound và Lower Bound trên cây nhị phân tìm kiếm

June 01, 2017 Cây nhị phân tìm kiếm là một cấu trúc dữ liệu phổ biến được dùng để lưu trữ thông tin một cách có tổ chức, mọi thông tin trên cây đều tuân thủ quy luật nhất định, từ đó, việc quản lý và tìm kiếm dữ liệu được tối ưu hơn. Các thao tác trên cây thường rất đa dạng và đơn giản, nhưng không phải thao tác nào cũng đơn giản, ví dụ như thuật toán tìm Upper bound và Lower bound, nó đòi hỏi bạn phải biết cách dùng đệ quy khéo léo(à quên giới thiệu về Upper và lower bound, cứ hiểu đơn giản như sau, Cho một dãy số, tìm trong dãy các số lower bound của x (số lớn nhất mà nhỏ hơn x) và upper bound của x (số nhỏ nhất mà lớn hơn x) ), để làm được bài này thì có rất nhiều cách, chẳng hạn sử dụng mảng để lưu trữ có sắp xếp, sau đó duyệt tuyến tính hoặc dùng BinarySearch để tìm kiếm, hoặc dùng danh sách liên kết đơn, kép, vòng,..tùy các bạn. Nhưng có lẽ tốt hơn hết là dùng cây nhị phân tìm kiếm, việc thêm vào và tìm kiếm sẽ nhanh hơn nhiều. Giả sử bài toán được "biến tấu" ... Read more

Duyệt cây nhị phân theo chiều rộng _Lập trình C++

June 04, 2017

*) Đối tượng hướng đến: - Các bạn đang học cấu trúc dữ liệu và giải thuật, biết cách sử dụng con trỏ, biết về stack, queue - Các bạn khác đọc tham khảo *)Nội dung: Có rất nhiều cách duyệt cây nhị phân, mỗi cách phù hợp với từng nhu cầu riêng của lập trình viên. Thường thì chúng ta duyệt theo chiều sâu (tức là duyệt LNR, LRN, NLR,...). Nhưng ít đề cập đến việc duyệt cây theo chiều rộng. Vậy nên mình sẽ chia sẻ với các bạn một phần nhỏ về kiến thức duyệt cây theo chiều rộng. - Đầu tiên cần biết duyệt cây theo chiều rộng tức là sẽ xuất các giá trị trên cây theo thứ tự từ trái qua phải và từ trên xuống dưới, xét cây sau: nếu xuất theo chiều rộng thì thứ tự xuất sẽ là: 40 5 45 35 56 15 48 13 16 47 49 Để làm được điều này chúng ta cần sư dụng một hàng đợi (queue), hàng đợi này lần lượt sẽ chứa các nút theo thứ tự trên, tức là chứa 40-> 5-> 45-> 35-> 56-> 15-> 48-> 13 ->16-> 47-> 49. Mà theo quy luật của hàng đợi, thì phần tử và... Read more

Tạ Quang Tú Working in Android programming, Computer vision, Deep learning Visit profile

Report Abuse

Từ khóa » Duyệt Cây Bằng Stack

Duyệt Cây Không Dùng đệ Quy Và Stack _Lập Trình C++ Căn Bản