Ok so this is my task:
Description:

Create a generic class called GenBinTree. GenBinTree will use nodes
that store a value of the generic type to store its contents.
This tree will not be a search tree (no ordering of nodes by value).

What ges me its the the part that says it will not be a search tree, from what i see dont get how a tree can be a tree withouth being a search tree, I do not understand how to implement a tree with the given criteria.

Recommended Answers

All 5 Replies

A tree is not a search tree when it is used to store certain data that may not be comparable. For example, you want to store data that just need to fill into a tree with at most 3 branches. Though, the tree may require to know what the current height it is because you are not going to search the tree.

/*
For example... I declare a tree that can have at most 3 branches...
Start, current height = 0
Input "m"
  root is "m", current height = 1
Input "a"
  check current height is full (only 1 node at root),
  increment the current height and insert the item
  tree becomes...          m            current height = 2
                        /  |  \
                      a    nl  nl
                     /|\
                    nlnlnl
Input "k"
  tree becomes...       .  m  .         current height = 2
                      /    |    \
                    a      k      nl
                   /|\    /|\
                  nlnlnl nlnlnl
Input "e"
  tree becomes...       .  m  .         current height = 2
                      /    |    \
                    a      k      e
                   /|\    /|\    /|\
                  nlnlnl nlnlnl nlnlnl
Input "m"
  check current height is full (all 3),
  increment the current height and insert the item
  tree becomes...       .  m  .         current height = 3
                      /    |    \
                    a      k      e
                   /|\    /|\    /|\
                  m nlnl nlnlnl nlnlnl
                /|\
               nlnlnl
*/

i understand i belive , so for a binary tree the most number of brancher is two of course, does the data get inserted from left to right am guessing? for example

   k    insert a  k    insert z    k
   / \             /\              /\
  b               b  a            b   c
                                 /\   /\  
                                z        

while checking that the the hegiht is not full instead of comparing the data?

Yes, you could assume that the data is entered from left to right without any comparison.

Ok so i just started my program but actually found out that the position of the new node or whatever is being inserted will be in a randomm position, heres what the book says

a) add
       Adds a node to the tree.  The node will be added as a leaf.  The position
       of the new node will be randomly determined, starting at the root and 
       moving down the tree, randomly going left or right at each level, until
       a null is reached. 

Is what that am doing it random? but seems to be ordered from right to left, yet also seems to be random.

Then you could use a Hash-liked when store children instead of ArrayList. What you would need to check whether you can insert into the children group is to see if the size is less than the maximum size allow per node. In this case, the insertion will not need to be in order.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.