We can better organize the cases if we use a top-level function find to take care...

  

Transcribed Image Text:

We can better organize the cases if we use a top-level function "find" to take care of special cases, and let it call a helper function "find-node" for the non-special cases. The reason this is an improvement is because the "find-node" function can more easily be written in a recursive style. Option #1: (find-node n v stack) Create a new parameter named "stack" that "find" will pass to "find-node" the helper function. This will be a list of nodes from root to insertion point. Initial value of "stack" is (list (bst-root t)), a list containing just the root of the tree. In the helper function, when the base cases are reached, "(cons in stack)" is the final value. For other cases, call "stack-node" function recursively with n replaced by left of n or right of n and "stack" replaced by (cons n stack). (define (find tv) (cond ((empty? (bst-root t)) null) (else (find-node (bst-root t) v null)) top-level function ; special case tree is empty general case let find-node do the work ; initial value of stack is null (define (find-node n v stack) (cond » Option #2: (find-node n v) Don't use extra parameter "stack". ; helper function ;cases go here In the base case for "find-node", the result is (list n). In the recursive case, result is the append of recursive call with (list n). Be sure to put recursive call on the left and (list n) on the right, because we want the root at the tail of the list and the insertion point at the head. (define (find tv) (cond ((empty? (bst-root t)) null) (else (find-node (bst-root t) v)) }) (define (find-node nv) (cond ; top-level function ;special case tree is empty ; general case let find-node do the work ;no parameter "stack" in option #2 ; helper function ; cases go here Convert list of nodes to list of values: (nl-to-vi x) When printing out results, it will be convenient to convert a list of nodes into a list of values. When nodes are displayed by the interpreter, each node is displayed along with any nested nodes that are connected to it, which is correct but hard to read on the screen. If we just want to check that the nodes are in the correct order, it's convenient to display a list of values of the nodes in the list, rather than the actual list of nodes. This function is merely for formatting convenience to print information out and display it. (define (nl-to-vlx) (cond " If x only contains one node Else ; base case, recursive case Take the value of the node and create a list of one item Take the value of the head node, cons it to the result of the recursive call to (cdr x) Traverse: (traverset) This function implements the recursive definition of BST in-order traversal described earlier. Its result is a list of nodes with the node values in ascending order. We will use the same trick we used for (find tv) and divide it into a top-level function and a recursive helper function. (define (traverset) ; top-level function (traverse-node (bst-root t));"traverse" calls "traverse-node" to do all the work (define (traverse-node n) (cond :recursive helper function base case, recursive case The top-level function "(traverse t)" will simply call the helper function "(traverse-node (bst-root t))" passing the root node as its parameter. In this way, the helper function can be simplified and written as a recursive function using only a node reference, without having to handle special cases involving the root of the BST structure. For reference, here is the recursive definition of traverse that we will use for the traverse-node function. If n is empty Else Return the empty list Return the append of (1) traverse on left of n, (2) list of n, and (3) traverse of right of n We can better organize the cases if we use a top-level function "find" to take care of special cases, and let it call a helper function "find-node" for the non-special cases. The reason this is an improvement is because the "find-node" function can more easily be written in a recursive style. Option #1: (find-node n v stack) Create a new parameter named "stack" that "find" will pass to "find-node" the helper function. This will be a list of nodes from root to insertion point. Initial value of "stack" is (list (bst-root t)), a list containing just the root of the tree. In the helper function, when the base cases are reached, "(cons in stack)" is the final value. For other cases, call "stack-node" function recursively with n replaced by left of n or right of n and "stack" replaced by (cons n stack). (define (find tv) (cond ((empty? (bst-root t)) null) (else (find-node (bst-root t) v null)) top-level function ; special case tree is empty general case let find-node do the work ; initial value of stack is null (define (find-node n v stack) (cond » Option #2: (find-node n v) Don't use extra parameter "stack". ; helper function ;cases go here In the base case for "find-node", the result is (list n). In the recursive case, result is the append of recursive call with (list n). Be sure to put recursive call on the left and (list n) on the right, because we want the root at the tail of the list and the insertion point at the head. (define (find tv) (cond ((empty? (bst-root t)) null) (else (find-node (bst-root t) v)) }) (define (find-node nv) (cond ; top-level function ;special case tree is empty ; general case let find-node do the work ;no parameter "stack" in option #2 ; helper function ; cases go here Convert list of nodes to list of values: (nl-to-vi x) When printing out results, it will be convenient to convert a list of nodes into a list of values. When nodes are displayed by the interpreter, each node is displayed along with any nested nodes that are connected to it, which is correct but hard to read on the screen. If we just want to check that the nodes are in the correct order, it's convenient to display a list of values of the nodes in the list, rather than the actual list of nodes. This function is merely for formatting convenience to print information out and display it. (define (nl-to-vlx) (cond " If x only contains one node Else ; base case, recursive case Take the value of the node and create a list of one item Take the value of the head node, cons it to the result of the recursive call to (cdr x) Traverse: (traverset) This function implements the recursive definition of BST in-order traversal described earlier. Its result is a list of nodes with the node values in ascending order. We will use the same trick we used for (find tv) and divide it into a top-level function and a recursive helper function. (define (traverset) ; top-level function (traverse-node (bst-root t));"traverse" calls "traverse-node" to do all the work (define (traverse-node n) (cond :recursive helper function base case, recursive case The top-level function "(traverse t)" will simply call the helper function "(traverse-node (bst-root t))" passing the root node as its parameter. In this way, the helper function can be simplified and written as a recursive function using only a node reference, without having to handle special cases involving the root of the BST structure. For reference, here is the recursive definition of traverse that we will use for the traverse-node function. If n is empty Else Return the empty list Return the append of (1) traverse on left of n, (2) list of n, and (3) traverse of right of n