Cấu trúc dữ liệu cấp bậc – Hierarchical Structures like Tree

Trình bày các sequence trong các điều khoản của list dẫn đến trình bày các sequence mà các thành phần của nó cũng là các sequence. Ví dụ, chúng ta có thể tạo object ((1 2) 3 4) bằng khởi tạo

(cons (list 1 2) (list 3 4))

giống như một list của 3 item, item đầu tiên là một list (1 2). Hình 2.5 trình bày cấu trúc các điều khoản của các pair.

Chúng ta cũng có thể hình dung các sequences mà các thành phần của nó là các sequence như các cây (tree). Các thành phần của sequence là các nhánh của cây, và các thành phần đó chính nó là các nhánh của cây trên nó. Hình 2.6 được biễu diễn dưới dạng tree.

Đệ quy( Recursion) là một thuật toán mạnh mẽ cho việc giải quyết cấu trúc tree, từ đó chúng ta có thể giảm các hoạt động toán tử trên tree đến các hoạt động tính toán trên các nhánh của nó, và cứ tiếp tục cho đến khi chúng ta tiếp cận đến các nhánh lá của tree. Ví dụ , So sánh procedure length trong bài trước và procedrue count-leaves, nó trả về tổng số lá của tree.

(define x (cons (list 1 2) (list 3 4)))
(length x)
3
(count-leaves x)
4
(list x x)
(((1 2) 3 4) ((1 2) 3 4))
(length (list x x))
2
(count-leaves (list x x))
8

Để thực thi count-leaves, gọi lại tiến trình đệ quy để tính length,

• length của một list x là 1 + với length cdr của x
• length của list trống là 0

Thực thi count-leaves tương tự. GIÁ trị của list trông là tương đương

count-leaves của một list trống là 0

Nhưng trong quá trình truy xuất đến các nhánh của cây, chúng ta sẽ xóa car của list, chúng ta phải chắc rằng car của list chính nó cũng là một tree, nên các lá của nó cũng cần đếm. Vì vậy, bước tiếp cận hiệu quả là:

count-leaves của một tree là count-leaves của car của một list x + với count-leaves của cdr của list x .

Cuối cùng, chúng ta sẽ lấy được các nút lá , vì thế chúng ta cần đếm là

• count-leaves của một leaf là 1

Để hỗ trợ trong việc viết procedure đệ quy trên tree, Schema cung cấp dự đoán nguyên thủy pair?, liệu rằng đối số có phải là pair. Procedure hoàn chỉnh như sau

(define (count-leaves x)
     (cond ((null? x) 0)
           ((not (pair? x)) 1)
           (else (+ (count-leaves (car x))
                    (count-leaves (cdr x))))))