(1) Please implement a binary search tree and particular the following functions:
- Search for an item based on the key value (search)
- Introduction to some key element in the SDS (insert)
- Calculating height of the tree (height)
- Calculate amounts of the binary tree elements (size)
Of course, you can add additional auxiliary methods in class BinTree, where deemed necessary. The node of the binary tree will contain an integer number, a pointer to the left child and a pointer to the right child , and it will be materialized as a class name BinNode.
After this you will materialize a class named BinTreeApp, which will do the followings:
1. It will introduce the following sequence numbers 1, 2, 3, ... 50 in an empty binary tree and then calculates and prints the screen height of the tree.
2. It will introduce the following sequence numbers 30 , 20, 40 , 10, 45, 35 , 25, 9
8 ... 2, 1 in an empty binary tree and then calculates and prints in the screen the height of the tree.
3. It will introduce 200 random numbers from the interval [ 1,1000 ] in an empty binary tree and will print in the screen the contents of the tree, sorted in ascending order. Each random number will be imported only if it is not already in the tree. The method of classification should not be used by some auxiliary data structure , e.g. table.
4. It will introduce N random numbers from the interval [ 1100.000 ] on a blank
binary tree and calculates and prints the average number of comparisons ( between elements of the tree ) for insertion ( given that: average number of comparisons = total number of comparisons / N ). Then you select 1000 random numbers in the same interval [ 1100.000 ] do a search in each one, and calculate and print the average number of comparisons ( between elements of the tree ) made ??during the search.
5. Shall the above energy (4 ) for N = { 25.000 , 50.000 , 75.000 , 100.000 } and prints the corresponding measurements on the screen. Then you complete the a table with the measurements. The number refers to the number of data elements introduced in the tree (can be N or less , depending on whether you allow duplicates ).
+More will follow, after this is done+
Knowledge of java
