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
27 February 2019 OSU CSE 8
Tree
27 February 2019 OSU CSE 9
newSequenceOfTree Sequence
• Creates and returns an empty Sequence
• Ensures:
newSequenceOfTree = < >
27 February 2019 OSU CSE
newSequenceOfTree
Sequence
• Creates and returns an empty
has the right type.
Sequence
• Ensures:
newSequenceOfTree = < >
27 February 2019 OSU CSE
The mathematical model of Sequence
string of tree of T, so this value (the empty string)
Sequence
27 February 2019 OSU CSE 12
Sequence
27 February 2019 OSU CSE 13
Note that the value of the
receiver does not only its type.
Sequence
27 February 2019 OSU CSE 14
void assemble(T root, Sequence
• 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
• 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
• 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
• 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
• 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