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ạ