Here's my problem: Given a tree represented by nexted lists, I need to
replace a subtree with an entirely new subtree. For example, using
a simple equation, 2*(3+5)+9, parsed into a tree:
+
/ \
* 9
/ \ is represented by '(+ (* 2 (+ 3 5)) 9)
2 + (in real life, my trees are much deeper)
/ \
3 5
The problem is to insert a new subtree (replacing the old) given a node
number using a level-order (breath first) traversal. Continuing with the
example: given, "replace node 4 with '(* 8 4)," yields:
+
/ \
* 9
/ \ is now represented by '(+ (* 2 (* 8 4)) 9)
2 *
/ \
8 4
Using a depth-first search, this is easily accomplished through recursion and
using a setf. However, using breath-first requires a queue which internally
duplicates the original structure, and therefore requires another method which
continues to elude me. Please Email me, or repost a solution.
Thanx,
Mike Fulkerson
Dept of Computing Sciences
Villanova University