trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Работа с иерархическими структурами данных\n",
    "#### Деревья, графы, вот это всё."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    ".\n",
    "└── a\n",
    "    ├── b\n",
    "    │   ├── c\n",
    "    │   └── d\n",
    "    └── e\n",
    "        └── f\n",
    "            └── g\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree = ('a', [\n",
    "    ('b', [\n",
    "        ('c', []),\n",
    "        ('d', [])\n",
    "    ]),\n",
    "    ('e', [\n",
    "        ('f', [\n",
    "            ('g', []),\n",
    "        ]),\n",
    "    ]),\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('a', [('b', [('c', []), ('d', [])]), ('e', [('f', [('g', [])])])])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_flat(tree, dictionary, parent=None):\n",
    "    (node, branches) = tree\n",
    "    children = []\n",
    "    dictionary[node] = (parent, children)\n",
    "    for branch in branches:\n",
    "        name = make_flat(branch, dictionary, parent=node)\n",
    "        children.append(name)\n",
    "    return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "flat = {}\n",
    "make_flat(tree, flat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': (None, ['b', 'e']),\n",
       " 'b': ('a', ['c', 'd']),\n",
       " 'c': ('b', []),\n",
       " 'd': ('b', []),\n",
       " 'e': ('a', ['f']),\n",
       " 'f': ('e', ['g']),\n",
       " 'g': ('f', [])}"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "flat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('e', ['g'])"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "flat['f']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}