Trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binärbäume"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Vorbereitung"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dieses notebook benötigt das Networkx package zur Visualisierung. Wenn Sie Annaconda nutzen, können Sie dies mit dem Befehl \n",
    "```\n",
    "conda install -c conda-forge networkx\n",
    "```\n",
    "installieren. In google colab sollte dies bereits zur Verfügung stehen. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Hilfsfunktionen zum Visualisieren von Bäumen\n",
    "\n",
    "Als erstes definieren wir uns die Hilfsfunktionen ```showTree``` mit der wir einen Baum grafisch darstellen können. Sie müssen diesen Code nicht verstehen, müssen die Zelle aber ausführen, damit Ihnen die ``` showTree``` Funktion zur Verfügung steht. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import matplotlib\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "class NodeWithId:\n",
    "    def __init__(self, value, id, left, right):\n",
    "        self.item = value\n",
    "        self.id = id\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "def _augmentTreeWithId( t, n):\n",
    "    if t == None:\n",
    "        return (None, n)\n",
    "    else:        \n",
    "        (leftNode, newN) = _augmentTreeWithId(t.left, n)\n",
    "        (rightNode, rightN) = _augmentTreeWithId(t.right, newN + 1)\n",
    "        return (NodeWithId(t.item, newN + 1, leftNode, rightNode), rightN )\n",
    "\n",
    "def _buildTreeGraph(g, t, parentNode, depth):\n",
    "    if t == None:\n",
    "        return\n",
    "    _buildTreeGraph(g, t.left, t, depth + 1)\n",
    "    g.add_node(t.id, pos=(t.id, -depth), label=str(t.item))\n",
    "    if (parentNode != None):\n",
    "        g.add_edge(t.id, parentNode.id)\n",
    "    _buildTreeGraph(g, t.right, t, depth + 1)\n",
    "\n",
    "def showTree(t):\n",
    "    g = nx.Graph()\n",
    "    (tt, _) = _augmentTreeWithId(t, 0)\n",
    "    _buildTreeGraph(g, tt, None, 0)\n",
    "    pos=nx.get_node_attributes(g,'pos')\n",
    "    labels = nx.get_node_attributes(g, 'label')\n",
    "    \n",
    "    nx.draw_networkx_nodes(g, pos, node_size=1000, node_color='#00b4d9')\n",
    "    nx.draw_networkx_edges(g, pos)\n",
    "    nx.draw_networkx_labels(g, pos, labels)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Erstellen einfacher Bäume"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir führen als erstes die grundlegende Datenstruktur ein. Wir folgen der rekursiven Definition. Ein Baum ist eine Wurzel, die ein Datenelement (hier das Feld item) sowie eine Referenz auf einen linken und einen rechten Unterbaum speichert."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryTree:\n",
    "    def __init__(self, item, left, right):\n",
    "        self.item = item\n",
    "        self.left = left\n",
    "        self.right = right"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Den leeren Baum definieren wir als den Wert ```None```."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir können uns nun bereits einen ersten Baum definieren."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "b = BinaryTree(\"root\", \n",
    "               BinaryTree(\"left\", None, None), \n",
    "               BinaryTree(\"right\", None, None)\n",
    "              )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dieser Baum besteht aus der Wurzel, sowie jeweils einem linken und rechten Teilbaum. Der linke und der rechte Teilbaum ist jeweils ein Blatt.  Mit der ```showTree``` funktion können wir den Baum nun visualisieren. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/MnkTPAAAACXBIWXMAAAsTAAALEwEAmpwYAAAjWElEQVR4nO3de0BUdd4G8OfMoA54ARRETc1cbXXNFLkaqbxuWVbrmgwXwbsgKeJdI827ad5TvCKCF0AuM5m2rrblm+b6al622vJWK9uKF0RRUMARGM77x2S5CggyM7+5PJ9/KgbOeSR9+Pmbc75HkmUZRERkHgrRAYiI7AlLl4jIjFi6RERmxNIlIjIjli4RkRk5VPeim5ub3K5dOzNFISKyDadPn74py7J7Za9VW7rt2rXDqVOnTJOKiMhGSZL0n6pe4/YCEZEZVbvSJbIUBWV6HLutw8lCHQ7nl+CqrhylMlBfAlqpHNCnmRN8nFXo6aqCSz2l6LhEVWLpkkU7VaDDyuxb+OR6MeorJJToK1D+yE2U54vL8NWte3BSKlBaIWOgR0NMbd8U3i4qMaGJqsHSJYt0+V4Zhnybi5OFOuj0MioA6CqqvmW9XAbulFcAADKvFWFvXjF8nFVI6d4CrR3rmSk10ZNxT5csiizLSMopRKfDP+Po7Xso+aVwa6MCQIlextHb99Dp8M9IyikEZ4yQpWDpksWQZRmTz95A7Jk8FOvlx7YRaqtcBor1MmLP5GHy2RssXrIILF2yCA8KNzGnECV645ZjiV5GYk4hppy9YdTjEj0Nli5ZhOTLd7AlpxDFRi7cB4r1MhJyCpGUU2iS4xPVFEuXhLt8rwwTzuQZfYX7qBK9jIln8nBFV2bS8xBVh6VLwg35Nhf3q7kywZh0FTIivsk1y7mIKsPSJaFOFhhueKjrm2Y1VS4DJwt1OFWgM88JiR7B0iWhVmbfgs7E2wqP0ullrMq+bdZzEj3A0iVhCsr02HO9uNbX4dZVBYDd14tQUKY385mJWLok0LHbOtRXSKY5+Oo4YOfqKl9uoJBw/Da3GMj8WLokzMlCHUrKq1nn6stNdu5ifQVOFrJ0yfxYuiTM4fwSPFaro/oCmgRg/J+AoO7A1weBcW8Cod5A3FAg5+Jvn5tz0fCxUG/D53x90PDxAxnAoU8B7VZA7QnMf+exc5fLwKH8ElP90oiqxIE3JMxVXRUr2cP7gLkJwN1CYHoY8P56oKsv8Mk2YME7wIZ9gCQZ/v3VIGDhVuDsaWDROGC1Fng9FDj3DeDmAQydXOX5r1V1fiIT4kqXhCmt6qKFPw0F3FsaVq4+fQDPAMChHjBoNHBfZyjU898B90oA9RigXn2gW0/A538MhV1D9zmKgQTgSpeEqV/Ve2juLQ3/vJUHNG/128cVCsNr+dcBpQPg3sLwsQeatzK8VkMNTPQeHlF1uNIlYVqpqviZL/3Shk2bA3lXf/u4LAM3rgHNPAyv3cgFKh56I+7Baw8foxotqzo/kQmxdEmYPs2c4FBdN/bqD5w8DHx7DCgvA3YnGbYSOnsCv38RUDkC2kTDa//8Gjjxv0DvNwxf69IMyL1c5aEdJCCwmZNxf0FENcDSJWF8nFVwUlbzW7B1e2DqcmDzQiDcHzjxJTBnk6F469UHZm8ETn9leG3jfGDyMqDN7wxf+6oauPQvw5UNi8Y9duiGSgV8nPk4HzI/qbrBzt7e3jIfwU6mUlCmR8svsqt9DI+pqBQSrr3Sng+xJJOQJOm0LMvelb3GlS4J41JPiT97NDT7b0IFgLc9GrFwSQiWLgk1rX1TqJTmvYxApZQw9XeuZj0n0QMsXRLK20UFH2dV9W+oGZGDZNhL9uJ+LgnC0iXhUrq3QANTDb55hEohIdWzhVnORVQZli4J19qxHtZ2aQ4nE28zOCklrOnSHM+o6pn0PETVYemSRRjZugmi2jijoYmKt6FSwpg2zhjVxtkkxyeqKZYuWQRJkrD6D+548doFKErvG/XYTkoJUW2cseoP7kY9LtHTYOmSxTh48CCyZ0Zh+e8ao5FSqvObaw4SoLivw1uX/4HVXZpDqsGtwUSmxtIli3D58mUMHToUaampmPJiO5zr0w4Bro5wUkq1/k2qgGF1G+DqiKNdG+PQrAk4cuSIKWIT1RpLl4QrLS1FSEgIYmNj0bdvXwCGN9cO9WyDw/5tENqyMVQKCc4OiipXvw4S4OyggEohIbRlYxz2b4NDPdvAv+NzSE5OxuDBg5Gby0evk3i8DZiEmzRpEi5evIg9e/ZAoah8HVBQpsfx24bHtR/KL8E1XTnuy4bxjC1VDghs5gQfZxX8XVWV3mk2Z84cHDlyBJ9//jkcHDhdjEyrutuAWbokVGZmJuLi4nD69Gm4upruLjG9Xo/+/fvDy8sLS5YsMdl5iADOXiALdf78ecTExECj0Zi0cAFAqVQiNTUVqamp2Lt3r0nPRVQdli4JUVRUhKCgICxevBg9evQwyznd3d2RkZGByMhIXLx48clfQGQCLF0yO1mWER0dDR8fH0RGRpr13D179sT7778PtVqNe/fumfXcRABLlwTYuHEjfvjhB2zYsEHItbOxsbF4/vnnERsba/ZzE7F0yaxOnDiBuXPnQqPRwMlJzONyJElCYmIijh49iuTkZCEZyH7x2hkym/z8fISEhGDz5s3o2LGj0CyNGzeGRqNBYGAgPD090b17d6F5yH5wpUtmUVFRgSFDhkCtVmPQoEGi4wAAunTpgjVr1kCtVqOgoEB0HLITLF0yi0WLFqGoqMjirpENDw/Ha6+9hpEjR6K6a9aJjIWlSyb3t7/9DZs2bUJGRgbq1bO8WbarVq3C1atXsWLFCtFRyA5wT5dMKicnB8OGDUN6ejpatWolOk6lGjRogKysLPj6+sLPzw+9e/cWHYlsGFe6ZDKlpaUIDg7G5MmTERgYKDpOtdq2bYvt27dj8ODBuHbtmug4ZMNYumQy06ZNg4eHB2bMmCE6So289tpriIqKQlhYGMrLy0XHIRvF0iWTSE9Px759+7B9+3arGh4+e/ZsqFQqzJo1S3QUslEsXTK6s2fPIjY2FhqNBi4uLqLj1MqDwTjp6en45JNPRMchG8TSJaMqKiqCWq3Ghx9+CE9PT9FxnoqbmxsyMzMxZswY/Otf/xIdh2wMS5eMRpZlREVFwd/fH6NHjxYdp078/PwwZ84cDsYho2PpktGsX78e586dw/r160VHMYqYmBh07twZMTExoqOQDWHpklEcP34cCxYsgEajgaOjo+g4RiFJErZs2YLjx49j69atouOQjeDNEVRnN2/eRGhoKBISEtChQwfRcYyqUaNG0Gq16N27N3r06GG1+9RkObjSpTrR6/WIiIhAaGgoBg4cKDqOSXTu3Bnx8fEcjENGwdKlOlm4cCF0Oh0WL14sOopJhYWF4c0338Tw4cNRUVEhOg5ZMZYuPbUDBw5gy5YtyMjIsIvHmq9YsQJ5eXlYvny56ChkxWz/TwqZxKVLlzBixAhkZmaiRYsWouOYRf369ZGZmQkfHx/4+flZ/DwJskxc6VKt3b9/H8HBwZg6dardTeRq06YNdu7cifDwcFy9elV0HLJCLF2qtSlTpqBVq1aYNm2a6ChCvPrqq3jnnXcQGhqKsrIy0XHIyrB0qVbS0tLw2WefITk52aoG2Rjb+++/j0aNGuG9994THYWsDEuXauzMmTOYOHEitFqt1Q2yMTaFQoGUlBRoNBp8/PHHouOQFWHpUo3cvXsXQUFBWLZsGbp16yY6jkVo1qwZMjMzER0djZ9++kl0HLISLF16IlmWERkZiZdffhkjR44UHcei+Pr6Yv78+QgKCkJJSYnoOGQFWLr0RPHx8fjxxx8RHx8vOopFGjt2LLp27Ypx48bxicL0RCxdqtaxY8ewaNEiaLVamxlkY2ySJCEhIQEnT55EYmKi6Dhk4XhzBFXpxo0bCA0NRWJiItq3by86jkVr2LAhtFotevXqBS8vL/To0UN0JLJQXOlSpfR6PcLDwxEREYEBAwaIjmMVOnXqhA0bNkCtVuP27dui45CFYulSpebPnw+9Xo+FCxeKjmJVgoODMWDAAAwbNoyDcahSLF16zP79+5GUlIRdu3bZxSAbY1u2bBny8/OxdOlS0VHIAvFPFP2Xn3/+GSNGjIBGo4GHh4foOFbp0cE4ffv2FR2JLAhXuvSrB4NsZsyYgV69eomOY9Vat26NnTt3IiIiAleuXBEdhywIS5d+NWnSJLRt2xZTpkwRHcUmvPLKK4iJieFgHPovLF0CAKSkpODgwYNISkqy60E2xjZz5kw4Ozvj3XffFR2FLARLl/DDDz9g8uTJ0Gg0cHZ2Fh3HpigUCuzcuRO7d++GRqMRHYcsAEvXzt25cwdBQUFYsWIFXnzxRdFxbFLTpk2RlZWFsWPH4scffxQdhwRj6doxWZYxevRo9OnTB8OHDxcdx6Z5e3tj4cKFCAoKQnFxseg4JBBL146tWbMG2dnZWLt2regodiE6Ohqenp4YO3YsB+PYMZaunTp69CiWLFkCjUYDlUolOo5dkCQJmzZtwjfffIOEhATRcUgQ3hxhh/Ly8hAWFoakpCQ899xzouPYFScnJ2i1WgQEBMDLywve3t6iI5GZcaVrZx4Mshk2bBjefPNN0XHs0vPPP4+NGzciODgYt27dEh2HzIyla2fmzp0LWZaxYMEC0VHsmlqtxttvv42hQ4dyMI6dYenakX379mH79u3YtWsXlEql6Dh2b+nSpSgsLMSSJUtERyEz4p6unfj3v/+NUaNG4eOPP0bz5s1FxyEA9erVQ0ZGBry9veHn54dXXnlFdCQyA6507YBOp4NarUZcXBwCAgJEx6GHPPPMM0hNTcXQoUNx+fJl0XHIDFi6dmDixIlo3749Jk2aJDoKVaJv376IjY1FSEgISktLRcchE2Pp2rgdO3bg0KFD2Lp1KwfZWLC4uDg0a9YMM2bMEB2FTIyla8O+//57TJ06FRqNBk2aNBEdh6qhUCiwY8cO7N27F5mZmaLjkAmxdG1UYWEhgoKCsHr1anTt2lV0HKoBV1dXZGVlISYmBufPnxcdh0yEpWuDZFnGqFGj8Mc//hFDhgwRHYdqwcvLC4sXL4ZareZgHBvF0rVBq1evxqVLl/DRRx+JjkJPITIyEt7e3oiOjuZgHBvE0rUxf//737F06VJkZWWhQYMGouPQU5AkCRs2bMD333+PTZs2iY5DRsabI2zI9evXERYWhuTkZLRr1050HKoDJycnaDQaBAQEwNvbGz4+PqIjkZFwpWsjysvLMXjwYIwcORJvvPGG6DhkBB07dsSmTZsQHByM/Px80XHISFi6NmL27NlQKpWYN2+e6ChkRIMGDYJarcaQIUM4GMdGsHRtwN69e5GSkoK0tDQOsrFBS5YsQVFRERYtWiQ6ChkB93StXHZ2NiIjI7Fnzx64u7uLjkMm8PBgHH9/f/Tr1090JKoDrnSt2INBNrNmzULPnj1FxyETatWqFdLS0jBs2DDk5OSIjkN1wNK1YrGxsejYsSMmTJggOgqZQWBgICZNmoTg4GAOxrFiLF0rtW3bNhw5cgSJiYkcZGNHZsyYAQ8PD0ybNk10FHpKLF0r9N1332H69OnQarVo3Lix6DhkRgqFAtu3b8e+ffuQnp4uOg49BZaulSksLIRarcaaNWvQpUsX0XFIABcXF2g0GsTGxuLcuXOi41AtsXStiCzLGDFiBPr164fw8HDRcUggT09PfPjhhwgKCkJRUZHoOFQLLF0rsnLlSly9ehWrVq0SHYUswOjRo+Hv748xY8ZwMI4VYelaia+++gorVqxAZmYmB9nQr9avX4+zZ89iw4YNoqNQDfHmCCuQm5uLwYMHY9u2bXj22WdFxyEL4ujoCI1Gg5deeunXpwqTZeNK18KVl5cjNDQUkZGReP3110XHIQvUoUMHJCQkICQkBDdv3hQdh56ApWvhZs2aBZVKhTlz5oiOQhZs4MCBCA0NRUREBPR6veg4VA2WrgXbs2cPdu3ahdTUVA6yoSdavHgxdDodFi5cKDoKVYN7uhbq4sWLiIqKwt69e+Hm5iY6DlkBBwcHpKen/zoYh9tRlokrXQt07949BAUFYc6cOfD39xcdh6xIy5YtsWvXLowYMQKXLl0SHYcqwdK1QOPHj0fnzp0RExMjOgpZod69e2Pq1KkIDg7G/fv3RcehR7B0LUxSUhKOHTuGLVu2cJANPbVp06ahVatWmDp1qugo9AiWrgX59ttv8e6770Kr1aJRo0ai45AVkyQJycnJOHDgANLS0kTHoYewdC1EQUEB1Go14uPj0blzZ9FxyAa4uLhAq9Vi4sSJOHv2rOg49AuWrgV4MMimf//+CAsLEx2HbEi3bt2wbNkyBAUF4e7du6LjEFi6FmH58uXIzc3FypUrRUchGzRy5EgEBAQgKiqKg3EsAEtXsEOHDmHVqlXIzMxE/fr1RcchGxUfH48LFy4gPj5edBS7x5sjBLp27RrCw8OxY8cOtG3bVnQcsmGOjo7QarXw9/eHj48PH2QqEFe6gpSVlSE0NBTR0dF8pDaZRfv27ZGYmIjQ0FDcuHFDdBy7xdIVZObMmXBycsLs2bNFRyE7MmDAAISHhyM8PJyDcQRh6Qqwe/duZGVlISUlBQoF/xeQeS1atAjl5eWYP3++6Ch2iX/izeynn35CdHQ0MjMzOciGhHgwGCcpKQn79+8XHcfusHTNqKSkBGq1GvPmzYOvr6/oOGTHPDw8fh2M85///Ed0HLvC0jUTWZYRExODF154AWPHjhUdhwi9evXCjBkzoFarORjHjFi6ZrJ161acOHECCQkJHGRDFmPKlClo27YtJk+eLDqK3WDpmsE//vEPvPfee9BqtWjYsKHoOES/kiQJSUlJ+OKLL5Camio6jl1g6ZrY7du3ERwcjPXr16NTp06i4xA9xtnZGRqNBpMmTcKZM2dEx7F5LF0TqqiowPDhw/HWW28hJCREdByiKr344otYsWIFBg0ahDt37oiOY9NYuia0dOlS3Lx5E8uXLxcdheiJhg8fjj59+mD06NEcjGNCLF0T+fLLL7F27VoOsiGrsnbtWmRnZ2PNmjWio9gsDrwxgStXriAiIgI7duxA69atRcchqjGVSgWNRgM/Pz/4+PggICBAdCSbw5WukT0YZDNu3Di8+uqrouMQ1dpzzz2HpKQkhIWFIS8vT3Qcm8PSNbK4uDg4Oztj5syZoqMQPbW33noLw4YN42AcE2DpGpFWq8XHH3+MnTt3cpANWb0FCxZAlmXMnTtXdBSbwmYwkh9//BFjx45FVlYWmjZtKjoOUZ0plUrs2rUL27dvx759+0THsRksXSN4MMhmwYIF8Pb2Fh2HyGiaN2+O9PR0jBo1Cj///LPoODaBpVtHsixj7Nix6NatG6Kjo0XHITK6gIAAxMXFQa1WQ6fTiY5j9Vi6dbRlyxacPn0amzZt4iAbslmTJk3Cc889h0mTJomOYvVYunVw+vRpzJo1i4NsyOZJkoStW7fiyy+/xM6dO0XHsWos3ad069YtqNVqbNy4Eb///e9FxyEyuSZNmkCj0WDKlCn4/vvvRcexWizdp1BRUYGhQ4di4MCBUKvVouMQmU3Xrl2xatUqBAUFobCwUHQcq8TSfQpLlixBQUEBli1bJjoKkdkNHToUffv2xahRozgY5ymwdGvp4MGDWLduHTIzM1GvXj3RcYiE+Oijj3Dp0iWsXr1adBSrw4E3tXDlyhUMGTIEqampeOaZZ0THIRJGpVIhKysLfn5+8PX1xcsvvyw6ktXgSreGysrKEBISgtjYWPTt21d0HCLh2rVrh+TkZISFheH69eui41gNlm4NzZgxA02bNkVcXJzoKEQW44033sDIkSMxePBglJeXi45jFVi6NZCVlYU9e/Zgx44dHGRD9Ih58+ZBqVRizpw5oqNYBTbIE1y4cAHjxo1DVlYWXF1dRcchsjhKpRJpaWlISUnBp59+KjqOxWPpVqO4uBhBQUH44IMP4OXlJToOkcVyd3dHRkYGIiMjkZ2dLTqORWPpVkGWZbzzzjvw8vJCVFSU6DhEFq9nz56YOXMmgoODORinGizdKmzevBnfffcdNm7cyEE2RDU0YcIEdOjQARMmTBAdxWKxdCtx8uRJzJ49GxqNBk5OTqLjEFkNSZKQmJiIr776Ctu2bRMdxyLx5ohH5OfnIzg4GJs3b8bzzz8vOg6R1WncuDG0Wi0CAwPh6emJbt26iY5kUbjSfciDQTZqtRqDBg0SHYfIanXp0gUfffQR1Go1B+M8gqX7kA8++AB3797FkiVLREchsnoRERHo168fRowYwcE4D2Hp/uLzzz/Hxo0bkZGRwUE2REayatUqXL16FStXrhQdxWJwTxdATk4Ohg0bhl27dqFVq1ai4xDZjAYNGiAzM/PXwTi9e/cWHUk4u1/plpaWIiQkBBMnTkRgYKDoOEQ259lnn8W2bdswePBg5Obmio4jnN2X7vTp0+Hu7o4ZM2aIjkJks15//XVERkYiLCzM7gfj2HXpZmRk4C9/+Qu2b9/OQTZEJjZnzhw0aNAA77//vugoQtlt05w/fx7jx4+HRqPhIBsiM1AqlUhNTUVaWhr27t0rOo4wdlm6RUVFCAoKwpIlS+Dp6Sk6DpHdcHNzQ2ZmJiIjI3Hx4kXRcYSwu9KVZRljxoyBr68vRo8eLToOkd3x9/fH7NmzoVarce/ePdFxzM7uSnfDhg04c+YM1q9fz0E2RIKMHz8enTp1wvjx40VHMTu7Kt2vv/4a8+fPh1ar5SAbIoEkScKWLVtw7NgxJCUliY5jVnZzc8TNmzcREhKChIQEdOjQQXQcIrvXqFEjaLVa9O7dGz169ED37t1FRzILu1jp6vV6DBkyBKGhoRg4cKDoOET0i86dOyM+Ph5qtRoFBQWi45iFXZTuokWLcO/ePSxevFh0FCJ6RFhYGPr37283g3FsvnQ/++wzJCQkID09HQ4OdrObQmRVVq5cidzcXCxfvlx0FJOz6Ra6dOkShg8fjoyMDLRs2VJ0HCKqQv369ZGZmQlfX1/4+fmhT58+oiOZjM2udB8MspkyZYpN/w8kshVt27bFjh07EB4ejmvXromOYzI2W7pTp05FixYtMH36dNFRiKiG+vXrhzFjxtj0YBybLN309HTs378f27Zt4w0QRFZm9uzZcHR0xMyZM0VHMQmbK92zZ88iNjYWGo0GLi4uouMQUS0pFAqkpKQgIyMDu3fvFh3H6GyqdO/evYugoCAsXbrUbi60JrJFbm5uyMrKQnR0NH766SfRcYzKZkpXlmVERUXhpZdewqhRo0THIaI68vX1xdy5c6FWq1FSUiI6jtHYTOmuW7cOFy5cwLp160RHISIjGTduHF544QXExMTYzI0TNlG6x48fx8KFC6HVauHo6Cg6DhEZiSRJSEhIwIkTJ7B161bRcYzC6m+OuHHjBkJCQpCYmIj27duLjkNERtawYUNotVr06tULPXr0QI8ePURHqhOrXunq9XpEREQgPDwcAwYMEB2HiEykU6dOWL9+PYKDg3H79m3RcepE6Eq3oEyPY7d1OFmow+H8ElzVlaNUBupLQCuVA/o0c4KPswo9XVVwqad87OsXLFiAsrIyLFq0SEB6IjKnkJAQHD16FMOHD8cnn3xS6cNk69op5iBVtznt7e0tnzp1yugnPVWgw8rsW/jkejHqKySU6CtQXkkMBwlwUipQWiFjoEdDTG3fFN4uKgDAgQMHEBkZiVOnTqFFixZGz0hElqe0tBSBgYEYMGAA4uLifv24MTrFmCRJOi3Lsnelr5mzdC/fK8OQb3NxslAHnV5GRS2+VgFApZTg46zCh+56DHzZH1lZWejVq5fR8hGR5bt8+TJ8fHyQlpaGjv4vG6VTUrq3QGvHekbLKLx0ZVlG8uU7mHAmD/cr5Ep/AtWUgwRU3Nch6OY5ZESG8DZfIjv0t799juCEXSgfHYdSGXXulAYKCWu7NMfI1k2M0inVla7J30iTZRmTz95A7Jk8FOvrVriA4ZtbUV+FfW16YPLZGzZz7R4R1Ywsy/jrM91wb9g0lFTUrXABw9cX62XEnskzS6eYtHQfFG5iTiFK9Mb9hZToZSTmFGLK2RtGPS4RWa6HO6VMadzrAMzVKSYt3eTLd7AlpxDFRi7cB4r1MhJyCpGUU2iS4xORZbGFTjFZ6V6+V4YJZ/KMvsJ9VIlexsQzebiiKzPpeYhILFvpFJOV7pBvc3G/wjz7rboKGRHf5JrlXEQkhq10iklK92SB4eLkum5w11S5DJws1OFUgc48JyQis7KlTjFJ6a7MvgVdVX8FGNUX+Pb/nnyQ//scGNEHUHsCF88+8dN1ehmrsq379kAiqlyVnTLuTeCfX9fsIDXtnl+YqlOMXroFZXrsuV5cq4uUK5W0FHhnNqD5BmjUBHjr94C+6mcmVQDYfb0IBWX6up6ZiCxItZ2yYR/wol/dT/LPr4Hhvf/rQ6bqFKOX7rHbOtRXGOGGhbyrQNuOtfqSBgoJx29zi4HIllTZKdUswozFFJ1i9IE3Jwt1KCmvwTq3ogLQJgKfZQLFd4Fu/kDMfEDlBAz2Ayr0QOyfAVe33765oT6Gfy5MAjp7PnbIYn0FThbq8Hrzhkb8FRGRSP/VKaP6Am+EAYc+BS7/G3BuCkz+EOj+EnBfB6yfC3z9v4beeGUQ8OlOYPtXvx0s+xyQuMSwqPPqBUxeauiaeVFAWalhOxMANh8AmnmYpFOMvtI9nF+CGv38+XQHcPwL4MMUYMcRoJEzsHEBUK++YUsBAOL3AIm/fA4AZJw0vFZJ4QKGze9D+bbzWA8iqqRTDu8D5iYAGaeAh2+Q2LUOyLsCbP0CWJQMHNr7+MGO7AfmJwJbDwL/vgB88bFhoTdvC9C0uaFfNN8AzTwAmKZTjF66V3U1XPLvzwCGTgbcWhiKNnw8cPSzOv+V4VpNz09EVuGxTvnTUMC9JdDgkelgR/YDwdGGBZxbC+BPwx4/2IChhkJt7AL4/o9h5fsExu4Uo28vlNb0ko4bV4EPYoCHZ2IqFMDtfMDN46nPf5+jGIhsymOd4t6y8k+8lfffr7lVMvLV1f23f2/gaPiaJzB2pxi9dOvX9D00txbAxMXAH7ye/Lm1mPrTgEPHiGzKY51SVR80dQdu5gJtOxj++2Ytbm6opmOM3SlG315opaphj/cfDOz4yLAHAwCFtwx7vJVp0tSwCs7NeeJhW9b0/ERkFWrcKS/3B7I2A0WFwM3rwF9San4Sl2bA3QLDm/qPMHanGL10+zRzgkNNfjIMGAb49QVmjwKCPYGpIcCFf1b+uSpHIOQdYPpgINQbOP9tpZ/mIAGBzZyeOjsRWZ4ad8rgGMPfoEf/EXh/BBDwmuH9oppo8zug95tA5CuGjsm/DsA0nWL0Ieb784oR9s013KnJZWNG5uygQLpnS14yRmRDnrpT/poGfPXX365+egpP2ylmHWLe01WFUjMNpXjU/QoZ/q7Gf94REYlT4065lQecPW24B+ByNrA7Gej5Sp3ObYpOMfoGqEs9Jf7s0RBZ14rqfitwLSgAvO3RSNgTPonINGrcKeVlwLq5wPXLQMPGhu2CN8Kf+rym6hSTvOs0rX1TfJpXbPK5lw9TKSVM/Z2r2c5HROZTo05p/gyw4S9GO6epOsUkU8a8XVTwcVbVbPPbCBwkwMdZBS9nbi0Q2SJb6hSTDTFP6d4CDYwx+KYGVAoJqZ6VXAhNRDbDVjrFZKXb2rEe1nZpDielab9JTkoJa7o0xzMq4z2znogsj610ikkfTDmydRNEtXFGQxN9kxoqJYxp44xRbZxNcnwisiy20CkmLV1JkrD6D+6IbONs9J9OTkoJUW2cseoP7k/+ZCKyCbbQKSYtXeC3b1J8l+ZopJTqvBHuIAGNlBLiuzTH6i7NIdViLgMRWT9r7xSTly5g+CaNauOMc33aIcDVEU5KqdYnVsDwkyjA1RHnA9txS4HIjllzp5h1Okxrx3o41LMNThXosCr7NnZfL0IDhYRifUWlT/l0kICGSgXuV8h426MRprR3hbcLLwsjIgNr7BSjz16ojYIyPY7fNjxa+VB+Ca7pynFfNoxSa6lyQGAzJ/g4q+DvquKdZkT0RJbSKdXNXhBaukREtsisA2+IiKhq1a50JUm6AeA/5otDRGQTnpVludJrz6otXSIiMi5uLxARmRFLl4jIjFi6RERmxNIlIjIjli4RkRn9Pyd+4CmHC3PAAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "showTree(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Es ist einfach, sich aus einzelnen Teilbäumen einen komplexeren Baum zusammenzubauen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "leftSubtree = BinaryTree(\"l\", \n",
    "               BinaryTree(\"ll\", None, None), \n",
    "               BinaryTree(\"lr\", None, None))\n",
    "rightSubtree = BinaryTree(\"r\", \n",
    "               BinaryTree(\"rl\", None, None), \n",
    "               BinaryTree(\"rr\", None, None))\n",
    "tree = BinaryTree(\"root\", leftSubtree, rightSubtree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3dd1gU1/oH8O/sUlZQFxZFUTGWUNQbLyokYkAEG2JXorHFjsFYnqgRsYKKSowa4y9WotGYmNg1EisCgi2QaIrlYq4lKApIM4JL2Z3fH0SvGkCW3Z0zu/N+nuc+994Ac76bd8/LcHbmDMfzPAghhAhDxjoAIYRICTVdQggREDVdQggREDVdQggREDVdQggRkEVVX6xXrx7frFkzgaIQQoh5+Omnnx7yPF+/oq9V2XSbNWuG1NRU46QiRAf5pRqcz1MjpUCNxJwiZKjLUMIDVhzQSGEBPwcbeCkV8LZXwM5SzjoukTiO4+5U9rUqmy4hrKXmq7HqZi4OZhbCSsahSKNF2UuXll8vLMWZ3CewkctQouUxoIEtZrZQwdNOwSY0IVWgpktE6e6TUoy8/AApBWqoNTy0ANTaym/kKeOBR2VaAMDu+49xOKsQXkoFdno0RJNalgKlJuTV6IM0Iio8z2NregHcE2/jbN4TFP3dcHWhBVCk4XE27wncE29ja3oB6M5LIhbUdIlo8DyPD69mY+qVLBRq+H8sI+iqjAcKNTymXsnCh1ezqfESUaCmS0ThacONSS9AkcawzbFIwyMmvQAzrmYb9LiE1AQ1XSIK2+4+wpb0AhQauOE+VajhsTm9AFvTC4xyfEKqi5ouYe7uk1JMu5Jl8DPclxVpeEy/koV76lKjjkNIVajpEuZGXn6A4iquTDAktZbHiEsPBBmLkIpQ0yVMpeSX3/Cg74dm1VXGAykFaqTmq4UZkJCXUNMlTK26mQu1kZcVXqbW8Fh9M0/QMQl5ipouYSa/VINDmYU6X4dbLaf2A7OHVfglLYADmY+RX6oxxsiEVImaLmHmfJ4aVjKu8m/QlBltbGsZhwt5tMRAhEe3ARNmUgrUKCp76Tx3XAAQ9C6Q8D1w9xbw6T5g41Lg1jXAoQEwegbwVtfy7y38C9i4BPjpDGBdC+j5DjDkfeDeLeDzReVNO7gdIJcD3724cVOhRouUAjUCHW0FerWElKMzXcJMYk4RKjyXTYwFFm0GvrkARE0B2r8N7DwHTJoPfDILuHuz/Ps2LgGK/gJiTgErvgJOHwJO7QOcWwIfRALuHsDeS/9ouED5B2oJOUVGfX2EVISaLmEmQ13J8kHfUUB9J+DmdeBJERAcAlhaAf/2Brz8y5uyRgMk/QCMngnY1AYaNAEGjgVOH672+PcrG58QI6KmS5gpqeyihfpO5f+dmwXUbwjInnubOjYCcjKBR3lAWWn5/3/5a9VUTFsxEAao6RJmrCr7DI37+wsqRyD7AaB9bt03+3752m5de8DCEsjK+OfXnj9GFaxf/S2EGBw1XcJMI8UrPsd1awsoagH7YsrPan+9CPx4GugcVP7hmE8gsGMNUPQYyLoHHNwG+Pcr/1k7B+BhJlBaUunhnV41PiFGQE2XMOPnYAOLqs42La2ABRvKr04Y3hHYEAl8+HH5B2UA8P6C8qY8oRswezjg1wfoPrj8a207Ak1fB0b5AMPf+sehLTigi4ON4V8UIa/AVbXHqKenJ0/PSCPGcjSrEO9euv/siQ9CUlrI8G07J7pkjBgFx3E/8TzvWdHX6EyXMONtr0CJQBvdvKxYy6OjPT1DjQiPmi5hxs5Sjv4NbAV/E8oADGxQm54aTJigpkuYmtVCBYVc2MsIFHIOM1vaCzomIU9R0yVMedop4KVUVP2BmgFZcICXUoEOSlpaIGxQ0yXM7fRoCOuqNr4xIIWMw9ftGgoyFiEVoaZLmGtkLcdbl06AKzHurl82MmBtG0c0VlgadRxCqkJNlzBVUlKCkSNHovTYbkx6zR62RlrftSgrQZ2zR9GvFj0fjbBFTZcwU1hYiP79+6OwsBDHjx3D+nZNMMFZCRsDN14bOYcPXnfEWG0mfH19kZ6ebtDjE6ILug+SMJGbm4s+ffrA1dUVMTExsLAofyuuaV0fbetaY/qVLKi1vF7PTrPgytdw17ZxxDhnJbBsGeo5OMDHxwfHjx+Hu7u7gV4NIdVHZ7pEcBkZGfDz80PHjh2xdevWZw0XADiOwzhnJa75NcPb9rVgI+d0fpPKUH52+7Z9LVzv0qy84f5t5syZiIyMhL+/P+huS8ICNV0iqD/++AM+Pj4YPnw4Vq1aBZms4rdgk1qWSPB2RmJHZwx1qgOFjIPSQlbppWUWXPmtvQoZh6FOdZDY0RkJ3s4Vfmg2ZswYbNy4EUFBQYiPjzfkyyPklWh5gQjm8uXLCAoKQkREBEJCQqr1M552CnzT3gn5pRpcyCt/XHtCThHuq8tQzJdvz+iksEAXBxt4KRXoaK+o1p1m/fv3h1KpxJAhQ7Bx40YMGjRI35dHSLVQ0yWCSEpKwuDBg/H555/jnXfe0fnn7SzlCHS0RaCjLRa4OBgkU5cuXXDs2DH07t0beXl5GD9+vEGOS0hVqOkSozty5AjGjh2Lb775Bt27d2cd5wXt27dHYmIievTogZycHMyePZt1JGLmaE2XGNVXX32FCRMm4MiRI6JruE+5uroiOTkZ27dvx+zZs1HVdqeE6IuaLjGatWvXYt68eTh9+jTeeuufG4mLSZMmTXDmzBmcOXMGEydORFkZPbSSGAc1XWJwPM9jwYIFWL9+PZKSktC6dWvWkarFwcEBp06dwp9//okhQ4ZArTbubclEmqjpEoPSaDSYPHkyfvjhByQlJeG1115jHUkntWvXxvfffw8LCwsEBQXh0aNHrCMRM0NNlxhMSUkJRowYgevXryM+Ph6Ojo6sI9WItbU1du3aBVdXVwQEBCA7O5t1JGJGqOkSgygsLETfvn1RXFyMo0ePom7duqwj6UUul2PDhg0IDAyEr68v/vzzT9aRiJmgpkv0lpubi27duqFx48bYs2cPFArz2CCc4zgsXboUkyZNgo+PD65du8Y6EjED1HSJXu7du4fOnTvDx8cHX3zxxQv7KJiLDz/8EEuXLoW/vz9SUlJYxyEmjpouqbEbN27Ax8cHo0aNwsqVK8Fxwj7rTEjvvfceNm/ejKCgIMTFxbGOQ0wYNV1SI5cuXYKfnx/mzp2LsLAw1nEE0a9fP+zduxfDhg3Dvn37WMchJsr8/hYkRnfmzBkEBwdjw4YNGDx4MOs4gvLz88Px48fRu3dv5ObmYuLEiawjERNDTZfo5PDhw5gwYQJ27dqFrl27so7DRLt27Z7t15Cbm4vZs2eb9dIKMSxaXiDVtmPHDoSEhCA2NlayDfcpFxcXJCcn46uvvqL9GohOqOmSalmzZg3mz5+P+Ph4eHl5sY4jCo0bN8aZM2eQnJyM8ePH034NpFqo6ZIq8TyPefPmYdOmTUhOTkarVq1YRxIVlUqFU6dOISMjA8HBwbRfA3klarqkUhqNBqGhoTh+/DiSkpLQtGlT1pFEydbWFocPH4ZCoUCvXr1ovwZSJWq6pELFxcUYNmwY0tLSEB8fj/r167OOJGpWVlb4+uuv0apVK/j7+yMrK4t1JCJS1HTJPzx+/Bh9+/ZFWVkZfvjhB9SpU4d1JJMgl8vx+eefo3fv3vD19cWdO3dYRyIiRE2XvCAnJwddu3ZF06ZNsXv3brPZR0EoHMdh8eLFmDx5Mnx9fXH16lXWkYjIUNMlz9y9exe+vr7o0qULtmzZYpb7KAhl+vTpWLZsGQICAnDx4kXWcYiIUNMlAIC0tDT4+PhgzJgxiI6Opov9DWDkyJGIiYlB3759cfLkSdZxiEhQ0yX4+eef4efnhwULFtDTcA2sT58+2LdvH0aMGIE9e/awjkNEgP5+lLiEhAQMGTIEmzZtwsCBA1nHMUu+vr44ceLEs/0aJk2axDoSYYiaroQdPHgQEydOxHfffYeAgADWccyah4fHs/0acnJyEB4eTks4EkXLCxK1bds2hIaG4ujRo9RwBfL6668jOTkZu3btwsyZM6HVallHIgxQ05WgVatWISIiAvHx8fD09GQdR1IaNWqEM2fO4MKFCxg3bhzt1yBB1HQlhOd5hIeHIyYmBsnJyXB3d2cdSZLs7e1x8uRJZGZmYvDgwXjy5AnrSERA1HQlQqPRICQkBHFxcUhKSoKzszPrSJJma2uLQ4cOwdbWFoGBgSgoKGAdiQiEmq4EFBcXY+jQobh16xbi4uJQr1491pEIyvdr2LlzJ9544w106dIFmZmZrCMRAVDTNXN//fUXevfuDZ7nERsbS/soiIxMJsO6devQv39/+Pr64vbt26wjESOjpmvGHj58iK5du6J58+bYvXs3rK2tWUciFeA4DhEREZg6dSp8fX1x5coV1pGIEVHTNVPp6enw9fVF165dsXnzZsjlctaRyCtMnToVK1asQEBAAC5cuMA6DjESarpm6Pr16/Dx8cH48eOxfPlyugjfhIwYMQLbtm1D3759cfz4cdZxiBFQ0zUzqamp8Pf3R0REBGbNmsU6DqmBoKAgHDhwAKNGjcJ3333HOg4xMLoN2IzEx8dj6NCh2Lx5MwYMGMA6DtGDj48PTp06hV69eiE3NxehoaGsIxEDoaZrJg4cOICQkBDs3r0b/v7+rOMQA2jbti3OnDnzbL+GefPm0VKRGaDlBTOwdetWTJ48GceOHaOGa2ZatmyJ5ORk7N69GzNmzKD9GswANV0Tt3LlSixevBgJCQno0KED6zjECJycnJCYmIiUlBSMGTMGpaWlrCMRPVDTNVE8zyMsLAzbtm1DcnIy3NzcWEciRmRvb48TJ04gJycHgwYNov0aTBg1XRNUVlaGiRMnIiEhAUlJSWjSpAnrSEQANjY2OHjwIJRKJXr27In8/HzWkUgNUNM1MWq1GkOGDMGdO3cQFxcHBwcH1pGIgCwtLbFjxw54eHigS5cuePDgAetIREfUdE3Io0ePEBQUBLlcjiNHjqB27dqsIxEGZDIZ1q5di0GDBsHHxwe3bt1iHYnogJquicjOzkZAQABcXFzw7bff0j4KEsdxHBYuXIgPP/wQvr6++O2331hHItVETdcE/Pnnn/D19UXPnj2xceNG2keBPPPBBx9g5cqV6NatG86dO8c6DqkGaroid+3aNfj4+CAkJARRUVF0cTz5h2HDhmH79u3o378/jh07xjoOeQVquiKWkpICf39/LFmyBDNmzGAdh4hYYGAgDh06hNGjR2PXrl2s45Aq0G3AIhUXF4d3330XX3zxBfr168c6DjEBnTp1erZfQ15eHiZPnsw6EqkANV0R2rdvH0JDQ7F37174+fmxjkNMyBtvvPFsv4aHDx9iwYIFtCQlMrS8IDJbtmzB1KlTcfz4cWq4pEZatGiB5ORk7N+/H9OnT6f9GkSGmq5I8DyP6OhoLFu2DImJiWjXrh3rSMSENWzYEAkJCbh06RLee+892q9BRKjpigDP85g9ezZ27NiB5ORkuLi4sI5EzICdnR2OHz+O/Px8DBgwAEVFRawjEVDTZa6srAzjx49HUlISkpKS0LhxY9aRiBmxsbHBgQMHoFKp0KNHD9qvQQSo6TKkVqsRHByMe/fu4dSpU1CpVKwjETNkaWmJ7du3w9PTE35+frh//z7rSJJGTZeRR48eoVevXrC2tsb3339P+ygQo5LJZFizZg3eeecd+Pj44ObNm6wjSRY1XQaysrLg7+8Pd3d3fPPNN7CysmIdiUgAx3GYP38+Zs2aBV9fX/z666+sI0kSNV2B3blzB76+vggKCsL69etpHwUiuNDQUKxevRrdu3fH2bNnWceRHGq6Arp69Sp8fX0RGhqKJUuW0EXrhJmhQ4dix44dGDBgAH744QfWcSSF7kirRH6pBufz1EgpUCMxpwgZ6jKU8IAVBzRSWMDPwQZeSgW87RWws3z12erFixfRv39/rFy5EqNGjRLgFRBStZ49e+Lw4cMYMGAA1qxZg+HDh1fr5ww9N6SGmu5LUvPVWHUzFwczC2El41Ck0aKMf/F7rheW4kzuE9jIZSjR8hjQwBYzW6jgaaeo8JgnT57E8OHDsXXrVvTt21eAV0FI9Xh7e+P06dMIDAxEbm4upkyZUun3GmNuSBHH83ylX/T09ORTU1MFjMPO3SelGHn5AVIK1FBreOhy46QMgELOwUupwE6PhmhSy/LZ1/bu3YvJkydj79696Ny5s8FzE2IIt2/fRvfu3TFixAgsWrTohaUvY80Nc8Zx3E88z3tW9DXJr+nyPI+t6QVwT7yNs3lPUKTjmwoAtACKNDzO5j2Be+JtbE0vAM/z2Lx5M6ZNm4YTJ05QwyWi1qxZMyQnJ+PQoUOYNm0atFqtUeeGlEn6TJfneXx4NRtb0gtQpDHcG8FGzsHjQRoyFk/FyRMn8Prrrxvs2IQYU0FBAfr164dGjRuj3pxV2Jrx2OBzY6KzEmta1zfrD5LpTLcCTxtujIEbLlD+m/18XWd0+zaOGi4xKUqlEkePHsXFNwKw4eZDo8yNmPQCzLiabdDjmhLJNt1tdx9hS3oBCg38pnqKt1bgm9wybE0vMMrxCTGWb3NKkenhB42lcR5+WqjhsTm9QLJzQ5JN9+6TUky7kmXw3+IvK9LwmH4lC/fUtK0eMQ3P5oaW5oaxSLLpjrz8AMVGflM9pdbyGHHpgSBjEaIvmhvGJ7mmm5JfflH3y9cXGksZD6QUqJGarxZmQEJqiOaGMCTXdFfdzIW6JssK4wKAy+dqNKZaw2P1zbwa/SwhQqnx3NCDFOeGpJpufqkGhzILdb7WUF9aAAcyHyO/VCPwyIRUD80N4Uiq6Z7PU8NKxubaQGsZhwt50vozipgOg80NTZnOPyK1uSGppptSoEZRGZsnoxZqtEgpkM4bi5gWvebGuABg72ZgSl9gsIfOjVdqc0NSTTcxpwi6/x42jDIeSMihBwMScdJ7biTGAos2A9+lAnLd9tGS2tyQ1C5jGWpWLbfcfcbjE1IZvedG31FAfaca/7iU5oakznRLGO+zUSztfT6IiOk9N/RouIC05oakmq4V4/01rM13fw9i4vSeG3puXiOluSGppttIwXY1xYnx+IRUhuaGcCTVdP0cbGDB6DeqBQd0cbBhMzghr0BzQzjS+fUCwEupgI1chkc1uTRm62m9xraVy+ClpEeWEHGiuSEcSZ3petsrUCLQZh4vK9by6GgvnTcWMS00N4QjqaZrZylH/wa2gr9oGYCBDWrTk1GJaNHcEI6kmi4AzGqhgkIu7OKVQs5hZkt7QcckRFc0N4QhuabraaeAl1Ih2IcGFlz5elkHCa1ZEdNEc0MYkmu6ALDToyGsBdr4RiHj8HW7hoKMRYi+aG4YnySbbpNalvisjSNsjPynlI2cw9o2jmissDTqOIQYCs0N45Nk0wWAsU3qYqKzErZGenPZyjmEOCsxzllplOMTYiw0N4xLsk2X4zisaV0fE5yVBv+tbiPnMNFZidWt6xv0uIQIgeaGcUm26QL/e3Ota+MIGw5AmX5PJrXggNpyDuvaOGJNG0dwet6PTggrz8+N2nIOcl6/fajlvJbmxt8k3XSB8jfXOGcl/L5dgebqfNjIOZ3/pcgAoPgJOtTicL1LM8n+2UTMy9O5camjEyxu/AYF+BrNDWtoYfXfK/jt7SY0N0BNFwBw4cIF/BZ/Elf6tUdiR2cMdaoDhYyD0kJW6eUzFhygtJBBIeMw1KkOJv73DFrGREjygwFi3g59sQk9E3Yi6e3XajQ3kt9uhrePbMTRnV8KmlusOJ6v/NY/T09PPjU1VcA4wuN5Hn5+fhgzZgzGjRv37J/nl2pwIa/8kdQJOUW4ry5DMV++BZ2TwgJdHGzgpVSgo70CdpZyPH78GK6urjhy5Ajat2/P8BURYjh5eXlwc3NDQkICWrduDUD3uQEAP//8M3r37o0bN26gdu3aLF+SIDiO+4nnec8Kvyb1pnvkyBHMmTMHv/zyC+Ry/W5F3LBhAw4cOIATJ04YKB0hbM2ZMwc5OTnYsmWL3scaMWIE3NzcsHDhQgMkE7eqmi54nq/0Px06dODNWVlZGd+mTRv+8OHDBjleSUkJ7+Liwp84ccIgxyOEpT///JNXqVT83bt3DXK8mzdv8g4ODnxmZqZBjidmAFL5SvqqpNd0t2/fDpVKhT59+hjkeJaWlli2bBnCwsKg1bJ56jAhhrJo0SJMmjQJjRs3NsjxmjdvjpEjR2Lx4sUGOZ6pkuzyQlFREdzc3LBnzx507NjRYMfleR7e3t6YOnUqRowYYbDjEiKk33//HV27dkVaWhqUSsNdcfDw4UO4u7vj/PnzcHFxMdhxxaaq5QXJnumuW7cOb731lkEbLlB+mU10dDTmz5+P4uJigx6bEKGEh4cjPDzcoA0XAOrVq4cZM2Zg/vz5Bj2uKZFk083JycEnn3yCqKgooxzfz88Pbdq0wYYNG4xyfEKM6cyZM/j9998RGhpqlONPnz4dycnJSElJMcrxxU6STXfZsmUIDg6Gm5ub0cZYsWIFli9fjoKCAqONQYih8TyP2bNnY+nSpbC2tjbKGLa2toiIiMDs2bNR1fKmuZJc0719+za+/PJLLFq0yKjj/Otf/0Lv3r0RHR1t1HEIMaR9+/ahpKQEw4YNM+o4Y8eOxYMHD3D06FGjjiNGkmu6CxYswJQpU9CwofH38YyMjMSmTZtw7949o49FiL5KS0sxd+5cREdHQyYzbmuwsLDAihUrEBYWBo1GY9SxxEZSTffy5cs4efIkZs2aJch4zs7OmDBhAiIiIgQZjxB9xMTE4LXXXkP37t0FGa9fv36oW7cudu7cKch4YiGpS8YCAwPRp08fTJkyRbAxK7qNkhCxefz4MVxcXBAbGyvobeznzp3Du+++i7S0NCgU5vPYHrpkDEBcXBz++OMPhISECDquvb09wsLCEB4eLui4hOhi1apVCAgIEHzfkE6dOqFDhw5Yt26doOOyJIkzXa1WCy8vL4SFhWHIkCGCj69Wq+Hm5oavv/4aPj4+go9PSFUyMzPRunVrpKamonnz5oKPf/36dfj6+uI///kPVCqV4OMbg+TPdHfv3g2ZTIbg4GAm4ysUCixZskSyl8gQcVuyZAlGjRrFpOECgLu7OwYOHIgVK1YwGV9wlW3KwJvJhjfFxcV8ixYt+NOnTzPNUVZWxrdt25bfv38/0xyEPC8tLY13cHDgs7Ozmea4d+8er1Kp+Dt37jDNYSiQ8oY3GzduhJubG/z9/ZnmkMvliI6ORnh4OMrKyphmIeSpefPmYcaMGahXrx7THI0aNUJoaKg0tn3kzXhN99GjR3BxccHJkyfRtm1b1nHA8zy6deuGIUOGYNKkSazjEIn78ccfMXDgQNy4cQM2Njas44huvupDsmu6K1euRGBgoGgK+HQznMjISBQWFrKOQySM//t234iICFE0XACoW7cu5s6da/ZX+pht071//z7Wr1+PJUuWsI7yAk9PT3Tu3Blr1qxhHYVI2NGjR5GZmYmxY8eyjvKC999/H9euXUNCQgLrKEZjtk03IiIC48aNQ9OmTVlH+YeoqCh8+umnyM7OZh2FSJBGo0FYWBhWrFgBCwsL1nFeYG1tjaioKLO+0scsm+7169exf/9+0f6Z0rJlSwwfPlx0Z+FEGr766isolUr069ePdZQKDR06FFqtFnv27GEdxSjM8oO0QYMGwdvbGx999BHrKJXKzs5Gq1atcPHiRbRs2ZJ1HCIRT548gZubG7799lt06tSJdZxKxcXFYdKkSbh27RosLS1Zx9GZpD5IO3fuHFJTUwXdX6Em6tevj+nTp0t6B30ivP/7v/9Dhw4dRN1wAaBr165o2bIlNm/ezDqKwZnVmS7P8/D19cWECRMwZswY1nFeqbCwEC4uLjh8+DA8PSt+WjMhhpKbmws3NzckJSXB3d2ddZxXunz5Mnr16oW0tDTUqVOHdRydSOZM9/Dhw3j06BFGjRrFOkq12NraYtGiRQgLCzPbDw2IeCxfvhyDBg0yiYYLAB4eHujWrRs++eQT1lEMq7Jb1XgTuw24tLSUb9WqFR8bG8s6ik5KS0t5V1dX/tixY6yjEDN2584dXqVS8RkZGayj6OTWrVu8SqXi79+/zzqKTiCF24C//PJLODo6olevXqyj6MTCwgLLly9HWFgYtFot6zjETC1cuBChoaFwcnJiHUUnzZo1w+jRo7F48WLWUQzGLNZ0i4qK4Orqiv379+PNN99kHUdnPM/j7bffRmhoqMksjRDT8euvv6J79+64ceMG6tatyzqOznJycuDu7o6zZ8/C1dWVdZxqMfs13U8//RSdOnUyyYYLlN8e/PHHH2PBggVQq9Ws4xAzM2fOHMybN88kGy4AODg4YObMmZg7dy7rKAZh8k334cOHWL16NaKiolhH0YuPjw/+/e9/Y/369ayjEDMSHx+P69ev4/3332cdRS/Tp0/HhQsXcOHCBdZR9GbyTTcqKgpDhw6Fi4sL6yh6W758OVasWIH8/HzWUYgZ4HkeYWFhiIqKgpWVFes4eqlVqxYiIyPN4kofk266t27dwo4dO8xmD87WrVujX79+0tlBnxjVnj17oNVqMXToUNZRDGL06NF4+PAhYmNjWUfRi0k33fnz52PatGlo0KAB6ygGExkZiS1btiA9PZ11FGLCSkpKMHfuXERHR0MmM+lp/oyFhQVWrFiBOXPmQKPRsI5TYyZbjZ9//hmnT5/GzJkzWUcxqMaNG2PSpElYtGgR6yjEhG3evBmvv/46unbtyjqKQfXp0wcqlQrbt29nHaXGTPaSsR49emDAgAGYPHky6ygGl5+fD1dXV5w+fRr/+te/WMchJuavv/6Ci4sLjh07Bg8PD9ZxDO78+fMYMmQI0tLSUKtWLdZxKmR2l4ydPHkSt2/fxsSJE1lHMQo7OzuEh4eLdmtKIm6ffPIJunfvbpYNFwC8vb3x5ptv4rPPPmMdpWYqu1WNF+ltwBqNhm/Xrh2/Z88e1lGMSq1W882aNeMTExNZRyEm5P79+7xKpeJv3brFOopRXb9+na9Xrx7/8OFD1lEqBKiwj18AAAvNSURBVHO6DXjXrl2wtLTE4MGDWUcxKmtrayxdutSsd9AnhhcZGYkxY8agWbNmrKMYlZubG4KDg7Fs2TLWUXRXWTfmRXim+/TsLyEhgXUUQWg0Gt7Dw4Pfu3cv6yjEBPznP//hHRwcRHv2Z2gZGRm8SqXib9++zTrKP8BcznQ3bNiANm3awM/Pj3UUQchkMkRHRyM8PBylpaWs4xCRmzt3LmbNmgUHBwfWUQTh5OSEDz74AAsWLGAdRScm03QLCgqe3bElJT169MBrr72GmJgY1lGIiF24cAEXL17E9OnTWUcR1EcffYQTJ07gl19+YR2l2kym6UZHR6N3796SvIQqOjoaixcvxuPHj1lHISLE8zxmz56NyMhI0V5CZSx16tTB/PnzERYWxjpKtZlE07137x42bdqEyMhI1lGYaN++PQICArB69WrWUYgIxcbGIjc3F6NHj2YdhYmQkBD88ccfiIuLYx2lWkyi6UZERGDChAlwdnZmHYWZpUuX4rPPPkNWVhbrKERENBoN5syZg+XLl0Mul7OOw4SVlRWioqJM5kEAom+6V69exaFDhzBnzhzWUZhq3rw5Ro4caVY76BP9bd++HSqVCn369GEdhal33nkHHMdh9+7drKO8kuhvA+7fvz86d+5sdnss1MTDhw/h7u6O8+fPm8VWlkQ/RUVFcHNzw549e9CxY0fWcZiLj4/HhAkTcO3aNeZbWZrsbcDJycm4fPkyPvjgA9ZRRKFevXqYMWMG5s+fzzoKEYF169bhrbfeoob7N39/f7i5uWHTpk2so1RJtGe6/N/PDXv//ffx3nvvMckgRoWFhXB1dcXBgwfh5eXFOg5h5Olzw5KTk+Hm5sY6jmj8+uuv6NGjB9LS0pg+nsgkz3QPHjyIwsJCjBgxgnUUUbG1tUVERATdHixxy5YtQ3BwMDXcl7Rt2xY9e/bEypUrWUepXGW3qvEMbwMuLS3l3dzc+KNHjzIZX+xKS0t5d3d3PjY2lnUUwsCtW7d4lUrF379/n3UUUbpz5w6vUqn4jIwMZhlgarcBb926FY0bN0bPnj1ZRxElc9lBn9TMwoULMWXKFDRs2JB1FFFq2rQpxo0bJ9rr+kW3pvt0zfLQoUPw9KxwSYSg/C8UHx8fhISESPaieCn65Zdf0LNnT9y4cQN16tRhHUe0cnNz4ebmxmzN26TWdNesWQNfX19quK/AcRxWrlyJBQsWQK1Ws45DBBIWFob58+dTw30FlUqFjz76SJQPAhBV083Ozsann36KqKgo1lFMQqdOndChQwesW7eOdRQigLi4OPzxxx8ICQlhHcUkTJ06FampqTh37hzrKC8QVdNdsmQJhg8fjpYtW7KOYjKWL1+Ojz/+GLm5uayjECPSarWYPXs2li1bxvzCf1NRq1YtLF68WHRX+oim6f73v//FN998Qxf+68jd3R0DBw6U3JaXUrN7927IZDIEBwezjmJSRo0ahYKCAnz//fesozwjmg/Shg0bhtatW5vchsRikJGRgTfeeAOXLl1C06ZNWcchBlZSUoJWrVohJiYG/v7+rOOYnNjYWHz00Uf49ddfYWFhIciYov8gLTU1FYmJiZgxYwbrKCapUaNGCA0NxcKFC1lHIUawceNGuLm5UcOtoaCgIDg6OuLLL79kHQWACM50eZ5Ht27dMGTIEEyaNMmoY5mzR48ewcXFBSdPnkTbtm1ZxyEGQnU1jB9//BGDBg1CWloabGxsjD5eVWe6Bj/Xzi/V4HyeGikFaiTmFCFDXYYSHrDigEYKC/g52MBLqYC3vQJ2lnKcOHECd+/exbhx4wwdRVLq1q2LuXPnIjw8HLGxsc/+ua71IMalaz1WrlyJwMBAarh6evPNN+Ht7Y21a9c+u4yM1dww2Jluar4aq27m4mBmIaxkHIo0WpRVcGgLDrCRy1Ci5dG/gS1+XjAFK8aPxKBBg2r6GsjfiouL0apVK2zduhW1PTrqXI8BDWwxs4UKnnYK4cObuZrMj55KOeKnjcJv+3fRWr0B3LhxA97e3vg29Xd8kas16tyo6kxX76Z790kpRl5+gJQCNdQaHrrs287xWnClpfBtaIedHg3RpJalDj9NKvJ/3+7F3BxLaFq21rkeMgAKOQcvpYLqYSB6zQ+tFnJeg7fr16V6GMDdJ6V4a08SsuwaQCu3NOrcMMoHaTzPY2t6AdwTb+Ns3hMU6fiGAgCek0FrZY2zeU/gnngbW9MLRHU9nSl5Wo85dv/GX01calQPLYAiDU/1MACDzA+ZDGVyS6qHnp6vRVa9JijTseEChp0bNWq6PM/jw6vZmHolC4UavsJTc12U8UChhsfUK1n48Go2vbF09HI9oOdlMVQP/dD8EA8x1kLnpvv0RcSkF6BIY9jiF2l4xKQXYMbVbIMe15xRPcSF6iEeYq2Fzk13291H2JJeUH5GZQSFGh6b0wuwNb3AKMc3N1QPcaF6iIdYa6FT0737pBTTrmQZ/LfGy4o0PKZfycI9dalRxzF1VA9xoXqIh5hroVPTHXn5AYq1wqwnqbU8Rlx6IMhYporqIS5UD/EQcy2q3XRT8ssvItZ3Ibq6ynggpUCN1HzaK7YiVA9xoXqIh9hrUe2mu+pmLtRGPlV/mVrDY/XNPEHHNBVUD3GheoiH2GtRraabX6rBocxCna9tw7gA4PI54Ot1wCezdP1paAEcyHyM/FJ6DtjzalSPp7XQA9WjYjWeH0/VsDZUj3/SuxY1pEstqtV0z+epYSXj9M1VI9YyDhfy6E+o51E9xIXqIR6mUItqNd2UAjWKyoT+3VGuUKNFSgG9qZ5n0HpoynT6dqrHP+lVDx3//b+M6vEivefGy/XQoT7VrUW1mm5iThH0e2vUXBkPJOQUMRpdnPSqx9frgGXTypd73mkPnDqg049TPf5J53qMCwD2bgam9AUGe+jVeKkeL6rR3Hi5HqM716g+1a1FtZpuhppVyy13n/H4YqN3PS7GAW8HAt+lAl366vzjVI8X1ageibHAos3lNZDrd9s21eN/ajw3Xq5HDetTnVpU62gljG/1LqZbzV+gdz3cPQDvbuX/21r3bRypHi+qUT36jgLqOxlkfKrH/9R4brxcjxrWpzq1qNaZrhWbdelnrBmPLzZ616NeQ71+nOrxohrVw0ANF6B6PK/Gc+PletSwPtWpRbWabiOFMA9zq4wT4/HFRu96cPrNUqrHi2pUDz1r8Dyqx//UeG68XI8a1qc6tahW0/VzsIEFo9+mFhzQxcH4zzQyJVQPcaF6iIcp1KJaTddLqYCNnM2Dg23lMngp6fExz6N6iAvVQzxMoRbVelxPfqkGTqduQi3QBhLPU8g43O/Wgh6a+Byqh7hQPcRDLLXQ+3E9dpZy9G9gW/Nn+9SQDMDABrXpDfUSqoe4UD3EwxRqUe1ss1qooJALu1iikHOY2dJe0DFNBdVDXKge4iH2WlS76XraKeClVAi2SG3Bla/PdKD1qgpRPcSF6iEeYq+FTmfhOz0awlqgzSQUMg5ft9PvelJzR/UQF6qHeIi5Fjo13Sa1LPFZG0fYGPnU3UbOYW0bRzRWVP1seamjeogL1UM8xFwLndebxzapi4nOStga6cXYyjmEOCsxzllplOObG6qHuFA9xEOstdC56XIchzWt62OCs9Lgv0Vs5BwmOiuxunV9gx7XnFE9xIXqIR5irUWNrqx4+mLWtXFEbTmn94K1BQfUlnNY18YRa9o4gjPgLZJSQPUQF6qHeIixFtW6OaIqd5+UYuTlB0gpUEOt4XV6TIYM5ZdaeCkV+LpdQ1qjMgCqh7hQPcRDyFpUdXOE3k33qdR8NVbfzMOBzMewlnEo1GgrfBqnBVd+u1yxlsfABrUxo4U9PO3oshdDo3qIC9VDPISohSBN96n8Ug0u5JU/Ajkhpwj31WUo5su3PHNSWKCLgw28lAp0tFfQnTQCoHqIC9VDPIxZixo3XY7jsgHc0Wk0Qgghr/E8X+GnbFU2XUIIIYbFZg80QgiRKGq6hBAiIGq6hBAiIGq6hBAiIGq6hBAioP8HQFHcfUnlsZMAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "showTree(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Traversierungsarten"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Genau wie eine Liste, kann ein Baum als Sequenz von Elementen interpretiert werden. Die Reihenfolge dieser Sequenz ist aber nicht eindeutig, sondern hängt davon ab, wie der Baum traversiert wird. \n",
    "\n",
    "Wir unterscheiden zwischen *depth-first* Traversierung und *breadth-first* Traversierung. Bei der depth-first Traversierung unterscheiden wir zusätzlich zwischen *preorder*, *postorder* und *inorder* Traversierung. Es gibt jedoch viele weitere Möglichkeiten einen Baum zu traversieren."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Inorder Traversierung"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bei der Inorder Traversierung wird zuerst der linke Teilbaum traversiert, danach wird der Wurzelknoten des jeweiligen Unterbaums verarbeitet, und zum Schluss wird der rechte Teilbaum traversiert. Die Implementation ist ganz einfach: Wir folgen einfach der Definition der Datenstruktur. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def printTreeInorder(t):\n",
    "    if (t == None):\n",
    "        return\n",
    "    else:\n",
    "        printTreeInorder(t.left)\n",
    "        print(t.item)\n",
    "        printTreeInorder(t.right)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn wir die Funktion aufrufen, können wir nachverfolgen, in welcher Reihenfolge die Knoten besucht werden. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ll\n",
      "l\n",
      "lr\n",
      "root\n",
      "rl\n",
      "r\n",
      "rr\n"
     ]
    }
   ],
   "source": [
    "printTreeInorder(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Preorder Traversierung"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bei der Preorder Traversierung, wird zuerst das Element an der Wurzel verarbeitet, bevor wir den linken und den rechten Teilbaum traversieren."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def printTreePreorder(t):\n",
    "    if (t == None):\n",
    "        return\n",
    "    else:\n",
    "        print(t.item)\n",
    "        printTreePreorder(t.left)        \n",
    "        printTreePreorder(t.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "root\n",
      "l\n",
      "ll\n",
      "lr\n",
      "r\n",
      "rl\n",
      "rr\n"
     ]
    }
   ],
   "source": [
    "printTreePreorder(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Postorder Traversierung"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Analog dazu verhält sich auch die Postorder Traversierung. Hier wird  die Wurzel einfach zuletzt (also nach dem linken und rechten Teilbaum) verarbeitet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def printTreePostorder(t):\n",
    "    if (t == None):\n",
    "        return\n",
    "    else:\n",
    "        printTreePostorder(t.left)        \n",
    "        printTreePostorder(t.right)\n",
    "        print(t.item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ll\n",
      "lr\n",
      "l\n",
      "rl\n",
      "rr\n",
      "r\n",
      "root\n"
     ]
    }
   ],
   "source": [
    "printTreePostorder(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Breadth-first Traversierung \n",
    "\n",
    "Bei der preorder, inorder und postorder Traversierung, gehen wir immer zuerst in die Tiefe. Diese Traversierungsarten sind besonders einfach zu implementieren, da sie der rekursiven Struktur der Datenstruktur folgen. \n",
    "Manchmal wollen wir aber trotzdem die Elemente Ebene für Ebene bearbeiten. Die sogenannte Breadth-first Traversierung ist etwas schwieriger zu implementieren. Die einfachste Variante ist, alle Knoten einer Ebene in einer Queue zu speichern und dann jeweils den ersten Knoten der Queue zu verarbeiten. Für jeden Knoten werden dann die Kinder wieder in die Queue eingefügt. Wir iterieren dann solange, bis alle Elemente in der Queue abgearbeitet sind. Die Implementation ist also hier nicht rekursiv, sondern interativ. \n",
    "\n",
    "Als Queue nutzen wir hier einfachheitshalber  eine Python List. Die Operation ```pop(0)``` entspricht dann der dequeue Operation und append der enqueue Operation. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def printTreeBreadthFirst(tree):\n",
    "    if tree == None:\n",
    "        return    \n",
    "    queue = [tree]\n",
    "    \n",
    "    while len(queue) > 0:  \n",
    "        \n",
    "        currentNode = queue.pop(0)        \n",
    "        if currentNode.left != None:\n",
    "            queue.append(currentNode.left)\n",
    "        if currentNode.right != None:\n",
    "            queue.append(currentNode.right)\n",
    "        print(currentNode.item)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "root\n",
      "l\n",
      "r\n",
      "ll\n",
      "lr\n",
      "rl\n",
      "rr\n"
     ]
    }
   ],
   "source": [
    "printTreeBreadthFirst(tree)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.4"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}