getChildren Binary Tree Python

manolakis · 07-25-2017, 06:11 PM

Hello,

I want a getChildren function for an item in a decision tree. This function should return a list of all chirdren of the item. Even for children of children. The binary tree is represented in a tree of 0s and 1s. like the following:

Code:

T = [[0, 1, 0, 0, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 1, 0, 0],
    [1, 0, 0, 0, 0],
    [0, 0, 0, 1, 0]]

Where is one means that at that index there is a child.
Could anyone please tell me how to write a recursive function for getChildren? My attempt is the following

Code:

def getChildren(T, item, children):
    for x in range(0, len(T[item]), 1):
        if T[item][x] == 1:
            children.append(x)
            getChildren(T, T[item][x], children)
    return children

# This is a call for getting the children of the 3rd node
getChildren(T, 2, [])

This unfortunately does not seem to work. Any suggestions

NevemTeve · 07-26-2017, 02:00 PM

Could you please explain this T array, how does it represent a binary tree?

astrogeek · 07-26-2017, 02:56 PM

What you are looking for is a reachability matrix of the graph (tree).

You can find algorithms for that in various texts and online, although the implementation is non-trivial and will vary greatly depending on the language used (how the graph data are stored, whether the language supports matrices directly or must use arrays, array types, etc...).

Here is a chapter which describes the basic problem.

Here is a stackexchange discussion of related problems (getting all descendents, i.e. children involves most of these ideas).

Several years ago my son wrote a set of both PHP and C++ classes which begin with tree structured data in a relational database and end with reachability and ordering (adjacency) lists and diagrams extracted from that data, which I still use but do not claim to fuly understand (He is much smarter than I am!

). While I cannot give a working example, I can point you in the right direction - graph theory and specifically, reachability matrix and related concepts.