[Tutor] binary trees/ linked lists

[alan.gauld@bt.com]

> Is there anything like a linked list

A Python list is like a linked list....

> binary tree 

You have to do that yourself. Either using a list or 
dictionary or by creating node classes...

Lutz describes the process in his book 
Programming Python (1st Ed.)

There's rarely any need for a true linked list in Python, 
since the built in list does it all for you however trees 
can be useful.

Some tree pseudocode:

class Node:
   def __init__(self,data,ltree=None,rtree=None)
      self.data = data
      self.ltree = ltree
      self.rtree = rtree

   def add(self,node):
      if cmp(node.data,self.data) <= 0: 
         if self.ltree: self.rtree.add(node)
         else self.ltree = node
	else:
         if self.ltree: self.ltree.add(node)
         else self.ltree = node      

   def find(self,data):
      if self.data == data: return self
      elif data <= self.data: 
           if self.rtree: return self.rtree.find(data)
           else: return None
      else:
           if self.ltree: return self.ltree.find(data)
           else: return None

root = Node(5)
root.add(Node(2))
root.add(Node(1))
root.add(Node(7))
print root.find(5)
print root.find(7)

Something like that...

Alan g.