#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2004
    Posts
    71
    Rep Power
    11

    finding node in a tree


    Hi.
    I have a question that might be a bit silly.
    I have a tree structure ( not binary), and a pointer to the root node.
    How do I write a function that looks for a node with a certain name and returns the node ( if found), or None.
    ( python has no static variables, which makes it a bit more difficult)
    thank you very much
    Roy
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2001
    Location
    Houston, TX
    Posts
    383
    Rep Power
    13
    We need more info on the data structure. The generic answer is "walk the tree", with more specific (but still generic) answers like, "do a depth-first traversal".
    Debian - because life's too short for worrying.
    Best. (Python.) IRC bot. ever.
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2004
    Posts
    71
    Rep Power
    11
    Thank you for your quick reply.
    Every node consists of:
    Node:
    name=the name of the node
    and variable number of attributes

    I want to compare the Node.name to the name that was recieved as
    parameter, if it is equal then return the node (self)
    if not, keep on looking or return None ( if no nodes left to look in)
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    London, England
    Posts
    1,585
    Rep Power
    1373
    That still doesn't tell us how you walk the tree - how do you get from one node to the next?

    What you describe is not a tree, unless the 'variable list of attributes' can also contain nodes. Is this the case, or are the nodes linked in some other way?


    Dave - The Developers' Coach
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2004
    Posts
    71
    Rep Power
    11
    You right Dave, my apology ( thinks for your patience )
    Every Node has some linking info as well:
    children =[]
    parent = None

    children is a list that contains all the direct children of the node.
    parent contains None ( if it is the root node) or reference to another node, which it is his it's parent.
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    London, England
    Posts
    1,585
    Rep Power
    1373
    There are several ways to do it. If you are using 2.2 or above then you could use generators to add an iterator to the class that would allow you to treat the tree as a sequence of nodes. If you also added a comparison function for the name attribute you could use the 'in' operator to test for the presence of a node with a give name.

    e.g.

    Code:
    #this import is only needed for 2.2
    from __future__ import generators
    
    class Node:
        def __init__(self, name, *nodes):
            self.name = name
            self.children = list(nodes)
            
        def addChild(self, kid):
            self.children.append(nodes)
            
        def __iter__(self):
            yield self
            for child in self.children:
                for node in child:
                    yield node
    
        def __eq__(self, name):
            return self.name == name
    
    
    if __name__ == '__main__':
        #create some sample data
        a = Node('a')
        b = Node('b')
        c = Node('c', a, b)
        d = Node('d', c)
        e = Node('e')
        f = Node('f')
        g = Node('g', d, e, f)
        h = Node('h')
        i = Node('i', g, h)
        j = Node('j', i)
        k = Node('k')
        l = Node('l', k, j)
        root = Node('root', l)
    
        #print out the nodes (depth first)
        for node in root: print node.name,
        print
        #test for node with the given name
        print 'x' in root
        print 'i' in root
    The output from the above script:
    Code:
    E:\prj\sandbox>python test2.py
    root l k j i g d c a b e f h
    False
    True
    Dave - The Developers' Coach
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2004
    Posts
    71
    Rep Power
    11
    Thank you very much Dave for your solution.
    it helped me heaps!!!
    There is one more issue though...
    1. How to delete an item (and all it's children as well)?
    2. How can I use built in operator overloading method to invoke
    deletion (like __delitem__)?
    Thank you very much
    Roy
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    35
    Rep Power
    11
    In all honesty, it sounds like you're prying for answers to a HW assignment. Rather than give you code, here are some hints:

    1. How to delete an item (and all it's children as well)?

    Traverse the tree until you find the parent of the node to delete; you will know that you are at the parent of the node to delete when its "children" array contains the node to delete. Just call children.remove() on that node.

    2. How can I use built in operator overloading method to invoke
    deletion (like __delitem__)?


    Just call the above code __delitem__, I believe (haven't done any operator overloading myself -- never had the need -- so someone else correct me if I'm wrong).

    - tps

IMN logo majestic logo threadwatch logo seochat tools logo