Parent child data structure python

Hi you may give itertree a try (I'm the author).

The package goes in the direction of anytree package but with a bit different focus. The performance on huge trees (>100000 items) is much better and it deals with iterators to have effective filter mechanism.

>>>from itertree import *
>>>root=iTree('root')

>>># add some children:
>>>root.append(iTree('Africa',data={'surface':30200000,'inhabitants':1257000000}))
>>>root.append(iTree('Asia', data={'surface': 44600000, 'inhabitants': 4000000000}))
>>>root.append(iTree('America', data={'surface': 42549000, 'inhabitants': 1009000000}))
>>>root.append(iTree('Australia&Oceania', data={'surface': 8600000, 'inhabitants': 36000000}))
>>>root.append(iTree('Europe', data={'surface': 10523000 , 'inhabitants': 746000000}))
>>># you might use __iadd__ operator for adding too:
>>>root+=iTree('Antarktika', data={'surface': 14000000, 'inhabitants': 1100})

>>># for building next level we select per index:
>>>root[0]+=iTree('Ghana',data={'surface':238537,'inhabitants':30950000})
>>>root[0]+=iTree('Niger', data={'surface': 1267000, 'inhabitants': 23300000})
>>>root[1]+=iTree('China', data={'surface': 9596961, 'inhabitants': 1411780000})
>>>root[1]+=iTree('India', data={'surface': 3287263, 'inhabitants': 1380004000})
>>>root[2]+=iTree('Canada', data={'type': 'country', 'surface': 9984670, 'inhabitants': 38008005})    
>>>root[2]+=iTree('Mexico', data={'surface': 1972550, 'inhabitants': 127600000 })
>>># extend multiple items:
>>>root[3].extend([iTree('Australia', data={'surface': 7688287, 'inhabitants': 25700000 }), iTree('New Zealand', data={'surface': 269652, 'inhabitants': 4900000 })])
>>>root[4]+=iTree('France', data={'surface': 632733, 'inhabitants': 67400000 }))
>>># select parent per TagIdx - remember in itertree you might put items with same tag multiple times:
>>>root[TagIdx('Europe'0)]+=iTree('Finland', data={'surface': 338465, 'inhabitants': 5536146 })

The created tree can be rendered:

>>>root.render()
iTree('root')
     └──iTree('Africa', data=iTData({'surface': 30200000, 'inhabitants': 1257000000}))
         └──iTree('Ghana', data=iTData({'surface': 238537, 'inhabitants': 30950000}))
         └──iTree('Niger', data=iTData({'surface': 1267000, 'inhabitants': 23300000}))
     └──iTree('Asia', data=iTData({'surface': 44600000, 'inhabitants': 4000000000}))
         └──iTree('China', data=iTData({'surface': 9596961,  'inhabitants': 1411780000}))
         └──iTree('India', data=iTData({'surface': 3287263, 'inhabitants': 1380004000}))
     └──iTree('America', data=iTData({'surface': 42549000, 'inhabitants': 1009000000}))
         └──iTree('Canada', data=iTData({'surface': 9984670, 'inhabitants': 38008005}))
         └──iTree('Mexico', data=iTData({'surface': 1972550, 'inhabitants': 127600000}))
     └──iTree('Australia&Oceania', data=iTData({'surface': 8600000, 'inhabitants': 36000000}))
         └──iTree('Australia', data=iTData({'surface': 7688287, 'inhabitants': 25700000}))
         └──iTree('New Zealand', data=iTData({'surface': 269652, 'inhabitants': 4900000}))
     └──iTree('Europe', data=iTData({'surface': 10523000, 'inhabitants': 746000000}))
         └──iTree('France', data=iTData({'surface': 632733, 'inhabitants': 67400000}))
         └──iTree('Finland', data=iTData({'surface': 338465, 'inhabitants': 5536146}))
     └──iTree('Antarktika', data=iTData({'surface': 14000000, 'inhabitants': 1100}))

E.g. Filtering can be done like this:

>>>item_filter = Filter.iTFilterData(data_key='inhabitants', data_value=iTInterval(0, 20000000))
>>>iterator=root.iter_all(item_filter=item_filter)
>>>for i in iterator:
>>>    print(i)
iTree("'New Zealand'", data=iTData({'surface': 269652, 'inhabitants': 4900000}), subtree=[])
iTree("'Finland'", data=iTData({'surface': 338465, 'inhabitants': 5536146}), subtree=[])
iTree("'Antarktika'", data=iTData({'surface': 14000000, 'inhabitants': 1100}), subtree=[])

Topics

  • Nodes
  • Linked Lists
  • Doubly Linked Lists
  • Queues
  • Stacks
  • Hash Maps
  • Recursion
  • Asymptotic Notation
  • Pattern Searching
  • Sorting Algorithms
  • Brute Force Algorithms
  • Trees

  • Tree Traversal: Breadth-First Search and Depth-First Search
  • Divide and Conquer
  • Heaps and Heapsort
  • Graphs and Graph Search
  • Greedy Algorithms

Wide and deep trees

There are two ways to describe the shape of a tree. Trees can be wide, meaning that each node has many children. And trees can be deep, meaning that there are many parent-child connections with few siblings per node. Trees can be both wide and deep at the same time.

Nodes as parents

Trees in computer science are often talked about similarly to family trees. A tree node that references one or more other nodes is called a “parent”.

A tree node can be a “parent” and a “child” simultaneously, because they are not exclusive. For instance, a node ‘b’ can be the child of node ‘a’, while being the parent to nodes ‘d’ and ‘e’. However, a child can only have one parent, while a parent can have multiple children.

Trees are composed of nodes

Trees are a data structure composed of nodes used for storing hierarchical data.

Each tree node typically stores a value and references to its child nodes.

Tree nodes children

A tree node contains a value, and can also include references to one or more additional tree nodes which are known as “children”.

Node root

In a tree data structure, the node that is not the child of any other node is called the root of the tree. A tree can only have one root.

Python TreeNode class

A TreeNode is a data structure that represents one entry of a tree, which is composed of multiple of such nodes.

The topmost node of a tree is called the “root”, and each node (with the exception of the root node) is associated with one parent node. Likewise, each node can have an arbitrary number of child nodes. An implementation of a TreeNode class in Python should have functions to add nodes, remove nodes, and traverse nodes within the tree.

class TreeNode:

def __init__(self, value):

self.value = value

self.children = []

def add_child(self, child_node):

print("Adding " + child_node.value)

self.children.append(child_node)

def remove_child(self, child_node):

print("Removing " + child_node.value + " from " + self.value)

self.children = [child for child in self.children

if child is not child_node]

def traverse(self):

nodes_to_visit = [self]

while len(nodes_to_visit) > 0:

current_node = nodes_to_visit.pop()

print(current_node.value)

nodes_to_visit += current_node.children

Learn More on Codecademy

What are the 4 data structures in Python?

The basic Python data structures in Python include list, set, tuples, and dictionary. Each of the data structures is unique in its own way.

Which data structure has parent and children nodes?

Unlike arrays and linked lists, a tree is a non-linear data structure that connects nodes (or, elements) in a parent-child relationship. That means the data is organized hierarchically. Each parent node has a pointer to a child node and therefore knows about it.

Does Python have a tree data structure?

What is a Tree Data Structure in Python? A Tree is a Data structure in which data items are connected using references in a hierarchical manner. Each Tree consists of a root node from which we can access each element of the tree.

What is parent in data structure?

Basic Terminologies In Tree Data Structure: Parent Node: The node which is a predecessor of a node is called the parent node of that node. {2} is the parent node of {6, 7}. Child Node: The node which is the immediate successor of a node is called the child node of that node. Examples: {6, 7} are the child nodes of {2}.