3. Write preconditions and postconditions for the ADT binary search three operat
ID: 3670529 • Letter: 3
Question
3. Write preconditions and postconditions for the ADT binary search three operations (the methods declared in the interface template for the ADT binary tree
4. Consider a method isLeaf that returns true if a binary tree is a one-node tree— that is, if it consists of only a leaf—and returns false otherwise.
a. Specify the method isLeaf (write the specifications of the method isLeaf).
b. Is isLeaf were not a method of a class of binary trees, would a client of the class be able to implement isLeaf? Explain
5. Starting with an empty binary search tree, in what order should you insert items to get the binary search tree in Figure 1.
6. Using the binary tree in Figure 1, trace the search algorithm when it searches for a. 30 b. 15
7. Consider the binary search tree in Figure 1. What tree results after you inset the nodes 80, 65, 75, 45, 35, and 25, in that order?
8. Suppose that you traverse the binary search tree in Figure 1 and write the data item in each node visited to a file. You plan to read this file later and create a new binary search tree by using the ADT binary search tree operation add. In creating the file, in what order should you traverse the tree so that the new tree will have exactly the same shape and nodes as the original tree? 3. Write preconditions and postconditions for the ADT binary search three operations (the methods declared in the interface template for the ADT binary tree
Use the tree in Figure 1 for exercises 1, 2, 5, 6, 7, and 8 60 20 70 10 40 30 50 Figure 1Explanation / Answer
3). Binary Search Tree ADT
Attributes
size: The number of nodes in this BinarySearchTree.
root: The root of this BinarySearchTree; a null value not part of the tree when the tree is empty.
Pre-Post Conditions:
add ( Type element )
pre-condition: element is not null, is not already in the tree and is comparable to the other elements in the tree
responsibilities: add an element to the tree such that the BST properties are maintained
post-condition: size is incremented by 1
element is added to the tree
returns: nothing
exception: if element is null, is already in the tree or is not comparable to other elements in the tree
remove( Type element )
pre-condition: element is not null and is comparable to the other elements in the tree
responsibilities: remove element from the tree such that the BST properties are maintained. If the target is not in the tree, nothing happens and the tree is not changed
post-condition: size is decremented by 1, if element was in the tree element is removed from the tree
returns: nothing
contains( Type target )
pre-condition: target is not null
responsibilities: determine if target is stored in this tree
post-condition: the tree is unchanged
returns: true if target is found in this tree, false otherwise
exception: if target is null
4).
boolean isLeaf():
return fals if root is null
if root has both right and left child, return flase
else call isLeaf on available chile (left/right)
Yes, you can call even if isLeaf is not a part of BST ADT
boolean isLeaf(BSTNode root);
5).
60, 20, 10, 40, 30, 50, 70
6).
search(30):
1. compare with root 60 : less than root, go left side
2. compare with left child of 60, greater than 20, go right of 20
3. less than 40, go left
4. equal to 30, return true
search(15):
1. grater than 60, go left
2. less than 20, go left
3. greater than 10, go right
4. encounter with null, return false
7).
After insertion, pre-order traversal will be:
60 20 10 40 30 25 35 50 45 70 65 80 75
8).
to write tree data in file:
store In-Order traversal and one of other traversal(Pre/Post order traversal)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.