blue_ndt
18-11-2008, 17:17
Bạn nào có thể minh họa quá trình sử dụng Stack để duyệt cây nhị phân tìm kiếm theo NLR giúp mình không.Mình xem trên các diễn đàn thấy chủ yếu là đưa code ra chứ không có ví dụ về giải thuật.
Việc duyệt trước một cây nhị phân được tiến hành như sau: In ra key của nút gốc,sau đó chuyển sang con trái, in ra khóa của nút con trái,...Quá trình thực hiện cho tới khi con trái là rỗng.Lúc này chương trình chuyển sang con phải của nút cận dưới,và duyệt theo sơ đồ trên,cứ như thế việc duyệt cây con phải được tiến hành.
Nhận thấy rằng nút càng được thăm muộn thì con phải của nó càng được duyệt trước.Chính vì thế sau khi in ra nút,ta phải đưa địa chỉ của nó vào Stack,sau đó mới chuyển sang con trái,để sau này khôi phục lại duyệt con phải của nó.Quá trình đưa địa chỉ vào Stack kết thúc khi con trái là rỗng.Và lúc này ta bắt đầu lấy địa chỉ từ Stack ra thực hiện duyệt cây con phải tương ứng.Việc duyệt cây con phải cũng tương tự,nghĩa là cũng in ra key,rồi đưa địa chỉ nút vào Stack....
Như vậy quá trình đưa vào Stack và lấy ra khỏi Stack được thực hiện trong cùng một vòng lặp.Mà khi cả vòng lặp đó kết thúc thì cây được duyệt xong.
Cho cây nhị phân tìm kiếm: 44 88 18 59 108 55 71 37 10 15 40
Đưa 44 vào Stack,chuyển sang duyệt con trái.
Đưa 18 vào Stack,tiếp tục tới 10.
Sau đó ta tiến hành quá trình đưa con phải vào Stack,quá trình diễn ra như thế ta lần lượt đưa được vào Stack theo thứ tự sau:
44 18 10 15 37 40 88 59 55 71 108
Kết thúc tất cả ta mới thực hiện lấy ra khỏi Stack(vào sau ra trước)?
Liệu mình hiểu như thế có đúng không
Việc duyệt trước một cây nhị phân được tiến hành như sau: In ra key của nút gốc,sau đó chuyển sang con trái, in ra khóa của nút con trái,...Quá trình thực hiện cho tới khi con trái là rỗng.Lúc này chương trình chuyển sang con phải của nút cận dưới,và duyệt theo sơ đồ trên,cứ như thế việc duyệt cây con phải được tiến hành.
Nhận thấy rằng nút càng được thăm muộn thì con phải của nó càng được duyệt trước.Chính vì thế sau khi in ra nút,ta phải đưa địa chỉ của nó vào Stack,sau đó mới chuyển sang con trái,để sau này khôi phục lại duyệt con phải của nó.Quá trình đưa địa chỉ vào Stack kết thúc khi con trái là rỗng.Và lúc này ta bắt đầu lấy địa chỉ từ Stack ra thực hiện duyệt cây con phải tương ứng.Việc duyệt cây con phải cũng tương tự,nghĩa là cũng in ra key,rồi đưa địa chỉ nút vào Stack....
Như vậy quá trình đưa vào Stack và lấy ra khỏi Stack được thực hiện trong cùng một vòng lặp.Mà khi cả vòng lặp đó kết thúc thì cây được duyệt xong.
Cho cây nhị phân tìm kiếm: 44 88 18 59 108 55 71 37 10 15 40
Đưa 44 vào Stack,chuyển sang duyệt con trái.
Đưa 18 vào Stack,tiếp tục tới 10.
Sau đó ta tiến hành quá trình đưa con phải vào Stack,quá trình diễn ra như thế ta lần lượt đưa được vào Stack theo thứ tự sau:
44 18 10 15 37 40 88 59 55 71 108
Kết thúc tất cả ta mới thực hiện lấy ra khỏi Stack(vào sau ra trước)?
Liệu mình hiểu như thế có đúng không