Duyệt Cây Nhị Phân Theo Chiều Rộng _Lập Trình C++
Có thể bạn quan tâm
Skip to main content 
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ào đầu tiên sẽ xuất ra đầu tiên, vậy nên dùng hàng đợi trong trường hợp này là hợp lý. Nhưng vấn đề ở chỗ làm sao để đưa các nút vào hàng đợi đúng theo quy luật này, mình đưa ra giải pháp như sau: +) đầu tiên cho Nút gốc vào hàng đợi. +) xuất nó ra và đưa con của nó vào hàng đợi(tức là đưa 5 và 45 vào). +) Tiếp theo vì số 40 đã xuất rồi, coi như nó không còn trong hàng đợi nữa -->giải phóng nó bằng hàm dequeue(hàm dequeue là hàm xóa phần tử đầu trong hàng đợi). +)Hàng đợi bây giờ chỉ còn 5 và 45, trong đó 5 là phần tử đứng đầu hàng. tiếp tục làm như cũ, xuất ra 5 và thêm hai con của 5 vào, rồi deque 5, rồi xuất ra 45, tiếp tục đưa hai con của 45 vào, deque 45 +)đến đây, hàng đợi chỉ còn 35 56, tiếp tục thực hiện thao tác này cho đến khi không còn phần tử nào để đưa vào hàng đợi, và không còn phần tử nào trong hàng đợi nữa thì thôi. Có thể đến đây nhiều bạn đã hình dung cách làm, nhưng để hiện thực nó thành từng dòng code thì có vẽ vẫn đang còn khó, dưới đây là code mình đã code demo. lưu ý trong phần này mình tự tạo ra lớp queue để dùng(bạn nào học lập trình hướng đối tượng rồi thì chắc là biết), tuy nhiên bạn không cần quan tâm đến nó(quan tâm chi cho mệt, trong thư viện chuẩn có rồi nha), cái cần quân tâm ở đây là thuật toán xuất theo chiều rộng cơ. #include<iostream> using namespace std; //đây là phần cài đặt Node và queue template <class T> struct Node { T x; Node*Left; Node*Right; Node() { this->Left = this->Right = NULL; } }; template <class T> struct queue { Node<T>*Head; Node<T>*Tail; queue() { this->Head = NULL; this->Tail = NULL; } bool empty(); void enqueue(T x); void dequeue(); T top(); }; template <class T> bool queue<T>::empty() { if (!this->Head) return true; return false; } template <class T> void queue<T>::dequeue() { if (this->Head) { Node<T>*P = this->Head; this->Head = P->Left; if(this->Head)this->Head->Right = NULL; delete P; if (!this->Head) this->Tail = NULL; } } template <class T> void queue<T>::enqueue(T x) { if (!this->Head) { this->Head = new Node<T>; this->Head->x = x; this->Tail = this->Head; } else { Node<T>*P = new Node<T>; P->x = x; this->Tail->Left= P; P->Right = this->Tail; this->Tail = P; } } template <class T> T queue<T>::top() { if (this->Head) { return this->Head->x; } else { return 0; } } template <class T> struct Tree { Node<T>*Root; Tree() { this->Root = NULL; } }; template<class T> void add(Node<T>*&R, int &x) { if (!R) { Node<T>*P = new Node<T>; P->x = x; R = P; } else { if (R->x == x) return; else if (R->x > x) { add(R->Left, x); } else { add(R->Right, x); } } } //đây là cái hàm xuất theo chiều rộng template <class T> void breadthFirstShow(Node<T>*&R) { queue<Node<T>*> nodes; nodes.enqueue(R); Node<T>* Temp; while (!nodes.empty()) { Temp = nodes.top(); cout << Temp->x << " "; if (Temp->Left) nodes.enqueue(Temp->Left); if (Temp->Right) nodes.enqueue(Temp->Right); nodes.dequeue(); } } int main() { Tree<int> A; int x = 9; while (x) { cin >> x; if (x) { add(A.Root, x); } } breadthFirstShow(A.Root); return 0; } Rồi ok, nhưng vẫn còn cái để nói, giả sử có người yêu cầu xuất các node sao cho những node có cùng mức thì nằm trên từng hàng, thật ra thì cơ bản nó vẫn vậy, chỉ cẩn biến hóa thêm một chút là ra thôi. dưới đây mình code sẵn đây. #include<iostream> using namespace std; template <class T> struct Node { T x; Node*Left; Node*Right; Node() { this->Left = this->Right = NULL; } }; template <class T> struct queue { Node<T>*Head; Node<T>*Tail; queue() { this->Head = NULL; this->Tail = NULL; } bool empty(); void enqueue(T x); void dequeue(); T top(); }; template <class T> bool queue<T>::empty() { if (!this->Head) return true; return false; } template <class T> void queue<T>::dequeue() { if (this->Head) { Node<T>*P = this->Head; this->Head = P->Left; if(this->Head)this->Head->Right = NULL; delete P; if (!this->Head) this->Tail = NULL; } } template <class T> void queue<T>::enqueue(T x) { if (!this->Head) { this->Head = new Node<T>; this->Head->x = x; this->Tail = this->Head; } else { Node<T>*P = new Node<T>; P->x = x; this->Tail->Left= P; P->Right = this->Tail; this->Tail = P; } } template <class T> T queue<T>::top() { if (this->Head) { return this->Head->x; } else { return 0; } } template <class T> struct Tree { Node<T>*Root; Tree() { this->Root = NULL; } }; template<class T> void add(Node<T>*&R, int &x) { if (!R) { Node<T>*P = new Node<T>; P->x = x; R = P; } else { if (R->x == x) return; else if (R->x > x) { add(R->Left, x); } else { add(R->Right, x); } } } template <class T> void breadthFistShow(Node<T>*&R) { queue<Node<T>*> nodes; nodes.enqueue(R); Node<T>* Temp; int node_of_previous_level =1; int node_of_following_level = 0; while (!nodes.empty()) { Temp = nodes.top(); if (node_of_previous_level) { if (Temp->Left) { nodes.enqueue(Temp->Left); node_of_following_level++; } if (Temp->Right) { nodes.enqueue(Temp->Right); node_of_following_level++; } cout << Temp->x << " "; nodes.dequeue(); node_of_previous_level--; } else { cout << "\n"; node_of_previous_level = node_of_following_level; node_of_following_level = 0; } } } int main() { Tree<int> A; int x = 9; while (x) { cin >> x; if (x) { add(A.Root, x); } } breadthFistShow(A.Root); return 0; } Thân ái! Tạ Tạ 
**) Đối tượng hướng đến: các bạn đã và đang học cấu trúc dữ liệu và giải thuật, các bạn chưa học muốn tìm hiểu trước thì vui lòng tìm hiểu về stack, cây nhị phân,...để dễ dàng tiếp thu thêm kiến thức này **) Nội dung Cây Biểu thức là cây nhị phân trong đó các node lá là các toán hạng (a,b,c,..A,B,C,...) và các nút cha là các toán tử (+,-,*,/,...) thỏa mãn độ ưu tiên toán tử (nhân chia trước công trừ sau). Việc cài đặt một cây nhị phân tìm kiếm thì có vẻ đơn giản nhưng để cài đặt một cây biểu thức thì không phải dễ đâu nhé 😅😅😅😅😅😅😅😅😅😅😅, bản thân mình phải trải qua một thời gian khá dài (khoảng 2 tiếng, 😅😅😅😅😅😅😅😅😅😅😅 ) từ bạn bè mới cài được nó. Đùa tý thôi, thật ra cũng khá khó thôi, không đến nỗi. Rồi, Dưới đây là hình ảnh của cây biểu thức để cài đặt được một cái cây "ngắn ngắn " thế này cũng tốn khá nhiều thời gian đây, mình sẽ sơ lược các bước để cài đặt cây, code mẫu thì các bạn kéo xuống dưới để xem nhé!!! **) Các bước cài đặt Read more 
Tạ Quang Tú Working in Android programming, Computer vision, Deep learning Visit profile
Duyệt cây nhị phân theo chiều rộng _Lập trình C++
*) Đố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ào đầu tiên sẽ xuất ra đầu tiên, vậy nên dùng hàng đợi trong trường hợp này là hợp lý. Nhưng vấn đề ở chỗ làm sao để đưa các nút vào hàng đợi đúng theo quy luật này, mình đưa ra giải pháp như sau: +) đầu tiên cho Nút gốc vào hàng đợi. +) xuất nó ra và đưa con của nó vào hàng đợi(tức là đưa 5 và 45 vào). +) Tiếp theo vì số 40 đã xuất rồi, coi như nó không còn trong hàng đợi nữa -->giải phóng nó bằng hàm dequeue(hàm dequeue là hàm xóa phần tử đầu trong hàng đợi). +)Hàng đợi bây giờ chỉ còn 5 và 45, trong đó 5 là phần tử đứng đầu hàng. tiếp tục làm như cũ, xuất ra 5 và thêm hai con của 5 vào, rồi deque 5, rồi xuất ra 45, tiếp tục đưa hai con của 45 vào, deque 45 +)đến đây, hàng đợi chỉ còn 35 56, tiếp tục thực hiện thao tác này cho đến khi không còn phần tử nào để đưa vào hàng đợi, và không còn phần tử nào trong hàng đợi nữa thì thôi. Có thể đến đây nhiều bạn đã hình dung cách làm, nhưng để hiện thực nó thành từng dòng code thì có vẽ vẫn đang còn khó, dưới đây là code mình đã code demo. lưu ý trong phần này mình tự tạo ra lớp queue để dùng(bạn nào học lập trình hướng đối tượng rồi thì chắc là biết), tuy nhiên bạn không cần quan tâm đến nó(quan tâm chi cho mệt, trong thư viện chuẩn có rồi nha), cái cần quân tâm ở đây là thuật toán xuất theo chiều rộng cơ. #include<iostream> using namespace std; //đây là phần cài đặt Node và queue template <class T> struct Node { T x; Node*Left; Node*Right; Node() { this->Left = this->Right = NULL; } }; template <class T> struct queue { Node<T>*Head; Node<T>*Tail; queue() { this->Head = NULL; this->Tail = NULL; } bool empty(); void enqueue(T x); void dequeue(); T top(); }; template <class T> bool queue<T>::empty() { if (!this->Head) return true; return false; } template <class T> void queue<T>::dequeue() { if (this->Head) { Node<T>*P = this->Head; this->Head = P->Left; if(this->Head)this->Head->Right = NULL; delete P; if (!this->Head) this->Tail = NULL; } } template <class T> void queue<T>::enqueue(T x) { if (!this->Head) { this->Head = new Node<T>; this->Head->x = x; this->Tail = this->Head; } else { Node<T>*P = new Node<T>; P->x = x; this->Tail->Left= P; P->Right = this->Tail; this->Tail = P; } } template <class T> T queue<T>::top() { if (this->Head) { return this->Head->x; } else { return 0; } } template <class T> struct Tree { Node<T>*Root; Tree() { this->Root = NULL; } }; template<class T> void add(Node<T>*&R, int &x) { if (!R) { Node<T>*P = new Node<T>; P->x = x; R = P; } else { if (R->x == x) return; else if (R->x > x) { add(R->Left, x); } else { add(R->Right, x); } } } //đây là cái hàm xuất theo chiều rộng template <class T> void breadthFirstShow(Node<T>*&R) { queue<Node<T>*> nodes; nodes.enqueue(R); Node<T>* Temp; while (!nodes.empty()) { Temp = nodes.top(); cout << Temp->x << " "; if (Temp->Left) nodes.enqueue(Temp->Left); if (Temp->Right) nodes.enqueue(Temp->Right); nodes.dequeue(); } } int main() { Tree<int> A; int x = 9; while (x) { cin >> x; if (x) { add(A.Root, x); } } breadthFirstShow(A.Root); return 0; } Rồi ok, nhưng vẫn còn cái để nói, giả sử có người yêu cầu xuất các node sao cho những node có cùng mức thì nằm trên từng hàng, thật ra thì cơ bản nó vẫn vậy, chỉ cẩn biến hóa thêm một chút là ra thôi. dưới đây mình code sẵn đây. #include<iostream> using namespace std; template <class T> struct Node { T x; Node*Left; Node*Right; Node() { this->Left = this->Right = NULL; } }; template <class T> struct queue { Node<T>*Head; Node<T>*Tail; queue() { this->Head = NULL; this->Tail = NULL; } bool empty(); void enqueue(T x); void dequeue(); T top(); }; template <class T> bool queue<T>::empty() { if (!this->Head) return true; return false; } template <class T> void queue<T>::dequeue() { if (this->Head) { Node<T>*P = this->Head; this->Head = P->Left; if(this->Head)this->Head->Right = NULL; delete P; if (!this->Head) this->Tail = NULL; } } template <class T> void queue<T>::enqueue(T x) { if (!this->Head) { this->Head = new Node<T>; this->Head->x = x; this->Tail = this->Head; } else { Node<T>*P = new Node<T>; P->x = x; this->Tail->Left= P; P->Right = this->Tail; this->Tail = P; } } template <class T> T queue<T>::top() { if (this->Head) { return this->Head->x; } else { return 0; } } template <class T> struct Tree { Node<T>*Root; Tree() { this->Root = NULL; } }; template<class T> void add(Node<T>*&R, int &x) { if (!R) { Node<T>*P = new Node<T>; P->x = x; R = P; } else { if (R->x == x) return; else if (R->x > x) { add(R->Left, x); } else { add(R->Right, x); } } } template <class T> void breadthFistShow(Node<T>*&R) { queue<Node<T>*> nodes; nodes.enqueue(R); Node<T>* Temp; int node_of_previous_level =1; int node_of_following_level = 0; while (!nodes.empty()) { Temp = nodes.top(); if (node_of_previous_level) { if (Temp->Left) { nodes.enqueue(Temp->Left); node_of_following_level++; } if (Temp->Right) { nodes.enqueue(Temp->Right); node_of_following_level++; } cout << Temp->x << " "; nodes.dequeue(); node_of_previous_level--; } else { cout << "\n"; node_of_previous_level = node_of_following_level; node_of_following_level = 0; } } } int main() { Tree<int> A; int x = 9; while (x) { cin >> x; if (x) { add(A.Root, x); } } breadthFistShow(A.Root); return 0; } Thân ái! Tạ Tạ Comments
Post a CommentPopular posts from this blog
Duyệt cây không dùng đệ quy và stack _Lập trình C++ căn bản
* )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 Read moreCây Biểu thức_ Lập trình C++
**) Đối tượng hướng đến: các bạn đã và đang học cấu trúc dữ liệu và giải thuật, các bạn chưa học muốn tìm hiểu trước thì vui lòng tìm hiểu về stack, cây nhị phân,...để dễ dàng tiếp thu thêm kiến thức này **) Nội dung Cây Biểu thức là cây nhị phân trong đó các node lá là các toán hạng (a,b,c,..A,B,C,...) và các nút cha là các toán tử (+,-,*,/,...) thỏa mãn độ ưu tiên toán tử (nhân chia trước công trừ sau). Việc cài đặt một cây nhị phân tìm kiếm thì có vẻ đơn giản nhưng để cài đặt một cây biểu thức thì không phải dễ đâu nhé 😅😅😅😅😅😅😅😅😅😅😅, bản thân mình phải trải qua một thời gian khá dài (khoảng 2 tiếng, 😅😅😅😅😅😅😅😅😅😅😅 ) từ bạn bè mới cài được nó. Đùa tý thôi, thật ra cũng khá khó thôi, không đến nỗi. Rồi, Dưới đây là hình ảnh của cây biểu thức để cài đặt được một cái cây "ngắn ngắn " thế này cũng tốn khá nhiều thời gian đây, mình sẽ sơ lược các bước để cài đặt cây, code mẫu thì các bạn kéo xuống dưới để xem nhé!!! **) Các bước cài đặt Read more 
Tạ Quang Tú Working in Android programming, Computer vision, Deep learning Visit profile Archive
- 2018 1
- October 1
- 2017 14
- June 5
- Tổng hợp code cây nhị phân _Lập trình C++ căn bản
- Duyệt cây không dùng đệ quy và stack _Lập trình C+...
- Duyệt cây nhị phân theo chiều rộng _Lập trình C++
- Cây Biểu thức_ Lập trình C++
- Bài toán Upper Bound và Lower Bound trên cây nhị p...
- May 2
- April 6
- March 1
- June 5
Report Abuse
Từ khóa » Duyệt Lrn
-
Duyệt Cây Nhị Phân Tìm Kiếm - Freetuts
-
Duyệt Cây NLR LNR LRN - YouTube
-
[Cây Nhị Phân Tìm Kiếm] Bài 6. Duyệt LRN Cây Nhị Phân ... - YouTube
-
Phần 1 - Cây Nhị Phân Tìm Kiếm — Giải Thuật Lập Trình
-
Duyệt Cây Nhị Phân Tìm Kiếm Trong C/C++ - Lập Trình Từ Đầu
-
Cách Vẽ Lại Cây Nhị Phân Tìm Kiếm Từ Kết Quả Duyệt - Cùng Lập Trình
-
Cây Nhị Phân Trong C++ | TopDev
-
Các Thuật Toán Duyệt Cây Nhị Phân Cài đặt Thuật Toán Duyệt Qua Cây ...
-
Giới Thiệu Về Cấu Trúc Cây (tiếp Theo) | Facebook
-
Các Thao Tác Cơ Bản Trên Cây Nhị Phân (Binary Tree) - Góc Học IT
-
Cách Vẽ Lại Cây Nhị Phân Tìm Kiếm Từ Kết Quả Duyệt
-
[PDF] CẤU TRÚC DỮ LIỆU & GIẢI THUẬT 1 CÂY (TREE)
-
Vẽ Lại Cây Nhị Phân Tìm Kiếm Từ Kết Quả Duyệt - Viết Linh Tinh
-
Cây Nhị Phân - SlideShare