Binary trees

[girgishf]

Hi,

I have a set of data stored in a file, I want to know how to import this data and check:

1- if they construct binary tree
2- for their binary search property

and finally if they have AVL property. (not that important)

I'm really stuck on this. I have spent 1 week to figure it out but I couldn't.
I need your help.

if u provide a sample code, that would be great.

[JosAH]

Hi,

I have a set of data stored in a file, I want to know how to import this data and check:

1- if they construct binary tree
2- for their binary search property

and finally if they have AVL property. (not that important)

I'm really stuck on this. I have spent 1 week to figure it out but I couldn't.
I need your help.

if u provide a sample code, that would be great.

In what order is that data in your file stored? Infix? Prefix? Postfix? Can you give us an example?

kind regards,

Jos

[girgishf]

Thanks for ur reply :)

the data are arranged as follows:

1- number of nodes

2- position of nodes(where the first number is the index of the left node and the second number is the index of the right index) followed by the node name.

3- some transaction records(another story, I'm gonna ask about that later)

Thanks again

sample:

3
0 1 Victoria
2 1 Russia
0 1 France
delete Viroria
insert Egypt
search Poland

[DarrylBurke]

Double posted at
binary tree

db

[Fubarable]

Double posted at
binary tree

db

Double post locked and will be deleted later.

[girgishf]

i double posted because no one replied yet

[Fubarable]

i double posted because no one replied yet

You may bump this thread if it's been > 24 hours, but it is against forum rules to double post as it splits the discussion unnecessarily and may make a volunteer do work that has been done before. Please do not do this again.

[JosAH]

Thanks for ur reply :)

the data are arranged as follows:

1- number of nodes

2- position of nodes(where the first number is the index of the left node and the second number is the index of the right index) followed by the node name.

3- some transaction records(another story, I'm gonna ask about that later)

Thanks again

sample:

3
0 1 Victoria
2 1 Russia
0 1 France
delete Viroria
insert Egypt
search Poland

I still don't understand it; look at your example: both Victoria and France have the same index numbers. Please also explain the definition of your 'index numbers'.

kind regards,

Jos

[girgishf]

explanation to the index numbers:

the first field is the left child index, an integer that denotes the index of the left child of the current node. A left child index of 0 indicates that the current node has no left left child. the second field is the right child index, an integer that denotes the index of the right child of the current node. A right child index of 0 indicates that the current node has no right left child. the third field is the node`s name.

Example:

7
2 3 Lemons
4 0 Lesbos
0 5 Mikonos
6 0 Naxos
0 7 Paros
0 0 Rohdes
0 0 Queensland

[girgishf]

You may bump this thread if it's been > 24 hours, but it is against forum rules to double post as it splits the discussion unnecessarily and may make a volunteer do work that has been done before. Please do not do this again.

ok, I apologize for that.....

[JosAH]

explanation to the index numbers:

the first field is the left child index, an integer that denotes the index of the left child of the current node. A left child index of 0 indicates that the current node has no left left child. the second field is the right child index, an integer that denotes the index of the right child of the current node. A right child index of 0 indicates that the current node has no right left child. the third field is the node`s name.

Example:

7
2 3 Lemons
4 0 Lesbos
0 5 Mikonos
6 0 Naxos
0 7 Paros
0 0 Rohdes
0 0 Queensland

Ok, I think I got it: your index values are 1 (one) based). Lemons is the root node with a left child Lesbos and a right child Mikonos etc. right? If so this data set doesn't even is a search tree because for a search tree ileft child <= root <= right child. Is my notion correct?

kind regards,

Jos

[girgishf]

That`s right, I have 5 sets of data and I should check for each set if it is binary tree or not.

so i need a sample code that can do that....

Thanks

[JosAH]

That`s right, I have 5 sets of data and I should check for each set if it is binary tree or not.

so i need a sample code that can do that....

I'm not going to write the program for you but here is the algorihm; define a class Node like this:

public class Node {
   public String data;
   public Node left;
   public Node right;
   public Node parent;
}

As you can see this is just a data class (no methods and all public members). The last member 'parent' is set to another node (its parent) if some other node has claimed that it is the parent of that particular position. All nodes are stored in an array or ArrayList. Set the parent node to refer to ifself for the root node.

When you read a node for index i; check if there is a node 'claimed' by a parent (the parent member is not null) but not yet filled in (no data set yet). If so fill in the data field and create nodes (if any) for its children. Otherwise the data set doesn't form a tree.

Repeat the above for all nodes; when done check the entire array (or List) for claimed nodes that are not filled in. If you find any the data didn't form a tree; if you find null nodes the data didn't form a tree either.

If the data set forms a tree you can check whether or not the tree is an AVL tree.

kind regards,

Jos

[girgishf]

I'm not going to write the program for you but here is the algorihm; define a class Node like this:

public class Node {
   public String data;
   public Node left;
   public Node right;
   public Node parent;
}

As you can see this is just a data class (no methods and all public members). The last member 'parent' is set to another node (its parent) if some other node has claimed that it is the parent of that particular position. All nodes are stored in an array or ArrayList. Set the parent node to refer to ifself for the root node.

When you read a node for index i; check if there is a node 'claimed' by a parent (the parent member is not null) but not yet filled in (no data set yet). If so fill in the data field and create nodes (if any) for its children. Otherwise the data set doesn't form a tree.

Repeat the above for all nodes; when done check the entire array (or List) for claimed nodes that are not filled in. If you find any the data didn't form a tree; if you find null nodes the data didn't form a tree either.

If the data set forms a tree you can check whether or not the tree is an AVL tree.

kind regards,

Jos

Thanks for your reply.

I have these data stored in a txt file, how can I import them in the program and do this algorithm?

[JosAH]

I have these data stored in a txt file, how can I import them in the program and do this algorithm?

By reading the data from the file?

kind regards,

Jos

[girgishf]

ok,,,,thanks for your help