### Thread: finding node in a tree

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

Join Date
Feb 2004
Posts
71
Rep Power
15

#### 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. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2001
Location
Houston, TX
Posts
383
Rep Power
17
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".
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2004
Posts
71
Rep Power
15
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)
4. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
London, England
Posts
1,585
Rep Power
1377
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
5. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2004
Posts
71
Rep Power
15
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.
6. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
London, England
Posts
1,585
Rep Power
1377
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
7. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2004
Posts
71
Rep Power
15
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
8. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2003
Posts
35
Rep Power
15
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