CODEWITHSUNDEEP
pythonrecursiondata-structuresbinary-tree
user2065276
user2065276

Reputation: 311

recursion on a tree with different type of nodes in python

I am building a Tree class that consists of inner nodes (denoted by the class Inner) and leaf nodes (denoted by the class Node). 

class Node(object):
    def __init__(self,bits,data):
        self.bits = bits
        self.data = data


class Inner(object):
    def __init__(self):
        self.bits = ''
        self.c0  = None
        self.c1 = None


class Tree(object):
    def __init__(self):
        self.root = None

   def insert_Item(self,key,datastr):
   #code goes here

I can insert both leafs and inner nodes using insert method. 

t = Tree()
t.insert('1111', 'A')
t.insert('1110', 'B')

The problem occurs with recursive formulation of insert method. I cannot call self.root.c0.insert() or self.root.c1.insert() assuming self.root.c0 and self.root.c1 points to Inner nodes. This is because Inner class does not have insert function.

What can i do to make insert method work on all three classes in a recursive fashion? Similarly i cannot do tree traversal as i get Error that Inner object has no attribute 'data'

Upvotes: 0

Views: 584

Answers (1)

manglano
manglano

Reputation: 844

Consider changing your implementation, so the tree only has nodes, traversal methods are a class method of the Node class, and the identity of the node as inner or leaf is determined as a function of whether the node has children or no children.

Generally, in terms of OOP, you want to implement as few classes as possible--as few as necessary to fully disambiguate the program's function while also providing the enhanced utility necessary for other programmers. Before implementing a new subclass, think: can another class perform the methods of this class without using polymorphism?

class Node(object):

      leftNode = None
      rightNode = None
      root = None

      def __init__(self,data,bit):
         self.bits = bit
         self.data = data
    /* I will make an assumption about the structure, left us assume the tree is simple, and preferentially populates the left subtree */
      def insert_Item(self,data,bit):
         if (leftNode == None):
              self.leftNode = Node(data,bit)
         elif (rightNode === None):
              self.rightNode = Node(data,bit)
         else:
              self.leftNode.insert_Item(data, bit)

class Tree(object):
    root = None
    def __init__(self, rootNode):
        self.root = rootNode

    def add_data(self,data,bit):
        self.root.insert_Item(data,bit)

With a little modification, these two classes will do everything you need. I recommend consulting this text as a primer: http://interactivepython.org/runestone/static/pythonds/index.html

Upvotes: 3

Related Questions