**Complete this problem in the LANGUAGE SCHEME (R5RS)** 3. In lab this week, you
ID: 3603830 • Letter: #
Question
**Complete this problem in the LANGUAGE SCHEME (R5RS)**
3. In lab this week, you wrote some functions to work with binary trees. In this question, you will develop some code for binary search trees, as we have been doing in lecture. The representation of a binary search tree will be the same as the binary trees we used in lab, that is, a tree is a three-element list: the value of the node, the left subtree, and the right subtree, with empty trees represented as the empty list. Unlike the binary search trees we have been discussing in lecture, for the questions here we will assume all of the values are strings, so you will need to use the comparison functions string string>?, and string-? functions to build and search through your trees. Note: For all of the binary search tree problems in 3 and 4, you should work with the data in the tree (or trees), and not extract the data from the tree into a list and solve the problem on the list. While that strategy could work, you would lose the advantages of having the data in a binary search tree, and will not get credit for these even if the code passes the Mimir tests.Explanation / Answer
//Checks whether the given node is a leaf... (define (leaf? tree) (if (and (null? (left-branch tree) (null? right-branch tree))) #t #f ) )//Checks wheter the tree has only left branch (define (left-only? tree) (if (and (null? (right-branch tree)) (not (null? (left-branch tree)))) #t #f )) //Checks wheter the tree has only left branch (define (right-only? tree) (if (and (null? (left-branch tree)) (not (null? (right-branch tree)))) #t #f )) //When node, left branch and right branch of the tree are passed as arguements, // function will make and return the tree (define (make-tree node left-branch right-branch) (list node left-branch right-branch) ) //This function returns the node element of a given tree (define (node tree) (car tree)) //This function returns the left branch(subtree) of a given tree (define (left-branch tree) (cadr tree) ) //This function returns the right branch(subtree) of a given tree (define (right-branch tree) (caddr tree) ) //This function will insert an element into a tree and returns the new tree (define (insert e tree) (cond ((null? tree) (make-tree e '() '()));If the passed tree is null then a new tree of the form (e '() '()) //will be created ((= e (node tree)) tree) // If the node of the element is eqaual to the elemented to be inserted // Then there is no need for inserting and the previous tree will be returned. //If the element is greater than the node element, then the element shud be inserted ;somewhere in the right-branch ((> e (node tree)) (make-tree (node tree) (left-branch tree) (insert e (right-branch tree))) ) //If the element is greater than the node element, then the element shud be inserted ;somewhere in the left-branch ((tree2 with cdr of set and a new tree with root node (car set) as arguement (define (set->tree set) (if (null? set) '() (set->tree2 (cdr set) (make-tree (car set) '() '())) )) //functon will extract each element of set and insert it into the given tree (define (set->tree2 set tree) (if (null? set) tree (set->tree2 (cdr set) (insert (car set) tree)) )) //Searching an element in a binary search tree.. (define (search-tree e tree) (cond ((null? tree) #f) ; If the set is null result is boolean false ((= (node tree) e) #t) ; If the node of tree equals e, the result is true ((> e (node tree)) (search-tree e (right-branch tree))); if e is greater than node element, it shud be searched in right-branch ((tree set)) ) //Inserting tree1 into ertreme right of tree2(function used while deletion...).. (define (join-trees tree1 tree2) (if (null? tree2) tree1 (make-tree (node tree2) (left-branch tree2) (join-trees tree1 (right-branch tree2))) ) ) //Function to delete an element from a tree.. (define (delete e tree) (if (null? tree) '() //If the tree is not null then.... (cond ((= e (node tree)) (cond ((leaf? tree) '() ) ((left-only? tree) (left-branch tree) ) ((right-only? tree) (right-branch tree) ) (else (join-trees (right-branch tree) (left-branch-tree) ) ) ) ) ((> e (node tree)) (make-tree (node tree) (left-branch tree) (delete e (right-branch tree)) ) ) ((Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.