Greetings,
I have a Lisp problem which hopefully someone has seen (at least something
similar). The problem: given a tree represented by nexted lists, I need to
replace a subtree with an entirely new subtree. The difficulty arises because
I need to use a level-order (breath-first) traversal. For example, using a
simple equation, 2*(3+5)+9, parsed into a tree:
+
/ \
* 9
/ \ represented by '(+ (* 2 (+ 3 5)) 9)
2 +
/ \
3 5
Then, given, "replace node 4 with '(* 8 4)," yields:
+
/ \
* 9
/ \ 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; therefore, once the required node is found,
it is not the same physical node as in the original tree (list). Since it is
a different physical node, I can't insert the new subtree.
Any advice/solution would be greatly appreciated.
Thanx,
Mike Fulkerson
········@tiger.vill.edu
Dept of Computing Sciences
Villanova University