Description
Part 1-
Consider the binary tree representation of general trees in our textbook where the left
branch of a node is the first child, and each right branch is connected to the next sibling (if
any).
– Extend the BinaryTree class to implement general trees.
– Write an add method that takes a parentItem and a childItem and inserts the childItem
as the last child of the parentItem if the parentItem is already in suach a tree structure.
The method returns true if insertion is successful and false if the parentItem is not in
the tree.
– Write the following methods to search an item in such a general tree structure:
a) levelOrderSearch (): Traverses the tree in level order; First the root node (i.e., the
node in the first level), then the children of the root node (i.e., nodes in the second
level), then the children of the nodes in the second level (i.e., nodes in the third
level), and so on.
b) postOrderSearch (): Traverse a node before traversing its subtrees starting from
the root node. Search for the item during traversal. Return the Node reference if
the item is in the tree and null if it is not in the tree.
– Override the preOrderTraverse method to traverse to obtain the string representation
of the tree.
– As a test construct at least two separate trees by adding 12 new items in the tree. You
should try to cover all possible cases with these insertions. You should check the
resulting tree by converting it into a string after each insertion.
– Analyze time complexity of your methods
Note that, method representations are not the prototypes of methods.
Part 2-
Construct a general search tree structure where the tree includes multidimensional items.
Each level of a mds tree (multidimensional search tree) splits all children along a specific
dimension, using a hyperplane that is perpendicular to the corresponding axis. At the root,
all children will be split based on the first dimension (i.e. if the first-dimension coordinate
is less than the root it will be in the left-subtree and if it is greater than the root it will be in
the right-subtree). Each level down in the tree divides on the next dimension, returning to
the first dimension once all others have been exhausted. So, every internal node can be
thought of as implicitly generating a splitting hyperplane that divides the space into two
parts, half-spaces. The items to the left of this hyperplane are represented by the leftsubtree of that node and items right of the hyperplane are represented by the right subtree.
For example, in a 3-dimensional tree, the root would have an x-aligned plane, the root’s
children would both have y-aligned planes, the root’s grandchildren would all have zaligned planes, the root’s great-grandchildren would all have x-aligned planes, the root’s
great-great-grandchildren would all have y-aligned planes, and so on.
Extends the BinaryTree class to implement mds trees. Your class should implement the
SearchTree interface.
Note:
Obey OOP principles
Use meaningful and related class, variable, method etc. names
Use intelliJ IDE on the given VM. VM download link can be found on moodle(in
HW1)
Your submission is HW04_studentnumber.zip and include following files:
o intelliJ project file
o Report.pdf
o Javadoc
The report must be in format “ReportFormat.doc” which was used in HW1
The implementations will be 75 points and the report is 25 points out of 100
Submit your homework until the last submission date
For your questions about homework, feel free to send an email b.koca@gtu.edu.tr
Good Luck!