1

I'm trying to implement a Tree in python, I found this thread and tried to work my own tree, but I got stuck at how to add grand childrens.

the tree I'm trying to construct is like:

Root
    ch1
        ch2
            ch3
            ch4

So I figured that the add_child() method should be recursive:

1, If the tree has no children, add children to Root

2, for each children of Root, if one of the children equals parent, add children to it and stop the loop(so the new child is actually a grand child).

3, if there is no match, call add_child() on the current children.

But my code gives me:

Root
    ch1
        ch2
            ch3
                ch4

Btw, every time I work with recursive algorithms I get confused, could anyone give me some good advice of how to write recursive codes? or is there any good tutorials?

class Node(object):
    def __init__(self, data, parent=None):
        self.data = data
        self.children = []
        self.parent = parent

    def __repr__(self, level=0):
        ret = "\t" * level + repr(self.data) + "\n"
        for child in self.children:
            ret += child.__repr__(level + 1)
        return ret

    def add_child(self, node, parent):

        if self.children == []:
            self.children.append(node)
            return

        for child in self.children:
            if child == parent:
                child.children.append(node)
                return
            else:
                child.add_child(node, parent)

        # self.children.append(node)


if __name__ == '__main__':

    tree = Node('Root')
    tree.add_child(Node('ch1'), 'Root')
    tree.add_child(Node('ch2'), 'ch1')
    tree.add_child(Node('ch3'), 'ch2')
    tree.add_child(Node('ch4'), 'ch2')
    print tree
Community
  • 1
  • 1
shengy
  • 9,461
  • 4
  • 37
  • 61

1 Answers1

1

The following section makes no sense:

if self.children == []:
    self.children.append(node)
    return

If a node has no children you automatically add the node to that node? What if the node should be added to a different parent?

You probably meant to write:

def add_child(self, node, parent):
    if self.data == parent:
        self.children.append(node)
        return
    for child in self.children:
        child.add_child(node, parent)

which produces the tree as expected.

Simeon Visser
  • 118,920
  • 18
  • 185
  • 180
  • It works! thanks, btw can you give me some advice about writing/debugging recursive programs? Anything would help, I'm so frustrated about this... – shengy Nov 27 '13 at 15:02
  • @shengy: practise often and try to keep the data structure in mind. What needs to happen at a node and where does data need to go? For example: do I need to pass information in the recursive call and what information do I need to return from a recursive call? – Simeon Visser Nov 27 '13 at 15:03