CS代写 CSE 12

程序代写 CS代考

27 February 2019 OSU CSE 1

• The Tree component family allows you to manipulate values modeled as
mathematical trees with any label type T (i.e., tree of T)

Copyright By PowCoder代写 加微信 powcoder

27 February 2019 OSU CSE 2

Interfaces and Classes
Standard Iterable extends extends
TreeKernel
implements
27 February 2019

Interfaces and Classes
Standard Iterable extends extends
TreeKernel
implements
TreeKernel has
contracts for four
newSequenceOfTree
disassemble
27 February 2019

Tree has contracts
Interfaces and Classes
for six methods:
replaceRoot
addSubtree
removeSubtree
numberOfSubtrees
implements
extends extends TreeKernel
27 February 2019

Mathematical Model
type TreeKernel is modeled by tree of T
27 February 2019 OSU CSE 6

No-argument Constructor • Ensures:
this = empty_tree
27 February 2019 OSU CSE 7

Tree tn = new Tree1<>();
27 February 2019 OSU CSE 8

Tree tn = new Tree1<>();
27 February 2019 OSU CSE 9

newSequenceOfTree Sequence> newSequenceOfTree()
• Creates and returns an empty Sequence> of the dynamic type needed in assemble and disassemble.
• Ensures:
newSequenceOfTree = < >
27 February 2019 OSU CSE

newSequenceOfTree
Sequence> newSequenceOfTree()
• Creates and returns an empty
has the right type.
Sequence> of the dynamic type needed in assemble and disassemble.
• Ensures:
newSequenceOfTree = < >
27 February 2019 OSU CSE
The mathematical model of Sequence> is
string of tree of T, so this value (the empty string)

Sequence> st = tn.newSequenceOfTree();
27 February 2019 OSU CSE 12

Sequence> st = tn.newSequenceOfTree();
27 February 2019 OSU CSE 13

Note that the value of the
receiver does not only its type.
Sequence> st = tn.newSequenceOfTree();
27 February 2019 OSU CSE 14

void assemble(T root, Sequence> children)
• Assembles in this a tree with root label root and subtrees children; the declaration notwithstanding, the dynamic type of each entry of children must be the same as the dynamic type of this and the dynamic type of children must be the same as that returned by newSequenceOfTree.
• Aliases: reference root
• Replaces: this
• Clears: children
• Ensures:
this = compose(root, #children) 27 February 2019 OSU CSE

x=70 tn=? st=< , , >
tn.assemble(x, st);
27 February 2019 OSU CSE 16

How could st get a non- Example
empty value? By adding
trees to it using the add Code
method for Sequence.
x=70 tn=? st=< , , >
tn.assemble(x, st);
27 February 2019 OSU CSE 17

x=70 tn=? st=< , , >
tn.assemble(x, st);
x=70 tn= st = < >
27 February 2019 OSU CSE 18

Note the alias created here, which you cannot see in the tracing table.
x=70 tn=? st=< , , >
tn.assemble(x, st);
x=70 tn= st = < >
27 February 2019 OSU CSE 19

disassemble
T disassemble(Sequence> children)
• Disassembles this into its root label, which is returned as the value of the function, and subtrees in children; the declaration notwithstanding, the dynamic type of children must be the same as that returned by newSequenceOfTree.
• Replaces: children
• Clears: this
• Requires:
this /= empty_tree
• Ensures:
#this = compose(disassemble, children) 27 February 2019 OSU CSE

NaturalNumber root =
tn.disassemble(st);
27 February 2019 OSU CSE 21

NaturalNumber root =
tn.disassemble(st);
root=13 tn= st=< , >
27 February 2019 OSU CSE 22

int size()
• Reports the size of this.
• Ensures:
size = |this|
27 February 2019 OSU CSE

iterator Iterator iterator()
• Returns an iterator over a multiset of elements of type T.
• Ensures:
~this.seen * ~this.unseen = PRE_ORDER(this)
27 February 2019 OSU CSE

• Reports the root of this.
• Aliases: reference returned by root
• Requires:
this /= empty_tree
• Ensures:
there exists children: string of tree of T (this = compose(root, children))
27 February 2019 OSU CSE

NaturalNumber k =
tn.root();
27 February 2019 OSU CSE 26

NaturalNumber k =
tn.root();
27 February 2019 OSU CSE 27

Note the alias created here, which you cannot see in the tracing table.
NaturalNumber k =
tn.root();
27 February 2019 OSU CSE 28

replaceRoot T replaceRoot(T x)
• Replacestherootofthiswithx,andreturnsthe old root.
• Aliases:referencex
• Requires:
this /= empty_tree
• Ensures:
there exists children: string of tree of T (#this = compose(replaceRoot, children) and
this = compose(x, children)) 27 February 2019 OSU CSE

NaturalNumber k =
tn.replaceRoot(n);
27 February 2019 OSU CSE 30

NaturalNumber k =
tn.replaceRoot(n);
n=4 tn= k = 13
27 February 2019 OSU CSE 31

Note the alias created here, which you cannot see in the tracing table.
NaturalNumber k =
tn.replaceRoot(n);
n=4 tn= k = 13
27 February 2019 OSU CSE 32

Another Example
n = tn.replaceRoot(n);
27 February 2019 OSU CSE 33

Another Example
n = tn.replaceRoot(n);
27 February 2019 OSU CSE 34

Another Example
This use of the method
avoids creating an alias: it swaps n with the old root.
n = tn.replaceRoot(n);
27 February 2019 OSU CSE 35

int height()
• Reports the height of this.
• Ensures:
height = ht(this)
27 February 2019 OSU CSE

addSubtree
void addSubtree(int pos, Tree st)
• Updates: this
• Clears: st
• Requires:
this /= empty_tree and
0 <= pos and pos <= [number of children of this] • Ensures: this = [#this with subtree #st inserted at position pos] • Adds st at position pos in the subtrees of this; the declaration notwithstanding, the dynamic type of st must be the same as the dynamic type of this. 27 February 2019 OSU CSE removeSubtree Tree removeSubtree(int pos)
• Removesandreturnsthesubtreeatpositionposof this.
• Updates:this
• Requires:
this /= empty_tree and
0<=pos and pos < [number of children of this] • Ensures: this = [#this with subtree at position pos removed and returned as result] 27 February 2019 OSU CSE numberOfSubtrees int numberOfSubtrees() • Reports the number of subtrees of the root of this. • Requires: this /= empty_tree • Ensures: there exists root: T, children: string of tree of T (this = compose(root, children) and numberOfSubtrees = |children|) 27 February 2019 OSU CSE • OSU CSE Components API: Tree – http://cse.osu.edu/software/common/doc/ 27 February 2019 OSU CSE 40 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts