tailieunhanh - TOÁN RỜI RẠC - CÂY – PHẦN 4

Định nghĩa: Trong nhiều trường hợp, ta cần phải “điểm danh” hay “thăm” một cách có hệ thống mọi đỉnh của một cây nhị phân, mỗi đỉnh chỉ một lần. Ta gọi đó là việc duyệt cây nhị phân hay đọc cây nhị phân. Có nhiều thuật toán duyệt cây nhị phân, các thuật toán đó khác nhau chủ yếu ở thứ tự thăm các đỉnh. Cây nhị phân T có gốc r được ký hiệu là T(r). Giả sử r có con bên trái là u, con bên phải là v. Cây có gốc u và các đỉnh khác. | TOÁN RỜI RẠC - CÂY - PHẦN 4 DUYỆT CÂY NHỊ PHÂN . Định nghĩa Trong nhiều trường hợp ta cần phải điểm danh hay thăm một cách có hệ thống mọi đỉnh của một cây nhị phân mỗi đỉnh chỉ một lần. Ta gọi đó là việc duyệt cây nhị phân hay đọc cây nhị phân. Có nhiều thuật toán duyệt cây nhị phân các thuật toán đó khác nhau chủ yếu ở thứ tự thăm các đỉnh. Cây nhị phân T có gốc r được ký hiệu là T r . Giả sử r có con bên trái là u con bên phải là v. Cây có gốc u và các đỉnh khác là mọi dòng dõi của u trong T gọi là cây con bên trái của T ký hiệu T u . Tương tự ta có cây con bên phải T v của T. Một cây T r có thể không có cây con bên trái hay bên phải. Sau đây là ba trong các thuật toán duyệt cây nhị phân T r . Các thuật toán đều được trình bày đệ quy. Chú ý rằng khi cây T x chỉ là môt đỉnh x thì duyệt T x có nghĩa là thăm đỉnh x . Thí dụ 5 . Các thuật toán duyệt cây nhị phân 1 Thuật toán tiền thứ tự 1. Thăm gốc r. 2. Duyệt cây con bên trái của T r theo tiền thứ tự. 3. Duyệt cây con bên phải của T r theo tiền thứ tự. Duyệt cây nhị phân T a trong hình trên theo tiền thứ tự 1. Thăm a 2. Duyệt T b . Thăm b . Duyệt T d . Thăm d . Duyệt T g . Thăm g . Duyệt T l Thăm l . Duyệt T h Thăm h . Duyệt T e . Thăm e . Duyệt T i . Thăm i . Duyệt T m Thăm m . Duyệt T n Thăm n 3. Duyệt T c