Topic : Tree In this assignment, you implement a method to convert a tree to a s
ID: 3605620 • Letter: T
Question
Topic : Tree
In this assignment, you implement a method to convert a tree to a string.
Your HW8Tree class must include the BinaryNode.java code.
Your HW8Tree class must have an instance variable that refers to (points to) the root of a tree. This class must provide these recursive methods:( Help me this Black Bold)
a public boolean add(E item, boolean[] left) method to add values to the tree. Starting from the root, at each node, the method must go down to the left if the corresponding position in the array is true, and otherwise must go down to the right. Once a null pointer is reached, the item must be added to the tree in place of the null pointer.
It is an error if the array of booleans is too short. In this case, the add method should throw a RuntimeException.
a public List toList() method that stores in a list a reference to each of the objects in the tree, as visited in an in-order traversal. You can choose what kind of list to use, as long as it satisfies the List interface.
a public String toString() method that converts the tree to a string, in the same way that folders are printed: the root is first, followed by the children of the node indented 4 spaces, the grandchildren indented 8 spaces, and so on.
Each of these methods must use recursion to traverse the tree. In each case, the recursion may be in a helper method.
For example, consider a tree with root "hello". "hello" has two children, "foo" and "bar". "foo" has children "world", and "baz", and "bar" has children "bug" and "loop".
The toString method converts the tree to the following string:
The above example shows what the string looks like when it is printed. As a string, it actually looks like this:
As many of you already know, " " is the newline character in Java.
Calling toList should return a list with contents world, foo, baz, hello, bug, bar, loop. Only this order correctly reflects an in-order traversal.
To add the string "fum" below and to the right of "bug", we would call
You should also create a test class that lets you test your code. You do not need to turn in the test class.
Explanation / Answer
Some trees to run tests on:
>>> dp1 = Tree('dp', [Tree('d', ['the']), Tree('np', ['dog'])]) >>> dp2 = Tree('dp', [Tree('d', ['the']), Tree('np', ['cat'])]) >>> vp = Tree('vp', [Tree('v', ['chased']), dp2]) >>> tree = Tree('s', [dp1, vp]) >>> print(tree) (s (dp (d the) (np dog)) (vp (v chased) (dp (d the) (np cat))))
The node label is accessed using the label()method:
>>> dp1.label(), dp2.label(), vp.label(), tree.label() ('dp', 'dp', 'vp', 's')
>>> print(tree[1,1,1,0]) cat
The treepositions method returns a list of the tree positions of subtrees and leaves in a tree. By default, it gives the position of every tree, subtree, and leaf, in prefix order:
>>> print(tree.treepositions()) [(), (0,), (0, 0), (0, 0, 0), (0, 1), (0, 1, 0), (1,), (1, 0), (1, 0, 0), (1, 1), (1, 1, 0), (1, 1, 0, 0), (1, 1, 1), (1, 1, 1, 0)]
In addition to str and repr, several methods exist to convert a tree object to one of several standard tree encodings:
>>> print(tree.pformat_latex_qtree()) Tree [.s [.dp [.d the ] [.np dog ] ] [.vp [.v chased ] [.dp [.d the ] [.np cat ] ] ] ]
There is also a fancy ASCII art representation:
>>> tree.pretty_print() s ________|_____ | vp | _____|___ dp | dp ___|___ | ___|___ d np v d np | | | | | the dog chased the cat
>>> tree.pretty_print(unicodelines=True, nodedist=4) s vp dp dp d np v d np the dog chased the cat
Trees can be initialized from treebank strings:
>>> tree2 = Tree.fromstring('(S (NP I) (VP (V enjoyed) (NP my cookie)))') >>> print(tree2) (S (NP I) (VP (V enjoyed) (NP my cookie)))
Trees can be compared for equality:
>>> tree == Tree.fromstring(str(tree)) True >>> tree2 == Tree.fromstring(str(tree2)) True >>> tree == tree2 False >>> tree == Tree.fromstring(str(tree2)) False >>> tree2 == Tree.fromstring(str(tree)) False
>>> tree != Tree.fromstring(str(tree)) False >>> tree2 != Tree.fromstring(str(tree2)) False >>> tree != tree2 True >>> tree != Tree.fromstring(str(tree2)) True >>> tree2 != Tree.fromstring(str(tree)) True
>>> tree < tree2 or tree > tree2 True