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 ...

1. Trang chủ >
2. Công Nghệ Thông Tin >
3. Kỹ thuật lập trình >

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 nhị phân LNR

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.29 MB, 148 trang )

+ Duyệt qua theo thứ tự đầu NLR + Duyệt qua theo thứ tự cuối LRN.trong đó: L : quét cây con trái của một nútR : quét cây con phải của một nút N : xử lý nút.

IV.2.4.2. Các thuật toán duyệt cây nhị phân

Thuật toán duyệt qua theo thứ tự giữa LNR: Trái - Gốc - Phải : +Duyệt qua cây con trái theo thứ tự giữa;+Duyệt qua gốc; +Duyệt qua cây con phải theo thứ tự giữa.Thuật toán duyệt qua theo thứ tự đầu NLR: Gốc - Trái - Phải: +Duyệt qua gốc;+Duyệt qua cây con trái theo thứ tự đầu; +Duyệt qua cây con phải thứ tự đầu.Thuật toán NLR sẽ duyệt cây theo chiều sâu. Thuật toán duyệt qua theo thứ tự cuối LRN: Trái - Phải - Gốc:+Duyệt qua cây con trái theo thứ tự cuối; +Duyệt qua cây con phải theo thứ tự cuối;+Duyệt qua gốc.Ví dụ: Biểu diễn biểu thức: A - B C + D lên cây nhị phân: +- DAB CDuyệt cây theo các thứ tự khác nhau: LNR: A - B C + D biểu thức trung tốNLR: + - A B C D biểu thức tiền tố LRN: A B C - D + biểu thức hậu tốVới cách biểu diễn một biểu thức số học dưới dạng cây nhị phân, dựa trên cách duyệt LRN ta có thể tính giá trị của biểu thức đó Bài tập.Do định nghĩa đệ quy của cây nhị phân, các thuật toán duyệt qua cây theokiểu đệ quy là thích hợp.

IV.2.4.3. Cài đặt thuật toán duyệt qua cây nhị phân LNR

a. Cài đặt thuật toán LNR dưới dạng đệ qui : Input: - Root : con trỏ chỉ đến nút gốc của cây nhị phânOutput: - Duyệt qua và xử lý mọi nút của cây nhị phân theo thứ tự giữa LNR void LNRĐệQuy TreePointer Root{if Root = NULL { LNRĐệQuy Root-LChild;Xử lý Root;Xử lý theo yêu cầu cụ thể, chẳng hạn: XuấtRoot-Data;LNRĐệQuy Root-RChild ; }return; }Thuật toán duyệt cây nhị phân theo thứ tự giữa LNR có thể viết lại dưới dạng lặp, bằng cách sử dụng một stack để lưu lại địa chỉ các nút gốc trước khi điđến cây con trái của nó. Trước hết, ta khai báo cấu trúc một nút của stack trên:typedef struct NS { TreePointer Data;struct NS Next; } NodeStack;typedef NodeStack StackType; b. Cài đặt thuật toán LNR dưới dạng lặp :Input: - Root : con trỏ chỉ đến nút gốc của cây nhị phân Output: - Duyệt qua và xử lý mọi nút của cây nhị phân theo thứ tự giữa LNRvoid LNRLapTreePointer Root { TreePointer p;int TiepTuc = 1; StackType S;p = Root; S = CreateEmptyStack; Khởi tạo ngăn xếp rỗngdo { while p = NULL{ PushS,p; Đẩy p vào stack Sp = p-LChild; }if EmptyStackS Nếu stack S khác rỗng{ PopS,p; Lấy ra phần tử p ở đỉnh stack SXuLyp; p = p-RChild;}else TiepTuc = 0; } while TiepTuc;return ;} Với hai trường hợp duyệt cây còn lại NLR và LRN, ta cũng có thể cài đặtchúng dưới dạng đệ quy và lặp bài tập. Một cách tổng quát, ta có thể viết lại ba thuật toán duyệt này dưới một dạng lặp duy nhất bài tập.

IV.2.5. Một cách biểu diễn khác của cây nhị phân

Xem Thêm

Tài liệu liên quan

• Giáo trình cấu trúc dữ liệu và giải thuật
  • 148
  • 3,035
  • 19

Tải bản đầy đủ (.pdf) (148 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(1.29 MB) - Giáo trình cấu trúc dữ liệu và giải thuật-148 (trang) Tải bản đầy đủ ngay ×