Hi all;
I have to create a Binary Tree(not a Binary Search Tree) whose node values are produced randomly...
If I had to create a Binary Search Tree , I could determine where the current node has to be inserted but in a Binary Tree I can't determine where the current node has to be inserted...
How can I determine where the current node has to be inserted in a Binary Tree ???
To my knowledge the only requirement for a binary tree is that each node has one parent and two children, or one root and two leaves if you want to use that analagy (the only exception is the first node entered, which has no parent/root). You can set it up however you want after that. Every node could have just a left child or a right child or you could always assign current input to left child before right child or right child before left. Every new node could be randomly entered into either a right or a left child of any node that doesn't already have one of each. You could randomly go right/left until you find a leaf. Etc.
To my knowledge the only requirement for a binary tree is that each node has one parent and two children, or one root and two leaves if you want to use that analagy. You can set it up however you want after that. Every node could have just a left child or a right child or you could always assign current input to left child before right child or right child before left. Every new node could be randomly entered into either a right or a left child of any node that doesn't already have one of each. You could randomly go right/left until you find a leaf. Etc.
Sorry, I couldn't told my problem clearly...
I meant the node values are produced randomly(A,K,G,B,...etc.) not the node positions.
In my tree , every node has to have two child nodes until the count > 0 (count is a user input and denotes the max nodes in a tree) .
For ex :
a
b c
d e f g
The above tree is possible, but the below is not in my assignment.
a
b
c
d
e
f
g
If this tree
a
b c
d e f g
is possible and the order of entry of the nodes named a to g (any one of which may have a random value stored within it) is in alphabetical order like this,
a
a
b
a
bc
a
bc
d
a
bc
de
a
bc
def
a
bc
defg
then the nodes need to have two pointer to type and the sequence of insertion into tree is always left child before right child as mentioned as one of the possibilities in my first post. (By the way, each node should have a value of sort stored in it too, otherwise it doesn't make sense just to link up the empty nodes).
Are you trying to write a balanced binary tree??
You should explore how AVL trees work.
When you say you need to create a binary tree but not a binary search tree, do you mean that that there is no order to the tree? In other words, do you simply insert the next element into the tree without doing any comparison of the values of the nodes? Normally when inserting a new node, in order to decide where to insert the node, you could traverse the tree from the root node. At each node, you would compare the value to insert to the value of the part of the tree you are inserting into. For example, if your tree was integers and the top node is 5, if you are inserting 7, you would go to the top node's right child since 7 is bigger than 5. If you were inserting 3, you would go left since 3 is less than 5. Are you saying that, in your case it makes no difference whether you go left or right and no comparisons are necessary. If it does not matter, what is the point in building it as a tree?
If it DOES matter, I'm confused by what you mean when you say you don't need to have a binary search tree. In order to insert your new element, you need to compare values and decide whether to left or right based on the comparison in order to be able to insert it into the right location. Thus you are building a binary search tree regardless of whether you are searching for values in that tree at a later time or not. Thus the AVL tree suggestion seems like the way to go since you need to build a balanced tree.
Am I misreading your goal?
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.