|
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| |||||||||
![]() |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
|
|
|
Get inside! Sample the range of functionality easily built with JMSL Library for Time Series Data Analysis, Heat Maps, Portfolio Optimization, Monte Carlo Simulation, Stock Price Charting and more. Download Now! |
|
#1
|
|||
|
|||
|
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
|
|||
|
|||
|
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
|
|||
|
|||
|
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
|
|||
|
|||
|
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
|
|||
|
|||
|
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
|
|||
|
|||
|
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
|
|||
|
|||
|
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
|
|||
|
|||
|
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 |
![]() |
| Viewing: Dev Shed Forums > Programming Languages > Python Programming > finding node in a tree |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
|
|