[SOLVED] data structure Scheme CSE1729 Introduction to Programming

CSE1729Introduction to Programming
October 28, 2019
Laboratory Assignment 7
Objectives
Workwithtrees
UseBinarySearchTrees
Activities Trees
1. Write a SCHEME function named treedepth which takes a tree node, n, as a parameter and returns the depth of the tree rooted at n . For the purpose of this exercise, the depth of a tree rooted at n is one plus the maximum of the depths of its two children. Recall the following code from the lecture slides:
define maketree value left right list value left right
define value T car T define right T caddr T define left T cadr T
define insert x T
cond null? T maketree x
eq? x value T T
x value T maketree
x value T maketree
value T
insert x left T right T
value T
left T
insert x right T
2. Define a SCHEME function named countpred P tree which given a binary tree and predicate func tion, P, applies the predicate to each of the values in the tree and returns the number of values for which the predicate returns t true.
3. Define a SCHEME function named countonechild which returns the number of internal nodes of a bi nary tree which have exactly one child.
Binary Search Trees
4. Define a SCHEME function named invertbst T which, given a Binary Search Tree BST inverts that BST. That is, the function returns a binary tree in which has the property that all values at nodes in the left subtree are greater than the value at the root node and all values at nodes in the right subtree are less than the value at the root node.
5. Write a SCHEME function, named numgteqz z T which, given a binary search tree T and an integer z , returns the number of integers in the tree that are greater than or equal to z . For example, given the tree
1

below and the number 5, your function should return 4, since there are 4 numbers in the tree that are greater than or equal to 5 specifically, 5, 8, 11, and 21.
Your solution should exploit the fact that the tree is a binary search tree to avoid considering certain subtrees.
8
4 11 15 21
Figure 1: A binary search tree with 6 nodes, 4 of which are 5 or larger.
6. OrganizationTreesBusinessesbuildorganizationalchartsshowingthemanagementstructureofthebusi ness. With some modifications to expand on our binary trees, we can store the same information in a tree structure and perform some computation on that data structure. There will be two modifications necessary. The data stored in each node will consist of two pieces of information, a name and the salary for the person represented by the node. These two pieces of information will be stored together in a pair. The second mod ification is necessary for managers to be able to manage more than two subordinates. Subordinates will be stored in a list of organization trees which are all subtrees of the node. See Figure 2 for an example in which the top manager has two direct reports. One direct report of Bob is Mary, who has only one direct report. The other is Steve who has three direct reports. See the convenience functions defined below as well as the SCHEME code for an example organization tree orgtree.
bob,1000000
mary,500000 steve,650000
frank;250000 sally;275000 nelly;350000 telly;375000
Figure 2: An organizational chart stored in a tree.
define makeorgtree name salary directreports list cons name salary directreports
define getname orgtree caar orgtree
define getsalary orgtree cdar orgtree
define getdirectreports orgtree cadr orgtree define org
makeorgchart bob
1000000
2

list makeorgchart
makeorgchart
mary
500000
list makeorgchart frank 250000 list steve
650000
list makeorgchart sally 275000 list
makeorgchart nelly 350000 list makeorgchart telly 375000 list
a Define a SCHEME procedure, named numdirectreports orgtree, which, given an organiza tional chart stored in a tree, returns the number of direct reports for the employee at the root of the tree.
b Define a SCHEME procedure, named deptsize orgtree, which, given an organizational chart stored in a tree, returns the number of employees in the department defined by the root of the given tree. Include the manager at the root of the tree plus the number of employees working under that manager sum of all the directreports, their direct reports and so on.
c DefineaSCHEMEprocedure,nameddeptbudget orgtree,which,givenanorganizationalchart stored in a tree, returns sum of all the salaries in the entire department defined by the root of the given tree. Include the salary of the manager at the root of the tree as well as employees working under the manager sum of all the salaries of the directreports, their direct reports and so on.
3