Create tree from dictionary python

Question

I have a python dictionary and I would like to create a tree from it. The dictionary is something like this:

Nội dung chính Show

Learn about trees and how to implement them.
Without assignment
How do you create a tree list in Python?
Is a tree a dictionary in Python?
Can you turn a dictionary into a list Python?
Can you turn a dictionary into a string?

dict_={"2":{'parent': "1"},"1":{'parent': None},"3":{'parent': "2"}}

in this case, the root is "1"

I tried to use treelib library but the problem when I iterate on the dictionary and create a node, its parent isn't created yet. For example, if I want to create a node for "2", its parent("1") isn't created yet, so can not do it. Any idea?

asked Dec 23, 2018 at 14:03

1

You could do the following, using treelib:

from treelib import Node, Tree

dict_ = {"2": {'parent': "1"}, "1": {'parent': None}, "3": {'parent': "2"}}

added = set()
tree = Tree()
while dict_:

    for key, value in dict_.items():
        if value['parent'] in added:
            tree.create_node(key, key, parent=value['parent'])
            added.add(key)
            dict_.pop(key)
            break
        elif value['parent'] is None:
            tree.create_node(key, key)
            added.add(key)
            dict_.pop(key)
            break

tree.show()

Output

1
└── 2
    └── 3

The idea is to add a node only if the parent is present in the tree or the parent is None. When the parent is None add it as root.

answered Dec 23, 2018 at 14:15

Dani MesejoDani Mesejo

58.5k6 gold badges45 silver badges68 bronze badges

You can do the following. First, transform the data structure to a parent-children mapping:

from collections import defaultdict

d = defaultdict(list)  # parent: List[children]
for k, v in dict_.items():
    d[v['parent']].append(k)

Then, starting with the root

root = d[None][0]

tree = Tree()
tree.create_node(root, root)

Create the tree from the top:

agenda, seen = [root], set([root])
while agenda:
    nxt = agenda.pop()
    for child in d[nxt]:
        tree.create_node(child, child, parent=nxt)
        if child not in seen:
            agenda.append(child)
            seen.add(child)

answered Dec 23, 2018 at 14:19

user2390182user2390182

68.6k6 gold badges60 silver badges82 bronze badges

Learn about trees and how to implement them.

Roots

A tree as a data structure can quickly become a complex mathematical subject ( check the wiki 👀 ), we are surrounded by real and virtual things (data really) that can be modeled and represented by a tree, so it is a very handy subject to understand even at a basic level.

Using Python's built-in defaultdict we can easily define a tree data structure:

def tree(): return defaultdict(tree)

That's it!

It simply says that a tree is a dict whose default values are trees.

(If you're following along at home, make sure to from collections import defaultdict)

(Also: Hacker News reader @zbuc points out that this is called autovivification. Cool!)

Examples

JSON-esque

Now we can create JSON-esque nested dictionaries without explicitly creating sub-dictionaries—they magically come into existence as we reference them:

users = tree()
users['harold']['username'] = 'hrldcpr'
users['handler']['username'] = 'matthandlersux'

We can print this as json with print(json.dumps(users)) and we get the expected:

{"harold": {"username": "hrldcpr"}, "handler": {"username": "matthandlersux"}}

Without assignment

We can even create structure with no assignment at all, since merely referencing an entry creates it:

taxonomy = tree()
taxonomy['Animalia']['Chordata']['Mammalia']['Carnivora']['Felidae']['Felis']['cat']
taxonomy['Animalia']['Chordata']['Mammalia']['Carnivora']['Felidae']['Panthera']['lion']
taxonomy['Animalia']['Chordata']['Mammalia']['Carnivora']['Canidae']['Canis']['dog']
taxonomy['Animalia']['Chordata']['Mammalia']['Carnivora']['Canidae']['Canis']['coyote']
taxonomy['Plantae']['Solanales']['Solanaceae']['Solanum']['tomato']
taxonomy['Plantae']['Solanales']['Solanaceae']['Solanum']['potato']
taxonomy['Plantae']['Solanales']['Convolvulaceae']['Ipomoea']['sweet potato']

We'll prettyprint this time, which requires us to convert to standard dicts first:

def dicts(t): return {k: dicts(t[k]) for k in t}

Now we can prettyprint the structure with pprint(dicts(taxonomy)):

{'Animalia': {'Chordata': {'Mammalia': {'Carnivora': {'Canidae': {'Canis': {'coyote': {},
                                                                            'dog': {}}},
                                                      'Felidae': {'Felis': {'cat': {}},
                                                                  'Panthera': {'lion': {}}}}}}},
 'Plantae': {'Solanales': {'Convolvulaceae': {'Ipomoea': {'sweet potato': {}}},
                           'Solanaceae': {'Solanum': {'potato': {},
                                                      'tomato': {}}}}}}

So the substructures we referenced now exist as dicts, with empty dicts at the leaves.

Iteration

This tree can be fun to iteratively walk through, again because structure comes into being simply by referring to it.

For example, suppose we are parsing a list of new animals to add to our taxonomy above, so we want to call a function like:

add(taxonomy,
    'Animalia>Chordata>Mammalia>Cetacea>Balaenopteridae>Balaenoptera>blue whale'.split('>'))

We can implement this simply as:

def add(t, path):
  for node in path:
    t = t[node]

Again we are never assigning to the dictionary, but just by referencing the keys we have created our new structure:

{'Animalia': {'Chordata': {'Mammalia': {'Carnivora': {'Canidae': {'Canis': {'coyote': {},
                                                                            'dog': {}}},
                                                      'Felidae': {'Felis': {'cat': {}},
                                                                  'Panthera': {'lion': {}}}},
                                        'Cetacea': {'Balaenopteridae': {'Balaenoptera': {'blue whale': {}}}}}}},
 'Plantae': {'Solanales': {'Convolvulaceae': {'Ipomoea': {'sweet potato': {}}},
                           'Solanaceae': {'Solanum': {'potato': {},
                                                      'tomato': {}}}}}}

Conclusion

This probably isn't very useful, and it makes for some perplexing code (see add() above).

But if you like Python then I hope this was fun to think about or worthwhile to understand.

There was a good discussion of this gist on Hacker News.

How do you create a tree list in Python?

Given a list of lists, write a Python program to convert the given list of lists into a tree-like dictionary..

Examples:.

Method #1 : Naive Method. This is a Naive approach in which we use two for loops to traverse the list of lists. ... .

Method #2 : Using reduce().

Is a tree a dictionary in Python?

Because Python doesn't implement trees for us, we'll define them using dictionaries. Each node of the tree will be a dictionary that has two keys. The first key is the string "value", which maps to the value in the node.

Can you turn a dictionary into a list Python?

In Python, a dictionary provides method items() which returns an iterable sequence of all elements from the dictionary. The items() method basically converts a dictionary to a list along with that we can also use the list() function to get a list of tuples/pairs.

Can you turn a dictionary into a string?

Use the str() and the literal_eval() Function From the ast Library to Convert a Dictionary to a String and Back in Python. This method can be used if the dictionary's length is not too big. The str() method of Python is used to convert a dictionary to its string representation.

programming python Defaultdict(tree) Python tree Python collapsible tree Extratypes tree Python

Create tree from dictionary python

Learn about trees and how to implement them.

Roots

Examples

JSON-esque

Without assignment

Iteration

Conclusion

How do you create a tree list in Python?

Is a tree a dictionary in Python?

Can you turn a dictionary into a list Python?

Can you turn a dictionary into a string?

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội