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?

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. — sean
– sean, Commented Dec 29, 2012 at 18:04

Hyperboreus · Accepted Answer · 2012-12-29 18:34:33Z

2

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)

answered Dec 29, 2012 at 18:34

Hyperboreus

32.5k9 gold badges50 silver badges88 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mei Over a year ago

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

Lev Levitsky · Accepted Answer · 2012-12-29 18:04:35Z

0

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.

answered Dec 29, 2012 at 18:04

Lev Levitsky

66.4k23 gold badges155 silver badges184 bronze badges

Comments

the_grandson · Accepted Answer · 2012-12-29 18:12:33Z

0

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.

answered Dec 29, 2012 at 18:12

the_grandson

151 silver badge10 bronze badges

1 Comment

Mei Over a year ago

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.

Collectives™ on Stack Overflow

Tree in python: recursive children creating

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related