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

Thuật toán HeapSort trong lập trình C++
*)Đối tượng hướng đến:
+)các bạn mới học lập trình
+)các bạn muốn ôn lại kiến thức về thuật toán
*)Nội dung:

-)Sắp xếp vun đống (Heapsort) dựa trên một cấu trúc dữ liệu được gọi là đống nhị phân (binary heap), gọi đơn giản là đống. Trong mục này chỉ nói về đống trong bài toán sắp xếp.
HeapSort được ứng dụng nhiều cho việc sắp xếp(trên mảng, trên list đơn,list kép,..), nhưng để làm quen với nó nên mình chỉ trình bày trên mảng và thực hiện sắp xếp tăng dần.
Nghe có vẻ phức tạp thế thôi nhưng bắt tay vào code luôn cũng không khó mấy :))
Không dài dòng nữa bắt đầu thôi.

Đầu tiên ta phải biết được cái "đống" này là một mảng có quy luật như sau:
Array[i]>=Array[j] và Array[i]>=Array[j+1], trong đó j=2*i+1.
vậy việc đầu tiên của chúng ta là phải sắp xếp "sơ sơ" sao cho mảng thỏa mãn yêu cầu trên, để làm được điều này, mình cần dùng đến hai hàm, hàm thứ nhất là hàm shift(có nghĩa là sự thay đổi), hàm thứ hai là hàm createHeap(Tạo đống) phần định nghĩa của hai hàm đó như sau:

void shift(int *&A, int left, int right)
{
int i = left;
int j = 2 * i + 1;
while(j <= right)
{
if ((j < right) && (A[j] < A[j + 1])) j++;
if (A[i] < A[j])
{
swap(A[i], A[j]);
i = j;
      j = i * 2 + 1;
}
else
{
return;
}
}

}

void createHeap(int *A, int n)
{
int i = n / 2 - 1;
while (i >= 0)
{
shift(A, i, n - 1);
i--;
}

}
//đây là hàm mình chưa nói đến nhưng cứ để đây cho dễ nói :)
void HeapSort(int *A, int n)
{
createHeap(A, n);
int r = n - 1;
while (r)
{
swap(A[0], A[r]);
r--;
if (r>0)
shift(A, 0, r);
}
}
-)Giải thích: Phần giải thích này mình phải xin lỗi trước vì mình không có khiếu sư phạm, giải thích hơi củ chuối, mấy bạn chịu khó nghe nhá:
+)đầu tiên là hàm shift, hàm này được dùng để sắp xếp "sơ sơ" từ left qua right sao cho những phần tử ở các vị trí i,2*i+1,2*i+2 thỏa mãn điều kiện mình có nói phần trên, tất nhiên ở giữa những vị trí đó còn có nhiều phần tử và chúng chưa được sắp xếp để thỏa mãn điều kiện trên(giải thích hơi chuối, mấy bạn bỏ quá), vậy câu hỏi đặt ra ở đây là, làm sao để mọi phần tử đều thỏa mãn điều kiện đó, câu trả lời là dùng hàm createHeap, nó đã được viết ở trên, đoạn này mình rất khó để giải thích, các bạn nên đọc lại code của mình và tham khảo thêm những tài liệu về Heap để dễ hình đung thuật toán này. Rồi, sau khi createHeap xong rồi, các bạn sẽ được mảng có số lớn nhất nằm ở đầu mảng, vậy làm sao đưa nó về cuối mảng? câu trả lời là swap nó với phần tử cuối cùng, tức là đổi vị trí cho phần tử cuối cùng, thế là chúng ta có số to nhất nằm cuối mảng(chúng ta đang sắp xếp tăng dần), sau đó giảm r xuống, tức là chỉ thực hiện việc tạo lại Heap bằng hàm shift, lí do vì sao thì các bạn nên tham khảo nhiều thêm về heap, mình chỉ giải thích đến đây thôi. Sau đó cứ lặp đi lặp lại việc tạo heap và hoán vị cho đến khi nào r=1, tức là chỉ còn hai phần tử cần xét.
 Các bạn nên tự cho những đoạn mảng ngắn chưa được sắp xếp, và thử "chạy bằng tay" hoặc Debug( Debug cho dễ :v), hai ba lần làm như vậy thì các bạn sẽ hiểu vì sao phải code như vậy.
Chúc các bạn thành công!