Tree in python: recursive children creating

Question

I have a class called rectangle with two parametres (SX and SZ). I need to do a function that will devide me a first rectangle in two parts with a line in a random place on the wider dimension, then these two new rectangles will be divided in two, then four etc. I use a simple tree structure and a function like this:

def devide(self):
 if (self.SX>self.SZ): #check which dimension is bigger
 temp=randint (int(self.SX/4), int(self.SX*3/4)) #generate random from x/4,3x/4 
 left=rectangle(temp, self.SZ) #create nodes
 right=rectangle(self.SX-temp, self.SZ)
 self.addChild(left) 
 self.addChild(right)
 else:
 temp=randint (int(self.SZ/4), int(self.SZ*3/4)) 
 up=rectangle(self.SX, temp) 
 down=rectangle(self.SX, self.SZ-temp)
 self.addChild(up)
 self.addChild(down)
 for c in self.getChilds():
 while (c.level()<3): ####why doesn't it work?:(
 c.devide() 

And the function level()— it should (but it doesn't) return a value of how many levels are between the root and the actual node:

def level(self): 
 root=self
 a=0
 while root.isRoot()==False: 
 a+=1
 root=root.getParent()
 return a

Important things for me are:

• how to limit those divisions (for example, to have only 1+2+4+8 nodes)? I mean, there are no static variables in Python and my function level() doesn't work properly.

• how to get the access to the youngest children (for example, to have them in array)

I am new in programming, especially in Python. Could somebody help me, please?

• sean: To add a limitation on the number of levels just pass it into the divide function via a keyword like so: def divide( rectangle, Max_levels=5 ) then each iteration in the recursive call do it such that ` Max_level - 1` and stop refusing once max_level reaches 0.

Answer 1

Maybe you are looking for something like this: (It is a double-linked (parent knows children and children know parent) binary tree)

#! /usr/bin/python3.2
import random
class Rectangle:
 def __init__ (self, width, height, parent = None):
 self.width = width
 self.height = height
 self.parent = parent
 self.children = []
 @property
 def level (self):
 return 0 if not self.parent else 1 + self.parent.level
 def split (self):
 if self.children: raise Exception ('Already split')
 ratio = random.random () * .5 + .25 #split between 1/4 and 3/4
 if self.width > self.height:
 width = int (ratio * self.width)
 self.children = [Rectangle (width, self.height, self),
 Rectangle (self.width - width, self.height, self) ]
 else:
 height = int (ratio * self.height)
 self.children = [Rectangle (self.width, height, self),
 Rectangle (self.width, self.height - height, self) ]
 def splitUntilLevel (self, maxLevel):
 if maxLevel <= self.level: return
 self.split ()
 for child in self.children: child.splitUntilLevel (maxLevel)
 def __str__ (self):
 s = '{}{} x {}\n'.format (' ' * (2 * self.level), self.width, self.height)
 for child in self.children: s += str (child)
 return s
r = Rectangle (100, 100)
r.splitUntilLevel (3)
print (r)

• Mei: Just... wow. Thank you very much, your code is so elegant and definite. It will be useful, I am really grateful.

Answer 2

It should be a += 1, not a = +1.

Also, calling divide() on an object will not increase its own level, so you'll never get out of the loop. You should check the level on the terminal leaves of the tree.

Answer 3

What does addChild(up) and addChild(down)? You could associate to each rectangle an integer that contains the self level, much more easy and if you want to limit the depth of the tree when generating a new rectangle just evaluate the result of: 2^h h-> depth of the tree.

• Mei: It's just adding a new node (called up or down) as a child to an actual node- i need this function for some graphic stuff and that's why called it like that. Thank you for this idea with a new integer, I think I will use it.