A general tree implementation? [closed]

Question

I want to build a general tree whose root node contains 'n' children, and those children may contain other children.....

Answer 1

A tree in Python is quite simple. Make a class that has data and a list of children. Each child is an instance of the same class. This is a general n-nary tree.

class Node(object):     def __init__(self, data):         self.data = data         self.children = []      def add_child(self, obj):         self.children.append(obj) 

Then interact:

>>> n = Node(5) >>> p = Node(6) >>> q = Node(7) >>> n.add_child(p) >>> n.add_child(q) >>> n.children [<__main__.Node object at 0x02877FF0>, <__main__.Node object at 0x02877F90>] >>> for c in n.children: ...   print c.data ...  6 7 >>>  

This is a very basic skeleton, not abstracted or anything. The actual code will depend on your specific needs - I'm just trying to show that this is very simple in Python.

Answer 2

I've published a Python [3] tree implementation on my site: http://www.quesucede.com/page/show/id/python_3_tree_implementation.

Hope it is of use,

Ok, here's the code:

import uuid  def sanitize_id(id):     return id.strip().replace(" ", "")  (_ADD, _DELETE, _INSERT) = range(3) (_ROOT, _DEPTH, _WIDTH) = range(3)  class Node:      def __init__(self, name, identifier=None, expanded=True):         self.__identifier = (str(uuid.uuid1()) if identifier is None else                 sanitize_id(str(identifier)))         self.name = name         self.expanded = expanded         self.__bpointer = None         self.__fpointer = []      @property     def identifier(self):         return self.__identifier      @property     def bpointer(self):         return self.__bpointer      @bpointer.setter     def bpointer(self, value):         if value is not None:             self.__bpointer = sanitize_id(value)      @property     def fpointer(self):         return self.__fpointer      def update_fpointer(self, identifier, mode=_ADD):         if mode is _ADD:             self.__fpointer.append(sanitize_id(identifier))         elif mode is _DELETE:             self.__fpointer.remove(sanitize_id(identifier))         elif mode is _INSERT:             self.__fpointer = [sanitize_id(identifier)]  class Tree:      def __init__(self):         self.nodes = []      def get_index(self, position):         for index, node in enumerate(self.nodes):             if node.identifier == position:                 break         return index      def create_node(self, name, identifier=None, parent=None):          node = Node(name, identifier)         self.nodes.append(node)         self.__update_fpointer(parent, node.identifier, _ADD)         node.bpointer = parent         return node      def show(self, position, level=_ROOT):         queue = self[position].fpointer         if level == _ROOT:             print("{0} [{1}]".format(self[position].name, self[position].identifier))         else:             print("\t"*level, "{0} [{1}]".format(self[position].name, self[position].identifier))         if self[position].expanded:             level += 1             for element in queue:                 self.show(element, level)  # recursive call      def expand_tree(self, position, mode=_DEPTH):         # Python generator. Loosly based on an algorithm from 'Essential LISP' by         # John R. Anderson, Albert T. Corbett, and Brian J. Reiser, page 239-241         yield position         queue = self[position].fpointer         while queue:             yield queue[0]             expansion = self[queue[0]].fpointer             if mode is _DEPTH:                 queue = expansion + queue[1:]  # depth-first             elif mode is _WIDTH:                 queue = queue[1:] + expansion  # width-first      def is_branch(self, position):         return self[position].fpointer      def __update_fpointer(self, position, identifier, mode):         if position is None:             return         else:             self[position].update_fpointer(identifier, mode)      def __update_bpointer(self, position, identifier):         self[position].bpointer = identifier      def __getitem__(self, key):         return self.nodes[self.get_index(key)]      def __setitem__(self, key, item):         self.nodes[self.get_index(key)] = item      def __len__(self):         return len(self.nodes)      def __contains__(self, identifier):         return [node.identifier for node in self.nodes if node.identifier is identifier]  if __name__ == "__main__":      tree = Tree()     tree.create_node("Harry", "harry")  # root node     tree.create_node("Jane", "jane", parent = "harry")     tree.create_node("Bill", "bill", parent = "harry")     tree.create_node("Joe", "joe", parent = "jane")     tree.create_node("Diane", "diane", parent = "jane")     tree.create_node("George", "george", parent = "diane")     tree.create_node("Mary", "mary", parent = "diane")     tree.create_node("Jill", "jill", parent = "george")     tree.create_node("Carol", "carol", parent = "jill")     tree.create_node("Grace", "grace", parent = "bill")     tree.create_node("Mark", "mark", parent = "jane")      print("="*80)     tree.show("harry")     print("="*80)     for node in tree.expand_tree("harry", mode=_WIDTH):         print(node)     print("="*80)