Results 1 to 16 of 16

Thread: Binary trees

  1. #1
    girgishf is offline Member
    Join Date
    Nov 2010
    Location
    Mississauga, ON, Canada
    Posts
    9
    Rep Power
    0

    Default Binary trees

    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.

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by girgishf View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    girgishf is offline Member
    Join Date
    Nov 2010
    Location
    Mississauga, ON, Canada
    Posts
    9
    Rep Power
    0

    Default

    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

  4. #4
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,457
    Rep Power
    20

    Default

    Double posted at
    binary tree

    db

  5. #5
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,315
    Blog Entries
    1
    Rep Power
    26

  6. #6
    girgishf is offline Member
    Join Date
    Nov 2010
    Location
    Mississauga, ON, Canada
    Posts
    9
    Rep Power
    0

    Default

    i double posted because no one replied yet

  7. #7
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,315
    Blog Entries
    1
    Rep Power
    26

    Default

    Quote Originally Posted by girgishf View Post
    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.

  8. #8
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by girgishf View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    girgishf is offline Member
    Join Date
    Nov 2010
    Location
    Mississauga, ON, Canada
    Posts
    9
    Rep Power
    0

    Default

    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

  10. #10
    girgishf is offline Member
    Join Date
    Nov 2010
    Location
    Mississauga, ON, Canada
    Posts
    9
    Rep Power
    0

    Default

    Quote Originally Posted by Fubarable View Post
    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.....

  11. #11
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by girgishf View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  12. #12
    girgishf is offline Member
    Join Date
    Nov 2010
    Location
    Mississauga, ON, Canada
    Posts
    9
    Rep Power
    0

    Default

    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

  13. #13
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by girgishf View Post
    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:

    Java Code:
    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
    cenosillicaphobia: the fear for an empty beer glass

  14. #14
    girgishf is offline Member
    Join Date
    Nov 2010
    Location
    Mississauga, ON, Canada
    Posts
    9
    Rep Power
    0

    Default

    Quote Originally Posted by JosAH View Post
    I'm not going to write the program for you but here is the algorihm; define a class Node like this:

    Java Code:
    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?

  15. #15
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by girgishf View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  16. #16
    girgishf is offline Member
    Join Date
    Nov 2010
    Location
    Mississauga, ON, Canada
    Posts
    9
    Rep Power
    0

Similar Threads

  1. Splay Trees
    By Growler in forum New To Java
    Replies: 0
    Last Post: 11-02-2010, 03:10 PM
  2. Need help with Trees...(8-puzzle)
    By ventrue in forum New To Java
    Replies: 2
    Last Post: 03-24-2009, 12:04 AM
  3. Tutorial on Binary Search Trees
    By JordashTalon in forum New To Java
    Replies: 3
    Last Post: 03-18-2009, 04:51 PM
  4. Game Trees
    By javaBoy1 in forum Advanced Java
    Replies: 0
    Last Post: 12-27-2008, 01:20 AM
  5. Help With Tournament Trees
    By wiggsfly in forum New To Java
    Replies: 2
    Last Post: 10-26-2008, 10:38 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •