CSE 2011代写、代做R程序设计、R语言代写、代做IOT ree

日期：2019-09-19 09:31

York University

CSE 2011 – Assignment 2

Student #: CSE Email:

1) root (lines of code = 7) 11

2) parent (lines of code = 9) 11

3) leftChild (lines of code = 8) 11

4) rotateR (lines of code = 15) 12

5) first (lines of code = 4) 11

6) next (lines of code = 13) 11

7) set (lines of code = 11) 11

8) insert (lines of code = 5) 11

9) delete (lines of code = 8) 11

Total 100

Figure 1: A tree created by parsing the string “((1 2 3) 4 (null 5 (6 7 8)))”. You have to rotate your head

to see it. As the user walks around, the current node is indicated with < .. >.

1

1. You are write a set of methods for a new class called TreeWalker that extends my IOT ree class. As

such, a TreeWalker object consists of a binary tree that can be inputted and printed in a pretty way.

Your class will will have three additional system invariants.

(a) The tree is displayed on the screen as done in Figure 1.

(b) Exactly one of its nodes is marked as the current node. This acts as a cursor.

(c) The nodes of the tree will be order so that it is a binary search tree.

Each constructor for your class must ensure that it establishes each of these invariants. Each of your

methods must ensure that it maintains them, i.e. if these system invariants are true before it is executed

then they will be true after. Your code does not attempt to maintain it, but the user may wish to

maintain the additional system invariant that the tree is an AVL tree. Your class will provide the tools

for doing this.

I provide the class MainGUI which consists of an event processing loop. It waits for one of the following

commands from the user and then calls the appropriate method from your TreeWalker class. Note how

the system invariants for the class become the loop invariants for this loop.

Each of the methods here takes the current position as the input and returns the new current position.

They do not change the current flag in these nodes and do not reprint the tree. This is done in GUI

with the following lines of code.

tree.notCurrent(current);

current = tree.leftChild(current);

tree.makeCurrent(current);

write.setText(tree.PrettyPrint());

To help you, I have also given you the code for deleteNoRight. It contains may of the technques you

will need.

root,parent,leftChild,rightChild (·, ↑,ւ,ց): Moves the current node to its root, parent, left child,

or right child as the case may be.

Levels: When there is not such a root, parent, left child, or right child to move to:

(a) First simply have the current node not move. No error needs to be given.

(b) If you have more time, automatically create the node needed. For example, when at the

root, moving up creates a new root. The previous root will be the new root’s left child.

As another example, if the tree is the empty tree (created with “null”), then it is ok for

the methods parent, leftChild, and rightChild to crash, but the method root should create

a root node with the value 100.

(c) If you have managed to write it, use the method set to set its value.

rotateL, rotateR: Suppose the current node is that with value 10 in the left tree of Figure 2. Suppose

the user’s command is rotateL (clockwise). Your code should change the tree to that on the right

side of the figure with the current node being that with the value 5. If the user’s command is

then to rotateR (counter clockwise), then the tree changes back. The purpose of this is that the

[..5] subtree moves up one level while the [10..] subtree moves one down. Hopefully, this helps to

balance the tree.

first,last,next,previous (⇐,⇒,←,→): These commands moves the current node to the first, last,

next or previous node in the sorted order by value (assuming that the tree is a binary search tree).

This is the same as tree’s infix Traversal order. The first node is found by starting at the root of

the tree and going left as far as you can go. The next in this order is as follows. If your current

node has a right child, then go to this right child and then from there follow the path left left left

as far as you can go. If your current node does not have a right child, travel (up and left) as far

as you can and then (up and right). Said another way follow the path up parent parent parent.

Stop the first time that the node you came from is the left node of where you currently are.

Figure 2: rotateL(10) changes the left tree to right tree and rotateR(5) changes is back.

this up and left process goes past the root, then where you started already was the last node in

this order. In this case, automatically create the node needed with an appropriate binary search

value. Hint: use getLeft or getRight already written to create this node.

set: The current code is automatically given a new value that will help move the tree towards being a

binary search tree, i.e. to an integer value that is between its previous and next node’s value in

the infix traversal order. Hint: Use the already written methods next, previous, f irst, and last.

(This routine is not called in MainGUI.)

Insert After: A new node is created after the current node according to the tree’s infix Traversal

order, i.e. go right and then left left left and put the new node there. Shorter code uses the

routines that you have already written. If the current node does not have a right child then the

method rightChild already written will create this node. Otherwise, the method next takes you

right left left left. Then lef tChild will create the node.

Delete: Delete the current node. If the current node does not have a right child, then it’s parent

adopts its left child. If no left child, it’s parent adopts its right. The adopted child becomes the

current node (unless it is null then the parent does.) If the current node two children, then the

next node is right left left left. This node does not have a left child. Hence, it can be deleted by

having its parent adopt its right child. Before deleting next, its element contents is moved to the

current node. This remains the current node. To help you, I give you the code for deleteNoRight.

You write deleteNoLef t symmetrically. Then use these in delete.

Have Fun:

3