8 Replies - 4822 Views - Last Post: 10 March 2013 - 08:42 AM Rate Topic: -----

#1 kikib92   User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 106
  • Joined: 26-September 11

Build a Binary Tree from XML File

Posted 08 March 2013 - 07:51 PM

Hi all. I've been working on a project where I am supposed to parse an xml file and build a binary tree from it. The file is much more dense than this but the layout is similar to this:
<?xml version="1.0" encoding="utf-8"?>
<MyJournal>
    <species>
        <name>Sea Creature</name>
        <species>
            <name>Fish</name>
            <species>
                <name>swordfish</name>
            </species>
            <species>
                <name>grouper</name>
            </species>
        </species>
        <species>
            <name>Mammal</name>
            <species>
                <name>dolphin</name>
            </species>
            <species>
                <name>whale</name>
            </species>
        </species>
    </species>
    <species>
        <name>Land animal</name>
        <species>
            <name>Mammal</name>
            <species>
                <name>dog</name>
            </species>
            <species>
                <name>cat</name>
            </species>
        </species>
        <species>
            <name>Bird</name>
            <species>
                <name>blue jay</name>
            </species>
            <species>
                <name>robin</name>
            </species>
        </species>
    </species>
</MyJournal>



I've figured out how to go through the data and create nodes in preorder but I am not sure how to build the tree structure once I get all the nodes. I was thinking if I could get the nodes inorder as well I could use the preorder and inorder to build the binary tree. However, I am stuck on how to get the data in order since the xml nodes do not have left and right pointers. I would really appreciate any pointers or direction you guys could give me. Thanks!

Is This A Good Question/Topic? 0
  • +

Replies To: Build a Binary Tree from XML File

#2 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7187
  • View blog
  • Posts: 24,357
  • Joined: 05-May 12

Re: Build a Binary Tree from XML File

Posted 08 March 2013 - 08:44 PM

Are you allowed to use an XML library? If you process the nodes using either a DOM, or getting SAX events, it's a simple matter of recursion.
Was This Post Helpful? 0
  • +
  • -

#3 kikib92   User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 106
  • Joined: 26-September 11

Re: Build a Binary Tree from XML File

Posted 08 March 2013 - 08:57 PM

Oh forgot to mention. We are using RapidXML for this project
Was This Post Helpful? 0
  • +
  • -

#4 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7505
  • View blog
  • Posts: 15,553
  • Joined: 16-October 07

Re: Build a Binary Tree from XML File

Posted 09 March 2013 - 04:15 AM

To build a binary tree, you need a key value. You have many possible key values here. Which one are you using? How are you accessing your data? Is a tree appropriate?
Was This Post Helpful? 0
  • +
  • -

#5 kikib92   User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 106
  • Joined: 26-September 11

Re: Build a Binary Tree from XML File

Posted 09 March 2013 - 06:09 PM

The key value is the name of the species. The assignment is to build a tree using the xml data so yes we are supposed to use one. The xml file I posted was just a sample of the layout of what I am doing. I'm using this smaller tree first so that I can figure out how to build the tree before I move on to the actual tree for the project since it is much more dense. This is the actual xml document for the project: http://www.cise.ufl....cts/species.xml Where the nodes of the tree will be objects with common name, scientific name, and rank. Scientific name and common name are the two keys that should be used to search the tree. However, the tree won't necessarily be sorted based on a key though since it is a phylogenetic tree.
I've been able to parse the xml document for the project in preorder but I'm having difficulty figuring out how to parse a file such as this inorder. Thanks!
Was This Post Helpful? 0
  • +
  • -

#6 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7505
  • View blog
  • Posts: 15,553
  • Joined: 16-October 07

Re: Build a Binary Tree from XML File

Posted 09 March 2013 - 07:58 PM

Ok, there are trees and binary trees and they ain't the same. Calling your structure a tree makes sense, calling it a binary tree less so. Then saying "the tree won't necessarily be sorted" means no binary tree, which must be sorted.

With what you have now, a reasonable "tree" structure would be:
struct Species {
   string name;
   vector <Species> subSpecies;
};


Was This Post Helpful? 0
  • +
  • -

#7 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7187
  • View blog
  • Posts: 24,357
  • Joined: 05-May 12

Re: Build a Binary Tree from XML File

Posted 09 March 2013 - 08:43 PM

View Postkikib92, on 09 March 2013 - 08:09 PM, said:

I've been able to parse the xml document for the project in preorder but I'm having difficulty figuring out how to parse a file such as this inorder. Thanks!

Why do you need to parse it in inorder? It doesn't make sense since the data is presented to you in preorder, why not read it in the order that data comes to you.

This post has been edited by Skydiver: 09 March 2013 - 08:43 PM

Was This Post Helpful? 0
  • +
  • -

#8 kikib92   User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 106
  • Joined: 26-September 11

Re: Build a Binary Tree from XML File

Posted 10 March 2013 - 08:20 AM

Oh okay. So I don't have to have nodes with left and right pointers. Instead I could loop through the XML document recursively and create nodes that have vectors of child nodes. Correct?
Was This Post Helpful? 0
  • +
  • -

#9 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7505
  • View blog
  • Posts: 15,553
  • Joined: 16-October 07

Re: Build a Binary Tree from XML File

Posted 10 March 2013 - 08:42 AM

That would be my guess, yes.

You're looking to represent the structure in memory so you can work with it. It really depends on the operations you need to do. You might have other structures that point to data based on keys for fast lookup. Or you might just search the thing on each request.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1