CODEWITHSUNDEEP
pythonrecursiontree
adapap
adapap

Reputation: 665

Non-binary tree recursion

I am trying to make a program that sets up a non-binary tree with each node being connected to children. In this test example, I used a binary tree for simplicity. The input is this:

1
3   5
4   6

(Tab characters are used between numbers). I am trying to generate the tree starting at the root (1), with its children being 3 and 5, and each of those nodes have children 4 and 6. The tree diagram might look something like this:

    4
   /
  3
 / \
1   6
 \ /
  5
   \
    4

When I try to add children to my tree, it creates an infinite loop calling my recursion function. I've narrowed down the problem to it calling the function with branch being 1 on loop, but here is the code:

# input is a list of branch values
file = open("treehash.txt","r")
input = file.readlines()
for line in range(len(input)):
input[line] = input[line].rstrip().split('\t')
file.close()

# create the tree node
class Tree(object):
    value = None
    children = []
    def __init__(self, value):
        self.value = value

# adds all children to a given parent
def set_children(parent, branch):
    if branch < len(input) - 1:
        for num in input[branch + 1]:
            parent.children.append(Tree(int(num)))
        for child in parent.children:
            set_children(child, branch + 1)

# store all roots in array
roots = []
for root in range(len(input[0])):
    roots.append(Tree(int(input[0][root])))
    set_children(roots[root], 0)

Upvotes: 0

Views: 3095

Answers (1)

Michael Butscher
Michael Butscher

Reputation: 10969

If you write variables in a class like you did with

class Tree(object):
    value = None
    children = []

they are bound to the class, not an instance. For value you overwrite it with an instance-bound variable in the __init__ constructor but the list referred by children is shared by all Tree instances.

Delete above variable settings and use instead:

class Tree(object):
    def __init__(self, value):
        self.value = value
        self.children = []

Upvotes: 1

Related Questions