Definitions — Python: Trees

The file structure is an example of a tree familiar to everyone who uses a computer. It consists of directories and different types of files:

python-package # Root directory
├── Makefile # File
├── README.md # File
├── __tests__ # Directory
│   └── test_fs.py # File
├── setup.cfg # File
├── pyproject.toml # File
└── .venv # Directory
    └── lib # Directory
        └── python3.6 # Directory
            └── site-packages # Directory
                └── pip # Directory
                    └── __init__.py # File

It's called a tree because of its structure. We build all elements of the file system in a hierarchy. If we're talking about Windows, there's a root directory or disk at the top level, and then there are files and directories, which themselves can contain files and directories.

The key feature of the tree structure is that it is recursive. In other words, a tree consists of subtrees, which in turn consists of subtrees, and so on. This feature defines the main ways of working with trees in the code. They all work recursively. Trees consist of nodes and edges between them. The edges don't exist, we only need them to visualize the connection and describe it if necessary.

Nodes can be of two types:

• Internal nodes with descendants
• Leaf nodes without descendants

In the case of a file system, leaf nodes are files, and internal nodes are directories.

Each node in the tree has a parent. The only exception is the root node — it has no parents, and that's where the tree starts. Internal nodes can have any number of descendants. In addition, you also need to understand the concept of depth, which determines how many steps you need to go along the nodes from the root node to reach the current one. Nodes located at the same depth and having a common parent are called sibling nodes.

Implementation

There's an infinite number of ways we can define trees. The most primitive option is nested tuples:

(('index.html', 'main.py'), 'index.py', ('favicon.ico', 'app.css'))
#                    * root – motorcade
#         /          |         \
#       *         index.py       *
#  /         |               |        \
# index.html main.py   favicon.ico app.css

# A couple more examples of trees with arbitrary data
() # An empty tree
(3, 2, (3, 8), ((8), 3))
(1, None, ((3)), (5, 'string', (False, (3), {"key": "value"})))

In the examples above, the root is the tuple itself, and all its elements are children. We treat the child as an internal node if it is a tuple or a leaf node otherwise. The internal node, in turn, consists of children.

Any tree will consist of two parts:

1. The data stored inside the tree
2. The structure of the tree, which is responsible for the relationships between the data

(('index.html', 'main.py'), 'index.py', ('favicon.ico', 'app.css'))

What is the structure of this tree, and what is the data? The data here are leaf nodes, but the inner tuples are exclusively the structure. They determine what data is and where it is, but they don't contain any data. This way of organizing a tree is unsuitable for storing a file structure. This tree doesn't allow you to set a name or directory.

Let us expand the structure to allow you to add more information. Let us imagine each tree element as a pair, in which the first element is the value stored in the node, and the second element is a list of child nodes. If the second element is missing, then we can assume that the current node is a leaf node:

('app', [ # Root
    ('dist', [ # Internal node
        ('index.html'), # Sheet
        ('main.py') # Sheet
    ]),
    ('index.py'), # Sheet
    ('assets', [ # Internal node
        ('favicon.ico'), # Sheet
        ('app.css'), # Sheet #
    ]),
])

#                  app
#          /        |         \
#        dist    index.py   assets
#       /    \             /     \
# index.html main.py   favicon.ico app.css

This option is more verbose but helps to store data in any node, not just a leaf node. Moreover, it doesn't have to be a string, as in the example above. Changing the data to dictionaries will allow you to add anything there.

The most flexible and convenient way to represent trees is through dictionaries. In such a tree, each node is a dictionary, and lists are used only for storing children:

# Note the separation of structure and data
# It is much more clear here
{
    "value": 5,
    "children": [
        {"value": 10},
        {"value": 100},
        {"value": "nested", "children": []}
    ]
}

By and large, that list and that dictionary can always be considered as trees. It works for any recursive data structure because structures can be elements. Any list can contain a list, just as any dictionary can hold a dictionary.

Recommended materials

1. Fractals