Cây gấp trong Vợt
Tôi là người mới bắt đầu chơi Vợt và tôi nhận được câu hỏi này:
- xác định cấu trúc,
node, trong đó có các lĩnh vực:value,left,middle,right. Cấu trúc này đại diện cho các nút trong cấu trúc cây.
Các trường này chứa giá trị được lưu trữ trong nút, cây con bên trái, cây con ở giữa và cây con bên phải tương ứng. Nếu một cây con không tồn tại, thì trường tương ứng phải chứa mộtemptyNodenhư được mô tả bên dưới.- xác định một cấu trúc,
emptyNodeđể chỉ định một nút trống trong cây.- Viết một hàm,
treeFoldnhận một hàmf, một giá trị ban đầuinitialvà một cấu trúc câytree, làm tham số. Sau đó nó sẽ tạo ra một giá trị duy nhất mà là kết quả của việc sử dụngfđể gấp các giá trị trong cây (sử dụngleft,middlevàrightsubtrees theo thứ tự đó). Lưu ý rằng đóflà một hàm có hai tham số. Tham số đầu tiên là một giá trị từ cây và tham số thứ hai là kết quả tích lũy một phần.
lệnh gọi hàm phải là:
(treeFold (lambda (a acc) (+ a acc)) 15 tree)
cây:
(node 7 (node 5 (emptyNode) (emptyNode) (emptyNode))
(node 20 (emptyNode) (emptyNode) (emptyNode))
(emptyNode))
đầu ra : 47
đây là những gì tôi đã làm cho đến nay:
(struct node (value left middle right) #:transparent)
(struct emptyNode () #:transparent)
(define tree
(node 7
(node 5 (emptyNode) (emptyNode) (emptyNode))
(node 20 (emptyNode) (emptyNode) (emptyNode))
(emptyNode)))
(define (treeFold f initial tree)
(if (emptyNode? tree)
(emptyNode)
(node (f initial (node-value tree))
(node-left tree)
(node-middle tree)
(node-right tree))))
Làm thế nào tôi có thể nhận được tổng số của toàn bộ lá?
bất kỳ ý tưởng hoặc sự giúp đỡ, cảm ơn
chỉnh sửa: vì vậy, dựa trên câu trả lời và thảo luận trong các nhận xét của nó, tôi đã nhận được một chức năng mới nhưng vẫn có một lỗi và tôi không thể tìm thấy nó. nó đây:
(define (treeFold f initial tree)
(cond
[(emptyNode? tree)
(f initial 0)]
[else (f (node-value tree)
(f (treeFold f
(treeFold f
(treeFold f initial
(node-left tree))
(node-middle tree))
(node-right tree))))]))
bạn có thể vui lòng cho tôi biết làm thế nào để sửa chữa nó? cảm ơn bạn.
chỉnh sửa: mã cuối cùng
(define (treeFold f initial tree)
(cond
[(emptyNode? tree) (f initial 0)]
[else (f (node-value tree)
(treeFold f
(treeFold f
(treeFold f initial
(node-left tree))
(node-middle tree))
(node-right tree)))]))
nó hoạt động như tôi mong đợi
Trả lời
cập nhật sau khi câu hỏi được chỉnh sửa với phiên bản mới của hàm.
Đây là một bước đi đúng hướng. Có một số mảnh đúng trong đó, và một số sai.
Các chức năng giống như các hộp có thể được kết nối với nhau. Nội dung đi vào một số dây và đi ra trên một số dây khác. Mỗi hộp có cách sử dụng thích hợp: số lượng dây và thứ mà nó mong đợi sẽ chảy vào trong chúng.
Phiên bản mới của bạn:
(define (treeFold f initial tree)
(cond
[(emptyNode? tree)
(f initial 0)]
[else (f (node-value tree) ;; (1)
(f (treeFold f ;; (2)
(treeFold f
(treeFold f initial
(node-left tree))
(node-middle tree))
(node-right tree))))]))
fmong đợi hai đối số. (f initial 0) có vẻ đúng, ít nhất về mặt đó. Cuộc gọi (1)cũng đến. Nhưng cuộc gọi đến ftại (2)chỉ có một đối số cung cấp cho f, do đó không thể là đúng.
Tiếp theo, đến ý nghĩa của nó. Ba cuộc gọi lồng nhau để treeFoldđược gần đúng: chúng tôi "đi" vào (node-left tree), tức là cây con bên trái, với initialnhư giá trị ban đầu, sau đó chúng tôi nhận được kết quả từ đó và sử dụng nó như là giá trị ban đầu mới đi vào tiểu giữa -tree và sử dụng kết quả được tính toán để chuyển qua cây con bên phải. Đẹp. Chúng tôi đã hoàn thành . Đó là kết quả cuối cùng mà chúng ta cần - không cần fbổ sung thêm nữa. Vì vậy, hai lệnh gọi đó lên ftrên ba lệnh gọi lồng nhau đến hoàn toàn treeFoldkhông cần thiết.
Ngoại trừ, chúng ta phải làm gì với (node-value tree)? Nó phù hợp ở đâu? Câu trả lời là, nó phải được kết hợp với initialgiá trị, theo cách gọi f, và kết quả của nó nên được sử dụng làm giá trị ban đầu mà chúng ta đi qua cây con bên trái ; giá trị mà chúng tôi bắt đầu gấp.
Trường hợp cơ sở cũng không chính xác. Chúng ta đã có initial, tại sao chúng ta lại cần kết hợp nó với nhau 0một cách đột ngột? Và tại sao 0? Ví dụ, chúng ta có thể gấp trên một cây giữ dây và việc kết hợp các dây với một số 0sẽ không có ý nghĩa gì.
Không, 0sẽ được cung cấp dưới dạng giá trị ban đầu trong lệnh gọi tới treeFold, như
(define (sumAllNumbersInWholeTree tree)
(treeFold + 0 tree))
Và với cây mang chuỗi, ví dụ, chúng ta có thể xác định
(define (collectAllStringsInWholeTree tree)
(treeFold string-append "" tree))
Phiên bản ban đầu của câu trả lời sau đây. Xem qua ví dụ (được chỉnh sửa rất nhẹ) của nó với sự hiểu biết mới của bạn. :)
Đối với
(define tree
(node 7
(node 5 (emptyNode) (emptyNode) (emptyNode))
(node 20 (emptyNode) (emptyNode) (emptyNode))
(emptyNode)))
nó phải là, theo thông số kỹ thuật,
47 == (treeFold + 15 tree)
== (treeFold + 15
(node 7
(node 5 (emptyNode) (emptyNode) (emptyNode))
(node 20 (emptyNode) (emptyNode) (emptyNode))
(emptyNode)))
== (treeFold +
(treeFold +
(treeFold + (+ 15 7) (node 5 (emptyNode) (emptyNode) (emptyNode)))
(node 20 (emptyNode) (emptyNode) (emptyNode)))
(emptyNode))
== (treeFold +
(treeFold +
(treeFold +
(treeFold +
(treeFold + (+ 22 5) (emptyNode))
(emptyNode))
(emptyNode))
(node 20 (emptyNode) (emptyNode) (emptyNode)))
(emptyNode))
== (treeFold +
(treeFold +
(treeFold +
(treeFold + 27 (emptyNode))
(emptyNode))
(node 20 (emptyNode) (emptyNode) (emptyNode)))
(emptyNode))
== (treeFold +
(treeFold +
(treeFold + 27 (emptyNode))
(node 20 (emptyNode) (emptyNode) (emptyNode)))
(emptyNode))
== (treeFold +
(treeFold + 27 (node 20 (emptyNode) (emptyNode) (emptyNode)))
(emptyNode))
.........
(viết ==cho "bằng"). Điều này đã cung cấp cho bạn mọi thứ bạn cần để có một định nghĩa hoàn chỉnh, cụ thể là
(treeFold + i (node v lt md rt))
==
(treeFold +
(treeFold +
(treeFold + (+ i v) lt)
md)
rt)
và
(treeFold + i (emptyNode))
==
i