แก้ไข #2: คำถามและการสำรวจทั้งหมดนี้ขึ้นอยู่กับความคิดพื้นฐานของซิปที่ขาดหายไป เป็นตัวแทนเปอร์สเปคทีฟในโครงสร้างข้อมูลจากมุมมองของโหนดใดโหนดหนึ่ง ดังนั้นซิปจึงเป็นคู่ของโหนดปัจจุบันและส่วนที่เหลือของแผนผังจากมุมมองของโหนดนั้นตลอดเวลา เดิมทีฉันพยายามสร้างโครงสร้างใหม่ทั้งหมดจากซิป ในขณะที่ซิปคือสิ่งเดียวที่ฉันต้องการมาตลอด ฉันจะทิ้งเรื่องราวทั้งหมดนี้ไว้ให้ลูกหลาน ด้วยความหวังว่าคนอื่นจะได้รับความช่วยเหลือ (หรือเพื่อเป็นการเตือนผู้สืบทอดคนต่อไป!)
คำถามเดิม:
ฉันกำลังพยายามใช้ซิปจัดการต้นไม้ ปัญหาเฉพาะคือฉันต้องสร้างเส้นทางรันไทม์ระหว่างสองโหนดที่ตรงกับเกณฑ์ที่กำหนดเองในแผนผังที่กำหนดเอง
ฉันคิดว่าฉันสามารถใช้ฟังก์ชัน path
เพื่อรับเส้นทางไปยังตำแหน่งหนึ่งได้โดยการโทร path
บนตำแหน่งปัจจุบัน แต่เส้นทางที่ส่งคืนดูเหมือนจะละเว้นขั้นตอนสุดท้ายที่จำเป็นในการไปถึงที่นั่น
ตัวอย่างเช่น:
(def test-zip (vector-zip [0 [1] [2 [3 [4] 5 [6 [7] [8]]]]]))
(-> test-zip
down right right down
right down right right
node)
ให้ 5
แต่
(-> test-zip
down right right down
right down right right
path)
ให้
[[0 [1] [2 [3 [4] 5 [6 [7] [8]]]]] [2 [3 [4] 5 [6 [7] [8]]]] [3 [4] 5 [6 [7] [8]]]]
ซึ่งไม่ใช่ตำแหน่งเดียวกัน (ไม่มีเอฟเฟกต์ของสามขั้นตอนสุดท้าย down right right
)
ดูเหมือนว่าฟังก์ชัน path จะพาคุณไปยังตำแหน่งหลักในแผนผังเท่านั้น โดยไม่สนใจพี่น้องระหว่างคุณกับตำแหน่งจริง
ฉันพลาดจุดสำคัญของฟังก์ชัน path
หรือไม่ ฉันคิดว่าเมื่อใช้ต้นไม้และเส้นทาง การใช้เส้นทางกับต้นไม้จะนำคุณไปยังตำแหน่งเดิมของเส้นทาง ไม่ใช่เพียงบางส่วนเท่านั้น
อัปเดต: ฉันใช้คำจำกัดความฟังก์ชันต่อไปนี้เพื่อรวบรวมเส้นทางของโหนดจากตำแหน่งเริ่มต้นไปยังตำแหน่งสิ้นสุด:
(defn lca-path [start-loc end-loc]
(let [sczip (z/root start-loc)
start-path (z/path start-loc)
start-node (z/node start-loc)
end-path (z/path end-loc)
end-node (z/node end-loc)
lca-path (filter (set start-path) end-path)
lca-node [(last lca-path)]
lca-to-start (conj (vec (drop (count lca-path) start-path)) start-node)
lca-to-end (conj (vec (drop (count lca-path) end-path)) end-node)
]
(concat (reverse lca-to-start) lca-node lca-to-end))
)
ได้รับอิทธิพลอย่างมากจากการแชทกับ @Mark Fisher ขอบคุณ!