CODEWITHSUNDEEP
pythonrecursiontree
user1993753
user1993753

Reputation: 15

Python: Read tree like data from text file and store in dictionary

I have a text file containing tree like data separated by a space with following structure: 'Number of branches' 'Name of node' ... 0 (0 means no further branch) For example:

1 A 3 B 2 C 0 
        D 0
    E 1 F 0
    G 2 H 0
      I 0

the corresponding dictionary 'tree' should be like:

tree = {'A': {'B': {'C': {},
                    'D': {}},
              'E': {'F': {}},
              'G': {'H': {},
                    'I': {}}}}

I think recursive way is the right way to do it but I am unable to make it work. I have following function so far:

def constructNodes(branch):

    global nodes_temp

    if not branch:
        branch = deque(file.readline().strip().split())
    node1 = branch.popleft()
    nodes_temp.add(node1)
    nbBranches = int(branch.popleft())
    for i in xrange(nbBranches):
        constructNodes(branch)
    return nodes_temp

Thanks in advance for the help.

Upvotes: 0

Views: 2469

Answers (2)

Paul Hankin
Paul Hankin

Reputation: 58319

You don't need a deque to iterate through a sequence, you can use a regular python iterable. That can make things a lot more concise.

data = """
1 A 3 B 2 C 0 
        D 0
    E 1 F 0
    G 2 H 0
      I 0"""

def construct_nodes(data):
    return dict((next(data), construct_nodes(data))
                for _ in xrange(int(next(data))))

print construct_nodes(iter(data.split()))

Upvotes: 3

Mark Tolonen
Mark Tolonen

Reputation: 177901

I think this is what you want:

from collections import deque

data = deque('''\
1 A 3 B 2 C 0 
        D 0
    E 1 F 0
    G 2 H 0
      I 0'''.split())

def constructNodes():
    D = {}
    count = int(data.popleft())
    for _ in range(count):
        node = data.popleft()
        D[node] = constructNodes()
    return D
tree = constructNodes()
print(tree)

Output:

{'A': {'B': {'C': {}, 'D': {}}, 'G': {'H': {}, 'I': {}}, 'E': {'F': {}}}}

With some formatting:

{'A': {'B': {'C': {},
             'D': {}},
       'G': {'H': {},
             'I': {}},
       'E': {'F': {}}}}

Upvotes: 2

Related Questions