{"id":20900,"date":"2021-05-28T13:54:20","date_gmt":"2021-05-28T11:54:20","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=20900"},"modified":"2025-06-12T09:12:07","modified_gmt":"2025-06-12T07:12:07","slug":"binaerbaum-java","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaerbaum-java\/","title":{"rendered":"Bin\u00e4rbaum (mit Java-Code)"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Zwei der wichtigsten Themen in der Informatik sind das Sortieren und Suchen von Datens\u00e4tzen. Eine Datenstruktur, die f\u00fcr beides h\u00e4ufig zum Einsatz kommt, ist der Bin\u00e4rbaum im Allgemeinen und seine Spezialf\u00e4lle <a href=\"\/de\/algorithmen\/binaerer-suchbaum-java\/\">bin\u00e4rer Suchbaum<\/a> und <a href=\"\/de\/algorithmen\/heapsort\/#Was_ist_ein_Heap\">bin\u00e4rer Heap<\/a>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In diesem Artikel erf\u00e4hrst du:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Was ist ein Bin\u00e4rbaum?<\/li>\n\n\n\n<li>Welche Arten von Bin\u00e4rb\u00e4umen gibt es?<\/li>\n\n\n\n<li>Wie implementiert man einen Bin\u00e4rbaum in Java?<\/li>\n\n\n\n<li>Welche Operationen stellen Bin\u00e4rb\u00e4ume bereit?<\/li>\n\n\n\n<li>Was bedeuten <em>pre-order<\/em>, <em>in-order<\/em>, <em>post-order<\/em> und <em>level-order<\/em> bei der Traversierung von Bin\u00e4rb\u00e4umen?<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Den Quellcode zum Artikel findest du in diesem&nbsp;<a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\" target=\"_blank\" rel=\"noopener\">GitHub-Repository<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"binaerbaum-definiton\">Bin\u00e4rbaum Definiton<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Ein Bin\u00e4rbaum ist eine Baum-Datenstruktur, in der jeder Knoten maximal zwei Kindknoten hat. Die Kindknoten werden als <em>linkes<\/em> und <em>rechtes<\/em> Kind bezeichnet.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"binaerbaum-beispiel\">Bin\u00e4rbaum Beispiel<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Ein Bin\u00e4rbaum sieht beispielsweise wie folgt aus:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"350\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-beispiel-v2-600x350.png\" alt=\"Bin\u00e4rbaum-Beispiel\" class=\"wp-image-21070\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-beispiel-v2-600x350.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-beispiel-v2-224x131.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-beispiel-v2-336x196.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-beispiel-v2-504x294.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-beispiel-v2-672x392.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-beispiel-v2-400x233.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-beispiel-v2-800x467.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-beispiel-v2-944x551.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-beispiel-v2.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Bin\u00e4rbaum-Beispiel<\/figcaption><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"binaerbaum-terminologie\">Bin\u00e4rbaum Terminologie<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Die folgenden Begriffe sollte man als Entwickler kennen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Ein <strong>Knoten<\/strong> (englisch \"node\") ist eine Struktur, die einen Wert enth\u00e4lt, sowie optionale Referenzen auf einen linken und einen rechten <strong>Kindknoten<\/strong> (oder nur <strong>Kind<\/strong>, englisch \"child node\" oder \"child\").<\/li>\n\n\n\n<li>Die Verbindung zwischen zwei Knoten bezeichnet man als <strong>Kante<\/strong> (englisch \"edge\").<\/li>\n\n\n\n<li>Der oberste Knoten wird als <strong>Wurzel<\/strong> oder <strong>Wurzelknoten<\/strong> bezeichnet (englisch \"root\" oder \"root node\").<\/li>\n\n\n\n<li>Ein Knoten, der Kinder hat, ist ein <strong>innerer Knoten<\/strong> (englisch \"inner node\", kurz \"inode\") und gleichzeitig der <strong>Elternknoten<\/strong> (englisch \"parent\" oder \"parent node\") des oder der Kinder.<\/li>\n\n\n\n<li>Ein Knoten ohne Kinder wird <strong>\u00e4u\u00dferer Knoten<\/strong> (englisch \"outer node\") oder auch <strong>Blatt<\/strong> (englisch \"leaf\" oder \"leaf node\") genannt.<\/li>\n\n\n\n<li>Ein Knoten mit nur einem Kind ist ein <strong>Halbblatt<\/strong> (englisch \"half node\"). Achtung: diesen Begriff gibt es \u2013 im Gegensatz zu allen anderen \u2013 ausschlie\u00dflich bei Bin\u00e4rb\u00e4umen, nicht bei B\u00e4umen im Allgemeinen.<\/li>\n\n\n\n<li>Die Anzahl der Kindknoten bezeichnet man auch als <strong>Ausgangsgrad<\/strong> eines Knotens (englisch \"degree\").<\/li>\n\n\n\n<li>Die <strong>Tiefe<\/strong> (englisch \"depth\") eines Knotens gibt an, wie viele Ebenen der Knoten von der Wurzel entfernt ist. Die Wurzel hat also eine Tiefe von 0, die Kinder der Wurzel eine Tiefe von 1, usw.<\/li>\n\n\n\n<li>Die <strong>H\u00f6he<\/strong> (englisch \"height\") des Bin\u00e4rbaums ist die maximale Tiefe aller Knoten.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Die folgende Grafik zeigt dieselbe Bin\u00e4rbaum-Datenstruktur wie zuvor, beschriftet mit Knotentypen, Knotentiefe und H\u00f6he des Bin\u00e4rbaumes.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"473\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-knotentypen-800x473.png\" alt=\"Bin\u00e4rbaum-Datenstruktur mit Knotentypen\" class=\"wp-image-20928\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-knotentypen-800x473.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-knotentypen-224x132.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-knotentypen-336x199.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-knotentypen-504x298.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-knotentypen-672x397.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-knotentypen-400x237.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-knotentypen-600x355.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-knotentypen-944x558.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-knotentypen-1200x710.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-knotentypen.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Bin\u00e4rbaum-Datenstruktur mit Knotentypen<\/figcaption><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"eigenschaften-von-binaerbaeumen\">Eigenschaften von Bin\u00e4rb\u00e4umen<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Bevor wir zur Implementierung von Bin\u00e4rb\u00e4umen und deren Operationen kommen, zun\u00e4chst eine kurze \u00dcbersicht \u00fcber einige spezielle Arten von Bin\u00e4rb\u00e4umen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"voller-binaerbaum\">Voller Bin\u00e4rbaum <\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">In einem <em>vollen Bin\u00e4rbaum<\/em> (englisch: <em>full binary tree<\/em>) haben alle Knoten entweder keine oder zwei Kinder.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"237\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/voller-binaerbaum-400x237.png\" alt=\"Voller Bin\u00e4rbaum\" class=\"wp-image-20942\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/voller-binaerbaum-400x237.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/voller-binaerbaum-224x133.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/voller-binaerbaum-336x199.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/voller-binaerbaum-504x299.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/voller-binaerbaum-672x398.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/voller-binaerbaum-600x356.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/voller-binaerbaum.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Voller Bin\u00e4rbaum<\/figcaption><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"vollstaendiger-binaerbaum\">Vollst\u00e4ndiger Bin\u00e4rbaum<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Leider wird diese Bezeichnung in der Literatur nicht einheitlich verwendet. Manche Autoren bezeichnen einen <em>kompletten Bin\u00e4rbaum<\/em> als vollst\u00e4ndig, andere bezeichnen einen <em>perfekten Bin\u00e4rbaum<\/em> als vollst\u00e4ndig. Ich werde daher nur die Begriffe <em>komplett<\/em> und <em>perfekt<\/em> verwenden.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"kompletter-binaerbaum\">Kompletter Bin\u00e4rbaum<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">In einem <em>kompletten Bin\u00e4rbaum<\/em> (englisch: <em>complete binary tree<\/em>) sind alle Ebenen, au\u00dfer m\u00f6glicherweise die letzte, vollst\u00e4ndig gef\u00fcllt. Wenn die letzte Ebene nicht vollst\u00e4ndig gef\u00fcllt ist, dann sind deren Knoten so weit wie m\u00f6glich links angeordnet.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"184\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/kompletter-binaerbaum-400x184.png\" alt=\"Kompletter Bin\u00e4rbaum\" class=\"wp-image-20944\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/kompletter-binaerbaum-400x184.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/kompletter-binaerbaum-224x103.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/kompletter-binaerbaum-336x155.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/kompletter-binaerbaum-504x232.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/kompletter-binaerbaum-672x309.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/kompletter-binaerbaum-600x276.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/kompletter-binaerbaum.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Kompletter Bin\u00e4rbaum<\/figcaption><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"perfekter-binaerbaum\">Perfekter Bin\u00e4rbaum<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Ein <em>perfekter Bin\u00e4rbaum<\/em> (englisch: <em>perfect binary tree<\/em>) ist ein voller Bin\u00e4rbaum, in dem alle Bl\u00e4tter die gleiche Tiefe haben. <\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"184\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/perfekter-binaerbaum-400x184.png\" alt=\"Perfekter Bin\u00e4rbaum der H\u00f6he 3\" class=\"wp-image-20940\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/perfekter-binaerbaum-400x184.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/perfekter-binaerbaum-224x103.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/perfekter-binaerbaum-336x155.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/perfekter-binaerbaum-504x232.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/perfekter-binaerbaum-672x309.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/perfekter-binaerbaum-600x276.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/perfekter-binaerbaum.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Perfekter Bin\u00e4rbaum der H\u00f6he 3<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Ein perfekter Bin\u00e4rbaum der H\u00f6he <em>h<\/em> hat <em>n = 2<sup>h+1<\/sup>-1<\/em> Knoten und <em>l = 2<sup>h<\/sup><\/em> Bl\u00e4tter. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Bei einer H\u00f6he von 3 sind das 15 Knoten, davon 8 Bl\u00e4tter.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"balancierter-binaerbaum\">Balancierter Bin\u00e4rbaum<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">In einem <em>balancierten Bin\u00e4rbaum<\/em> (englisch: <em>balanced binary tree<\/em>) unterscheiden sich die linken und rechten Teilb\u00e4ume eines jeden Knoten in der H\u00f6he um maximal eins.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"237\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/balancierter-binaerbaum-400x237.png\" alt=\"Balancierter Bin\u00e4rbaum\" class=\"wp-image-20948\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/balancierter-binaerbaum-400x237.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/balancierter-binaerbaum-224x133.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/balancierter-binaerbaum-336x199.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/balancierter-binaerbaum-504x299.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/balancierter-binaerbaum-672x398.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/balancierter-binaerbaum-600x356.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/balancierter-binaerbaum.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Balancierter Bin\u00e4rbaum<\/figcaption><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"sortierter-binaerbaum\">Sortierter Bin\u00e4rbaum<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">In einem <em>sortierten Bin\u00e4rbaum<\/em> (englisch: <em>sorted binary tree<\/em>) enth\u00e4lt der linke Teilbaum eines Knotens nur Werte die kleiner (oder gleich) als der Wert des Elternknotens sind, und der rechte Teilbaum nur Werte die gr\u00f6\u00dfer (oder gleich) als der Wert des Elternknotens sind. Solch eine Datenstruktur wird auch <a href=\"\/de\/algorithmen\/binaerer-suchbaum-java\/\">bin\u00e4rer Suchbaum<\/a> genannt.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"binaerbaum-in-java\">Bin\u00e4rbaum in Java<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">F\u00fcr die Bin\u00e4rbaum-Implementierung in Java definieren wir zun\u00e4chst die Datenstruktur f\u00fcr die Knoten (<a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/Node.java\" target=\"_blank\" rel=\"noopener\">Klasse Node im GitHub-Repository<\/a>). Der Einfachheit halber verwenden wir <code>int<\/code>-Primitive als Werte. Wir k\u00f6nnen nat\u00fcrlich auch jeden anderen oder einen generischen Datentyp verwenden; mit einem <code>int<\/code> ist der Code allerdings leserlicher \u2013 und das ist f\u00fcr dieses Tutorial am wichtigsten.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">Node<\/span> <\/span>{\n  <span class=\"hljs-keyword\">int<\/span> data;\n  Node left;\n  Node right;\n  Node parent;\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-title\">Node<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> data)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">this<\/span>.data = data;\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Die <code>parent<\/code>-Referenz ist nicht zwingend n\u00f6tig f\u00fcr die Speicherung und Darstellung des Baumes; sie ist allerdings \u2013 zumindest bei bestimmten Arten von Bin\u00e4rb\u00e4umen \u2013 hilfreich beim L\u00f6schen von Knoten.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Der Bin\u00e4rbaum selbst besteht zun\u00e4chst einmal nur aus dem Interface <a rel=\"noreferrer noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinaryTree.java\" target=\"_blank\">BinaryTree<\/a> und dessen Minimal-Implementierung <a rel=\"noreferrer noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BaseBinaryTree.java\" target=\"_blank\">BaseBinaryTree<\/a>, welche lediglich eine Referenz auf den Wurzelknoten enth\u00e4lt:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">interface<\/span> <span class=\"hljs-title\">BinaryTree<\/span> <\/span>{\n  <span class=\"hljs-function\">Node <span class=\"hljs-title\">getRoot<\/span><span class=\"hljs-params\">()<\/span><\/span>;\n}\n\n<span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">BaseBinaryTree<\/span> <span class=\"hljs-keyword\">implements<\/span> <span class=\"hljs-title\">BinaryTree<\/span> <\/span>{\n  Node root;\n\n  <span class=\"hljs-meta\">@Override<\/span>\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> Node <span class=\"hljs-title\">getRoot<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> root;\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Warum wir uns hier die M\u00fche machen ein Interface zu definieren, wird sich im weiteren Verlauf des Tutorials zeigen.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Bin\u00e4rbaum-Datenstruktur ist damit vollst\u00e4ndig definiert.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"binaerbaum-traversierung\">Bin\u00e4rbaum-Traversierung<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Eine der wichtigsten Operationen auf Bin\u00e4rb\u00e4umen ist die Traversierung aller Knoten, also das Besuchen aller Knoten in einer bestimmten Reihenfolge. Die g\u00e4ngigsten Arten der Traversierung sind:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Tiefensuche (pre-order, post-order, in-order, reverse in-order)<\/li>\n\n\n\n<li>Breitensuche (level-order)<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">In den folgenden Abschnitten werden die verschiedenen Arten an folgendem Beispiel gezeigt:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"274\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-beispiel-400x274.png\" alt=\"Beispiel f\u00fcr Bin\u00e4rbaum-Traversierung\" class=\"wp-image-21128\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-beispiel-400x274.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-beispiel-224x153.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-beispiel-336x230.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-beispiel-504x345.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-beispiel-672x460.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-beispiel-600x411.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-beispiel.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Beispiel f\u00fcr Bin\u00e4rbaum-Traversierung<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Das oben erw\u00e4hnte Besuchen w\u00e4hrend der Traversierung realisieren wir mit dem <a rel=\"noopener\" href=\"https:\/\/en.wikipedia.org\/wiki\/Visitor_pattern\" target=\"_blank\">Visitor-Pattern<\/a>, d. h. wir erstellen ein Visitor-Objekt, das wir an die Traversierungsmethode \u00fcbergeben.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"tiefensuche-im-binaerbaum\">Tiefensuche im Bin\u00e4rbaum<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Bei der Tiefensuche (englisch: depth-first search, DFS) wird in einer bestimmten Reihenfolge:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>der aktuelle Knoten besucht (im folgenden als \"N\" bezeichnet),<\/li>\n\n\n\n<li>die Tiefensuche rekursiv auf das linke Kind aufgerufen (im folgenden \"L\"),<\/li>\n\n\n\n<li>die Tiefensuche rekursiv auf das rechte Kind aufgerufen (im folgenden \"R\").<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Die g\u00e4ngigen Reihenfolgen sind:<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Hauptreihenfolge (pre-order)<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">In der Hauptreihenfolge (Kennzeichnung: N\u2013L\u2013R) erfolgt die Traversierung in folgender Reihenfolge:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Besuchen des aktuellen Knotens \"N\"<\/li>\n\n\n\n<li>Rekursiver Aufruf der Tiefensuche auf linken Teilbaum \"L\"<\/li>\n\n\n\n<li>Rekursiver Aufruf der Tiefensuche auf rechten Teilbaum \"R\"<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Die Knoten des Beispielbaumes werden, wie in folgender Grafik zu sehen, in folgender Reihenfolge besucht: 3\u21921\u219213\u219210\u219211\u219216\u219215\u21922<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"300\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-hauptreihenfolge-400x300.png\" alt=\"Bin\u00e4rbaum-Traversierung in Hauptreihenfolge (pre-order)\" class=\"wp-image-21138\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-hauptreihenfolge-400x300.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-hauptreihenfolge-224x168.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-hauptreihenfolge-336x252.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-hauptreihenfolge-504x378.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-hauptreihenfolge-672x504.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-hauptreihenfolge-600x450.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-hauptreihenfolge.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Bin\u00e4rbaum-Traversierung in Hauptreihenfolge (pre-order)<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Der Code hierf\u00fcr ist relativ simpel (<a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalRecursive.java#L21\" target=\"_blank\" rel=\"noreferrer noopener\">Klasse DepthFirstTraversalRecursive ab Zeile 21<\/a>):<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">traversePreOrder<\/span><span class=\"hljs-params\">(Node node, NodeVisitor visitor)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">if<\/span> (node == <span class=\"hljs-keyword\">null<\/span>) {\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n  visitor.visit(node);\n  traversePreOrder(node.left, visitor);\n  traversePreOrder(node.right, visitor);\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Die Methode kann entweder direkt aufgerufen werden \u2013 dann muss ihr der Wurzelknoten \u00fcbergeben werden \u2013 oder \u00fcber die nicht-statische Methode <code>traversePreOrder()<\/code> der gleichen Klasse (<a rel=\"noreferrer noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalRecursive.java#L17\" target=\"_blank\">DepthFirstTraversalRecursive ab Zeile 17<\/a>):<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-5\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">traversePreOrder<\/span><span class=\"hljs-params\">(NodeVisitor visitor)<\/span> <\/span>{\n  traversePreOrder(tree.getRoot(), visitor);\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-5\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Dazu muss eine Instanz von <code>DepthFirstTraversalRecursive<\/code> erstellt werden, wobei dem Konstruktur eine Referenz auf den Bin\u00e4rbaum \u00fcbergeben wird:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-6\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">new<\/span> DepthFirstTraversalRecursive(tree).traversePreOrder(visitor);<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-6\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Eine iterative Implementierung ist mit einem Stack m\u00f6glich (<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalIterative.java#L20\" target=\"_blank\">Klasse DepthFirstTraversalIterative ab Zeile 20<\/a>). Die iterativen Implementierungen sind recht komplex, weshalb ich sie hier nicht mit abdrucke. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Warum ich in den iterativen Tree-Traversals <code>ArrayDeque<\/code> anstatt <code>Stack<\/code> verwende, kannst du hier nachlesen: <a href=\"\/de\/algorithmen\/java-stack\/#warum-man-stack-nicht-mehr-verwenden-sollte\">Warum man Stack nicht (mehr) verwenden sollte<\/a><\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Nebenreihenfolge (post-order)<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">In der Nebenreihenfolge (Kennzeichnung: L\u2013R\u2013N) erfolgt die Traversierung in folgender Reihenfolge:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Rekursiver Aufruf der Tiefensuche auf linken Teilbaum \"L\"<\/li>\n\n\n\n<li>Rekursiver Aufruf der Tiefensuche auf rechten Teilbaum \"R\"<\/li>\n\n\n\n<li>Besuchen des aktuellen Knotens \"N\"<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Die Knoten des Beispielbaumes werden hierbei in folgender Reihenfolge besucht: 13\u21921\u219211\u219215\u21922\u219216\u219210\u21923<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"300\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-nebenreihenfolge-v2-400x300.png\" alt=\"Bin\u00e4rbaum-Traversierung in Nebenreihenfolge (post-order)\" class=\"wp-image-21186\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-nebenreihenfolge-v2-400x300.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-nebenreihenfolge-v2-224x168.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-nebenreihenfolge-v2-336x252.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-nebenreihenfolge-v2-504x378.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-nebenreihenfolge-v2-672x504.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-nebenreihenfolge-v2-600x450.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-nebenreihenfolge-v2.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Bin\u00e4rbaum-Traversierung in Nebenreihenfolge (post-order)<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Den Code findest du in <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalRecursive.java#L42\" target=\"_blank\">DepthFirstTraversalRecursive ab Zeile 42<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-7\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">traversePostOrder<\/span><span class=\"hljs-params\">(Node node, NodeVisitor visitor)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">if<\/span> (node == <span class=\"hljs-keyword\">null<\/span>) {\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n  traversePostOrder(node.left, visitor);\n  traversePostOrder(node.right, visitor);\n  visitor.visit(node);\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-7\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Die iterative Implementierung, die bei der Post-Order-Traversierung noch komplizierter ist als bei der Pre-Order-Traversierung, findest du in <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalIterative.java#L44\" target=\"_blank\">DepthFirstTraversalIterative ab Zeile 44<\/a>.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Symmetrische Reihenfolge (in-order)<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">In der symmetrischen Reihenfolge (Kennzeichnung: L\u2013N\u2013R) erfolgt die Traversierung in folgender Reihenfolge:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Rekursiver Aufruf der Tiefensuche auf linken Teilbaum \"L\"<\/li>\n\n\n\n<li>Besuchen des aktuellen Knotens \"N\"<\/li>\n\n\n\n<li>Rekursiver Aufruf der Tiefensuche auf rechten Teilbaum \"R\"<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Die Knoten des Beispielbaumes werden in folgender Reihenfolge besucht: 13\u21921\u21923\u219211\u219210\u219215\u219216\u21922<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"300\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-symmetrische-reihenfolge-400x300.png\" alt=\"Bin\u00e4rbaum-Traversierung in symmetrischer Reihenfolge (in-order)\" class=\"wp-image-21139\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-symmetrische-reihenfolge-400x300.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-symmetrische-reihenfolge-224x168.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-symmetrische-reihenfolge-336x252.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-symmetrische-reihenfolge-504x378.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-symmetrische-reihenfolge-672x504.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-symmetrische-reihenfolge-600x450.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-symmetrische-reihenfolge.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Bin\u00e4rbaum-Traversierung in symmetrischer Reihenfolge (in-order)<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Den rekursiven Code findest du in <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalRecursive.java#L62\" target=\"_blank\" rel=\"noopener\">DepthFirstTraversalRecursive ab Zeile 62<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-8\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">traverseInOrder<\/span><span class=\"hljs-params\">(Node node, NodeVisitor visitor)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">if<\/span> (node == <span class=\"hljs-keyword\">null<\/span>) {\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n  traverseInOrder(node.left, visitor);\n  visitor.visit(node);\n  traverseInOrder(node.right, visitor);\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-8\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Die iterative Implementierung der In-Order-Traversierung findest du in <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalIterative.java#L69\" target=\"_blank\">DepthFirstTraversalIterative ab Zeile 69<\/a>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Im bin\u00e4ren Suchbaum werden bei der In-Order-Traversierung die Knoten in der Reihenfolge ihrer Sortierung besucht. <\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Anti-symmetrische Reihenfolge (reverse in-order)<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">In der anti-symmetrischen Reihenfolge (Kennzeichnung: R\u2013N\u2013L) erfolgt die Traversierung in folgender Reihenfolge:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Rekursiver Aufruf der Tiefensuche auf rechten Teilbaum \"R\"<\/li>\n\n\n\n<li>Besuchen des aktuellen Knotens \"N\"<\/li>\n\n\n\n<li>Rekursiver Aufruf der Tiefensuche auf linken Teilbaum \"L\"<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Die Knoten des Beispielbaumes werden in entgegengesetzter Reihenfolge zur In-Order-Traversierung besucht: 2\u219216\u219215\u219210\u219211\u21923\u21921\u219213<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"300\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-anti-symmetrische-reihenfolge-400x300.png\" alt=\"Bin\u00e4rbaum-Traversierung in anti-symmetrischer Reihenfolge (reverse in-order)\" class=\"wp-image-21140\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-anti-symmetrische-reihenfolge-400x300.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-anti-symmetrische-reihenfolge-224x168.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-anti-symmetrische-reihenfolge-336x252.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-anti-symmetrische-reihenfolge-504x378.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-anti-symmetrische-reihenfolge-672x504.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-anti-symmetrische-reihenfolge-600x450.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-anti-symmetrische-reihenfolge.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Bin\u00e4rbaum-Traversierung in anti-symmetrischer Reihenfolge (reverse in-order)<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Den rekursiven Code findest du in <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalRecursive.java#L83\" target=\"_blank\" rel=\"noopener\">DepthFirstTraversalRecursive ab Zeile 83<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-9\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">traverseReverseInOrder<\/span><span class=\"hljs-params\">(Node node, NodeVisitor visitor)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">if<\/span> (node == <span class=\"hljs-keyword\">null<\/span>) {\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n  traverseReverseInOrder(node.right, visitor);\n  visitor.visit(node);\n  traverseReverseInOrder(node.left, visitor);\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-9\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Die iterative Implementierung der Reverse-In-Order-Traversierung findest du in <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalIterative.java#L89\" target=\"_blank\">DepthFirstTraversalIterative ab Zeile 89<\/a>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Im bin\u00e4ren Suchbaum werden bei der Reverse-In-Order-Traversierung die Knoten in absteigender Reihenfolge ihrer Sortierung besucht.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"breitensuche-im-binaerbaum\">Breitensuche im Bin\u00e4rbaum<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Bei der Breitensuche (englisch: breadth-first, BFS) \u2013 auch Level-Order-Traversierung genannt \u2013 werden die Knoten von der Wurzel beginnend, Ebene f\u00fcr Ebene, von links nach rechts besucht.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Es ergibt sich folgende Reihenfolge: 3\u21921\u219210\u219213\u219211\u219216\u219215\u21922<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"275\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-breitensuche-600x275.png\" alt=\"Bin\u00e4rbaum-Traversierung via Breitensuche (level-order)\" class=\"wp-image-21143\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-breitensuche-600x275.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-breitensuche-224x103.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-breitensuche-336x154.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-breitensuche-504x231.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-breitensuche-672x308.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-breitensuche-400x183.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-breitensuche-800x367.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-breitensuche-944x433.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-traversierung-breitensuche.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Bin\u00e4rbaum-Traversierung via Breitensuche (level-order)<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Um die Knoten in dieser Reihenfolge zu besuchen, ben\u00f6tigen wir eine Queue, in der wir zuerst den Root-Knoten einf\u00fcgen, und dann wiederholt das erste Element entnehmen, dieses besuchen und dessen Kinder in die Queue eintragen \u2013 solange bis die Queue wieder leer ist.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Den Code findest du in der Klasse <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BreadthFirstTraversal.java\" target=\"_blank\" rel=\"noopener\">BreadthFirstTraversal<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-10\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">traverseLevelOrder<\/span><span class=\"hljs-params\">(Node root, NodeVisitor visitor)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">if<\/span> (root == <span class=\"hljs-keyword\">null<\/span>) {\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n\n  Queue&lt;Node&gt; queue = <span class=\"hljs-keyword\">new<\/span> ArrayDeque&lt;&gt;();\n  queue.add(root);\n\n  <span class=\"hljs-keyword\">while<\/span> (!queue.isEmpty()) {\n    Node node = queue.poll();\n    visitor.visit(node);\n\n    <span class=\"hljs-keyword\">if<\/span> (node.left != <span class=\"hljs-keyword\">null<\/span>) {\n      queue.add(node.left);\n    }\n    <span class=\"hljs-keyword\">if<\/span> (node.right != <span class=\"hljs-keyword\">null<\/span>) {\n      queue.add(node.right);\n    }\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-10\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Den Aufruf aller Traversierungs-Arten findest du beispielhaft in der Methode <a rel=\"noreferrer noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/example\/Example1.java#L50\" target=\"_blank\"><code>traverseTreeInVariousWays()<\/code> der Klasse Example1<\/a>.<\/p>\n\n\n<div class=\"convertkit-form wp-block-convertkit-form\" style=\"\"><script async data-uid=\"5c918c0177\" src=\"https:\/\/happycoders.kit.com\/5c918c0177\/index.js\" data-jetpack-boost=\"ignore\" data-no-defer=\"1\" data-no-optimize=\"1\" nowprocket><\/script><\/div>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"operationen-auf-binaerbaeumen\">Operationen auf Bin\u00e4rb\u00e4umen<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Neben der Traversierung sind weitere grundlegenden Operationen auf Bin\u00e4rb\u00e4umen das Einf\u00fcgen sowie das L\u00f6schen von Knoten.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Operationen zum Suchen werden von speziellen Bin\u00e4rb\u00e4ume wie z. B. dem <a href=\"\/de\/algorithmen\/binaerer-suchbaum-java\/\">bin\u00e4ren Suchbaum<\/a> bereitgestellt. Ohne spezielle Eigenschaften k\u00f6nnen wir im Bin\u00e4rbaum nur suchen, in dem wir \u00fcber alle Knoten traversieren und diese mit dem gesuchten Element vergleichen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"element-einfuegen\">Element einf\u00fcgen<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Beim Einf\u00fcgen neuer Elemente m\u00fcssen wir verschiedene F\u00e4lle unterscheiden:<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall A: Knoten unter Blatt oder Halbblatt einf\u00fcgen<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Es ist leicht einen neuen Knoten an ein Blatt oder ein Halbblatt anzuh\u00e4ngen. Hierzu m\u00fcssen wir lediglich die <code>left<\/code>- oder <code>right<\/code>-Referenz des Parent-Knotens <em>P<\/em>, an den wir den neuen Knoten <em>N<\/em> anh\u00e4ngen wollen, auf den neuen Knoten setzen. Wenn wir auch mit <code>parent<\/code>-Referenzen arbeiten, m\u00fcssen wir diese im neuen Knoten <em>N<\/em> auf den Parent-Knoten <em>P<\/em> setzen.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"200\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_blatt-600x200.png\" alt=\"Anh\u00e4ngen eines neuen Knotens an ein Blatt\" class=\"wp-image-21072\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_blatt-600x200.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_blatt-224x75.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_blatt-336x112.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_blatt-504x168.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_blatt-672x224.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_blatt-400x133.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_blatt-800x267.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_blatt-944x315.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_blatt.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Anh\u00e4ngen eines neuen Knotens an ein Blatt<\/figcaption><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"200\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_halbblatt-600x200.png\" alt=\"Anh\u00e4ngen eines neuen Knotens an ein Halbblatt\" class=\"wp-image-21076\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_halbblatt-600x200.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_halbblatt-224x75.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_halbblatt-336x112.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_halbblatt-504x168.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_halbblatt-672x224.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_halbblatt-400x133.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_halbblatt-800x267.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_halbblatt-944x315.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_halbblatt.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Anh\u00e4ngen eines neuen Knotens an ein Halbblatt<\/figcaption><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Fall B: Knoten zwischen internen Knoten und dessen Kind einf\u00fcgen<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Doch wie geht man vor, wenn man einen Knoten zwischen einem internen Knoten und einem seiner Kinder einf\u00fcgen will?<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"210\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_mehrdeutig_v4-400x210.png\" alt=\"Neuen Knoten unter internen Knoten einf\u00fcgen\" class=\"wp-image-21087\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_mehrdeutig_v4-400x210.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_mehrdeutig_v4-224x118.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_mehrdeutig_v4-336x176.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_mehrdeutig_v4-504x265.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_mehrdeutig_v4-672x353.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_mehrdeutig_v4-600x315.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_mehrdeutig_v4.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Neuen Knoten unter internen Knoten einf\u00fcgen<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Das ist nur mit einer Reorganisation des Baumes m\u00f6glich. Wie genau der Baum reorganisiert wird, h\u00e4ngt von der konkreten Art des Bin\u00e4rbaumes ab.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wir implementieren in diesem Tutorial einen sehr einfachen Bin\u00e4rbaum und gehen f\u00fcr die Reorganisation wie folgt vor: <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Wenn der neue Knoten <em>N<\/em> als linkes Kind unter den internen Knoten <em>P<\/em> eingef\u00fcgt werden soll, wird <em>P<\/em>s aktueller linker Teilbaum <em>L<\/em> als linkes Kind unter den neuen Knoten <em>N<\/em> gesetzt. Entsprechend wird der Parent von <em>L<\/em> auf <em>N<\/em> gesetzt und der Parent von <em>N<\/em> auf <em>P<\/em>.<\/li>\n\n\n\n<li>Wenn der neue Knoten <em>N<\/em> als rechtes Kind unter den internen Knoten <em>P<\/em> eingef\u00fcgt werden soll, wird <em>P<\/em>s aktueller rechter Teilbaum <em>R<\/em> als rechtes Kind unter den neuen Knoten <em>N<\/em> gesetzt. Entsprechend wird der Parent von <em>R<\/em> auf <em>N<\/em> gesetzt und der Parent von <em>N<\/em> auf <em>P<\/em>.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Die folgende Grafik zeigt den zweiten Fall: Wir f\u00fcgen den neuen Knoten <em>N<\/em> zwischen <em>P<\/em> und <em>R<\/em> ein:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"286\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_zwischen_knoten-600x286.png\" alt=\"Einf\u00fcgen eines neuen Knotens zwischen internem Knoten und seinem Kind\" class=\"wp-image-21090\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_zwischen_knoten-600x286.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_zwischen_knoten-224x107.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_zwischen_knoten-336x160.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_zwischen_knoten-504x240.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_zwischen_knoten-672x320.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_zwischen_knoten-400x191.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_zwischen_knoten-800x381.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_zwischen_knoten-944x450.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_einfuegen_zwischen_knoten.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Einf\u00fcgen eines neuen Knotens zwischen internem Knoten und seinem Kind<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Das ist \u2013 wie gesagt \u2013 eine sehr einfache Implementierung. Im Beispiel oben resultiert diese in einem stark unbalancierten Bin\u00e4rbaum.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Spezielle Bin\u00e4rb\u00e4ume gehen hier anders vor, um eine Baum-Struktur beizubehalten, die die speziellen Eigenschaften des jeweiligen Bin\u00e4rbaumes (Sortierung, Balancierung, etc.) erf\u00fcllt.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Baumknoten einf\u00fcgen \u2013 Java-Quellcode<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Hier siehst du den Code zum Einf\u00fcgen eines neuen Knotens mit Wert <code>data<\/code> unter den gegebenen Knoten <code>parent<\/code> an die gegebene Seite <code>side<\/code> (links oder rechts) mit der im vorherigen Abschnitt festgelegten Reorganisations-Strategie (<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/SimpleBinaryTree.java#L18\" target=\"_blank\">Klasse SimpleBinaryTree ab Zeile 18<\/a>).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">(Der <a href=\"\/de\/java\/switch-expressions\/\">Switch-Ausdruck mit den geschweiften Klammern<\/a> wurde in Java 12\/13 eingef\u00fchrt).<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-11\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> Node <span class=\"hljs-title\">insertNode<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> data, Node parent, Side side)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">var<\/span> node = <span class=\"hljs-keyword\">new<\/span> Node(data);\n\n  node.parent = parent;\n\n  <span class=\"hljs-keyword\">switch<\/span> (side) {\n    <span class=\"hljs-keyword\">case<\/span> LEFT -&gt; {\n      <span class=\"hljs-keyword\">if<\/span> (parent.left != <span class=\"hljs-keyword\">null<\/span>) {\n        node.left = parent.left;\n        node.left.parent = node;\n      }\n      parent.left = node;\n    }\n\n    <span class=\"hljs-keyword\">case<\/span> RIGHT -&gt; {\n      <span class=\"hljs-keyword\">if<\/span> (parent.right != <span class=\"hljs-keyword\">null<\/span>) {\n        node.right = parent.right;\n        node.right.parent = node;\n      }\n      parent.right = node;\n    }\n\n    <span class=\"hljs-keyword\">default<\/span> -&gt; <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalStateException();\n  }\n\n  <span class=\"hljs-keyword\">return<\/span> node;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-11\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">In der <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/example\/Example1.java#L20\" target=\"_blank\">Methode <\/a><code><a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/example\/Example1.java#L27\" target=\"_blank\" rel=\"noreferrer noopener\">createSampleTree()<\/a><\/code><a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/example\/Example1.java#L20\" target=\"_blank\"> der Klasse Example1<\/a> siehst du, wie der Bin\u00e4rbaum aus dem Beispiel vom Beginn des Artikels angelegt wird. <\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"element-loeschen\">Element l\u00f6schen<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Auch beim L\u00f6schen eines Knotens m\u00fcssen wir verschiedene F\u00e4lle unterscheiden.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall A: Knoten ohne Kinder (Blatt) l\u00f6schen<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Ist der zu l\u00f6schende Knoten <em>N<\/em> ein Blatt, hat also selbst keine Kinder, dann wird der Knoten einfach entfernt. Dazu pr\u00fcfen wir, ob der Knoten linkes oder rechtes Kind des Parents <em>P<\/em> ist und setzen entsprechend dessen <code>left<\/code>- oder <code>right<\/code>-Referenz auf <code>null<\/code>.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"199\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_blatt_entfernen_v2-600x199.png\" alt=\"Knoten ohne Kind (Blatt) aus Bin\u00e4rbaum entfernen\" class=\"wp-image-21097\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_blatt_entfernen_v2-600x199.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_blatt_entfernen_v2-224x74.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_blatt_entfernen_v2-336x111.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_blatt_entfernen_v2-504x167.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_blatt_entfernen_v2-672x223.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_blatt_entfernen_v2-400x133.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_blatt_entfernen_v2-800x265.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_blatt_entfernen_v2-944x313.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_blatt_entfernen_v2.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Knoten ohne Kind (Blatt) aus Bin\u00e4rbaum entfernen<\/figcaption><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Fall B: Knoten mit einem Kind (Halbblatt) l\u00f6schen<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Hat der zu l\u00f6schende Knoten <em>N<\/em> selbst ein Kind <em>C<\/em>, dann r\u00fcckt dieses an die gel\u00f6schte Position auf. Wir m\u00fcssen wieder pr\u00fcfen, ob der zu l\u00f6schende Knoten <em>N<\/em> linkes oder rechtes Kind des Parents <em>P<\/em> ist. Danach setzen wir entsprechend die <code>left<\/code>- oder <code>right<\/code>-Referenz des Parents auf das Kind <em>C<\/em> des zu l\u00f6schenden Knotens <em>N<\/em> (den vorherigen Enkel) \u2013 und die <code>parent<\/code>-Referenz des Kindes <em>C<\/em> auf den Parent <em>P<\/em> des zu l\u00f6schenden Knotens <em>N<\/em> (den vorherigen Gro\u00dfeltern-Knoten).<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"211\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_halbblatt_entfernen-600x211.png\" alt=\"Knoten mit einem Kind (Halbblatt) aus Bin\u00e4rbaum entfernen\" class=\"wp-image-21099\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_halbblatt_entfernen-600x211.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_halbblatt_entfernen-224x79.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_halbblatt_entfernen-336x118.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_halbblatt_entfernen-504x177.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_halbblatt_entfernen-672x236.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_halbblatt_entfernen-400x141.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_halbblatt_entfernen-800x281.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_halbblatt_entfernen-944x332.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_halbblatt_entfernen.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Knoten mit einem Kind (Halbblatt) aus Bin\u00e4rbaum entfernen<\/figcaption><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Fall C: Knoten mit zwei Kindern l\u00f6schen<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Wie geht man vor, wenn man einen Knoten mit zwei Kindern l\u00f6schen will?<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"211\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_mehrdeutig-400x211.png\" alt=\"Wie entfernt man einen internen Knoten aus einem Bin\u00e4rbaum?\" class=\"wp-image-21102\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_mehrdeutig-400x211.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_mehrdeutig-224x118.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_mehrdeutig-336x177.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_mehrdeutig-504x266.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_mehrdeutig-672x354.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_mehrdeutig-600x317.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_mehrdeutig.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Wie entfernt man einen internen Knoten aus einem Bin\u00e4rbaum?<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Dies ist nur mit einer Umorganisation des Bin\u00e4rbaum m\u00f6glich. Analog zum Einf\u00fcgen gibt es auch f\u00fcr das L\u00f6schen \u2013 je nach konkreter Art des Bin\u00e4rbaumes \u2013 unterschiedliche Strategien. In einem Heap beispielsweise wird an die Position des gel\u00f6schten Knotens der letzte Knoten des Baums gesetzt und danach der Heap repariert.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wir verwenden f\u00fcr unser Tutorial folgende, einfach zu implementierende Variante: <\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Wir ersetzen den gel\u00f6schten Knoten <em>N<\/em> durch dessen linken Teilbaum <em>L<\/em>.<\/li>\n\n\n\n<li>Wir h\u00e4ngen den rechten Teilbaum <em>R<\/em> an den am weitesten rechts liegenden Knoten des linken Teilbaums an.<\/li>\n<\/ol>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"358\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_v2-800x358.png\" alt=\"Knoten mit zwei Kindern aus Bin\u00e4rbaum entfernen\" class=\"wp-image-21108\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_v2-800x358.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_v2-224x100.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_v2-336x150.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_v2-504x226.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_v2-672x301.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_v2-400x179.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_v2-600x269.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_v2-944x422.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_v2-1200x537.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum_internen_knoten_entfernen_v2.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Knoten mit zwei Kindern aus Bin\u00e4rbaum entfernen<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Es ist gut zu erkennen, wie diese Strategie zu einem sehr unbalancierten Bin\u00e4rbaum f\u00fchrt. Bin\u00e4rb\u00e4ume wir der bin\u00e4re Suchbaum und der Bin\u00e4re Heap haben daher \u2013 wie auch beim Einf\u00fcgen \u2013 komplexere Strategien. <\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Baumknoten l\u00f6schen \u2013 Java-Quellcode<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Die folgende Methode (<a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/SimpleBinaryTree.java#L71\" target=\"_blank\" rel=\"noopener\">Klasse SimpleBinaryTree ab Zeile 71<\/a>) entfernt den \u00fcbergebenen Knoten <code>node<\/code> aus dem Baum. Die F\u00e4lle A, B und C sind durch entsprechende Kommentare gekennzeichnet. <\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-12\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">deleteNode<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">if<\/span> (node.parent == <span class=\"hljs-keyword\">null<\/span> &amp;&amp; node != root) {\n    <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalStateException(<span class=\"hljs-string\">\"Node has no parent and is not root\"<\/span>);\n  }\n\n  <span class=\"hljs-comment\">\/\/ Case A: Node has no children --&gt; set node to null in parent<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (node.left == <span class=\"hljs-keyword\">null<\/span> &amp;&amp; node.right == <span class=\"hljs-keyword\">null<\/span>) {\n    setParentsChild(node, <span class=\"hljs-keyword\">null<\/span>);\n  }\n\n  <span class=\"hljs-comment\">\/\/ Case B: Node has one child --&gt; replace node by node's child in parent<\/span>\n  <span class=\"hljs-comment\">\/\/ Case B1: Node has only left child<\/span>\n  <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (node.right == <span class=\"hljs-keyword\">null<\/span>) {\n    setParentsChild(node, node.left);\n  }\n\n  <span class=\"hljs-comment\">\/\/ Case B2: Node has only right child<\/span>\n  <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (node.left == <span class=\"hljs-keyword\">null<\/span>) {\n    setParentsChild(node, node.right);\n  }\n\n  <span class=\"hljs-comment\">\/\/ Case C: Node has two children<\/span>\n  <span class=\"hljs-keyword\">else<\/span> {\n    removeNodeWithTwoChildren(node);\n  }\n\n  <span class=\"hljs-comment\">\/\/ Remove all references from the deleted node<\/span>\n  node.parent = <span class=\"hljs-keyword\">null<\/span>;\n  node.left = <span class=\"hljs-keyword\">null<\/span>;\n  node.right = <span class=\"hljs-keyword\">null<\/span>;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-12\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Die Methode <code>setParentsChild()<\/code> pr\u00fcft, ob der zu l\u00f6schende Knoten das linke oder rechte Kind seines Elternknotens ist und ersetzt die entsprechende Referenz im Elternknoten durch den Kindknoten <code>child<\/code>. Dieser ist <code>null<\/code>, wenn der zu l\u00f6schende Knoten keine Kinder hat und entsprechend die Kind-Referenz im Elternknoten auf <code>null<\/code> gesetzt werden soll.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">F\u00fcr den Fall, dass der zu l\u00f6schende Knoten die Wurzel ist, wird einfach die Wurzelreferenz neu gesetzt.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-13\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">setParentsChild<\/span><span class=\"hljs-params\">(Node node, Node child)<\/span> <\/span>{\n  <span class=\"hljs-comment\">\/\/ Node is root? Has no parent, set root reference instead<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (node == root) {\n    root = child;\n    <span class=\"hljs-keyword\">if<\/span> (child != <span class=\"hljs-keyword\">null<\/span>) {\n      child.parent = <span class=\"hljs-keyword\">null<\/span>;\n    }\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n\n  <span class=\"hljs-comment\">\/\/ Am I the left or right child of my parent?<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (node.parent.left == node) {\n    node.parent.left = child;\n  } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (node.parent.right == node) {\n    node.parent.right = child;\n  } <span class=\"hljs-keyword\">else<\/span> {\n    <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalStateException(\n        <span class=\"hljs-string\">\"Node \"<\/span> + node.data + <span class=\"hljs-string\">\" is neither a left nor a right child of its parent \"<\/span>\n            + node.parent.data);\n  }\n\n  <span class=\"hljs-keyword\">if<\/span> (child != <span class=\"hljs-keyword\">null<\/span>) {\n    child.parent = node.parent;\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-13\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">In Fall C (Knoten mit zwei Kindern l\u00f6schen) wird der Baum, wie im vorangegangenen Abschnitt beschrieben, umorganisiert. Dies geschieht in der separaten Methode <code>removeNodeWithTwoChildren()<\/code>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-14\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">removeNodeWithTwoChildren<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n  Node leftTree = node.left;\n  Node rightTree = node.right;\n\n  setParentsChild(node, leftTree);\n\n  <span class=\"hljs-comment\">\/\/ find right-most child of left tree<\/span>\n  Node rightMostChildOfLeftTree = leftTree;\n  <span class=\"hljs-keyword\">while<\/span> (rightMostChildOfLeftTree.right != <span class=\"hljs-keyword\">null<\/span>) {\n    rightMostChildOfLeftTree = rightMostChildOfLeftTree.right;\n  }\n\n  <span class=\"hljs-comment\">\/\/ append right tree to right child<\/span>\n  rightMostChildOfLeftTree.right = rightTree;\n  rightTree.parent = rightMostChildOfLeftTree;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-14\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">In der <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/example\/Example1.java#L83\" target=\"_blank\" rel=\"noreferrer noopener\">Methode <code>deleteSomeNodes()<\/code> der Klasse Example1<\/a> siehst du, wie einige Knoten des Beispielbaums wieder gel\u00f6scht werden.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"array-darstellung-des-binaerbaums\">Array-Darstellung des Bin\u00e4rbaums<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Zum Abschluss m\u00f6chte ich dir eine alternative Repr\u00e4sentation des Bin\u00e4rbaums zeigen: die Speicherung in einem Array.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Dabei enth\u00e4lt das Array so viele Elemente wie ein perfekter Bin\u00e4rbaum der H\u00f6he des zu speichernden Bin\u00e4rbaumes, also <em>2<sup>h+1<\/sup>-1<\/em> Elemente bei einer H\u00f6he <em>h<\/em> (in der folgenden Grafik: 7 Elemente bei H\u00f6he 2).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Knoten des Baumes werden von der Wurzel abw\u00e4rts, Ebene f\u00fcr Ebene, von links nach rechts durchnummeriert und auf das Array abgebildet, wie folgende Grafik zeigt:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"380\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-array-darstellung-400x380.png\" alt=\"Array-Repr\u00e4sentation eines Bin\u00e4rbaums\" class=\"wp-image-20959\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-array-darstellung-400x380.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-array-darstellung-224x213.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-array-darstellung-336x319.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-array-darstellung-504x479.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-array-darstellung-672x638.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-array-darstellung-600x570.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binaerbaum-array-darstellung.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Array-Repr\u00e4sentation eines Bin\u00e4rbaums<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Nicht vorhandene Knoten k\u00f6nnen durch einen festgelegten Wert dargestellt werden. Sollte der Baum beispielsweise nur nicht-negative ganze Zahlen enthalten, k\u00f6nnte ein fehlender Knoten durch den Wert -1 dargestellt werden.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Bei einem <a href=\"#Kompletter_Binarbaum\">kompletten Bin\u00e4rbaum<\/a> kann alternativ das Array entsprechend verk\u00fcrzt werden oder die Anzahl der Knoten als zus\u00e4tzlicher Wert gespeichert werden.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"vor-und-nachteile-der-array-darstellung\">Vor- und Nachteile der Array-Darstellung<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Die Array-Darstellung hat folgende Vorteile:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Die Speicherung ist kompakter, da keine Referenzen auf Kinder (und ggf. Eltern) ben\u00f6tigt werden.<\/li>\n\n\n\n<li>Trotzdem gelangt man schnell von Eltern zu Kindern und umgekehrt:<br>F\u00fcr einen Knoten an Index <em>i<\/em> befinden sich...\n<ul class=\"wp-block-list\">\n<li>das linke Kind an Index <em>2i+1<\/em>,<\/li>\n\n\n\n<li>das rechte Kind an Index <em>2i+2<\/em>,<\/li>\n\n\n\n<li>der Elternknoten an Index <em>i\/2 abgerundet<\/em>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Eine Level-Order-Traversierung kann durch simple Iteration \u00fcber das Array durchgef\u00fchrt werden.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Dagegen aufwiegen muss man folgende Nachteile:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Wenn der Bin\u00e4rbaum nicht komplett ist, wird Speicherplatz durch ungenutzte Array-Felder verschwendet.<\/li>\n\n\n\n<li>Wenn der Baum \u00fcber die Array-Gr\u00f6\u00dfe hinaus w\u00e4chst, m\u00fcssen die Daten in ein neues, gr\u00f6\u00dferes Array kopiert werden.<\/li>\n\n\n\n<li>Wenn der Baum kleiner wird, sollten (mit einem gewissen Spielraum) die Daten in ein neues, kleineres Array kopiert werden, um ungenutzten Speicherplatz freizugeben.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zusammenfassung\">Zusammenfassung<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">In diesem Artikel hast du erfahren, was ein Bin\u00e4rbaum ist, welche Arten von Bin\u00e4rb\u00e4umen es gibt, welche Operationen auf Bin\u00e4rb\u00e4ume anwendbar sind und wie man Bin\u00e4rb\u00e4ume in Java implementiert.<\/p>\n<aside><p>Wenn dir der Artikel weitergeholfen hat, w\u00fcrde ich mich sehr \u00fcber eine positive Bewertung auf meinem <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">ProvenExpert-Profil<\/a> freuen. Dein Feedback hilft mir, meine Inhalte weiter zu verbessern und motiviert mich, neue informative Artikel zu schreiben.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">Bewertung abgeben<\/a><\/p>\r\n                        <p>M\u00f6chtest du auf dem Laufenden bleiben und informiert werden, wenn neue Artikel auf HappyCoders.eu ver\u00f6ffentlicht werden? Dann <a href=\"#\" data-formkit-toggle=\"d8ee997126\">klicke hier<\/a>, um dich f\u00fcr den HappyCoders-Newsletter anzumelden.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"#\" data-formkit-toggle=\"d8ee997126\">Newsletter-Anmeldung<\/a><\/p><\/aside>","protected":false},"excerpt":{"rendered":"<p>Was ist ein Bin\u00e4rbaum und welche Arten gibt es? Wie implementiert man einen Bin\u00e4rbaum in Java? Welche Operationen gibt es? Was bedeuten pre-order, in-order, post-order und level-order bei der Traversierung?<\/p>\n","protected":false},"author":1,"featured_media":30728,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_titles_title":"","_seopress_titles_desc":"Was ist ein Bin\u00e4rbaum und wie implementiert man ihn in Java? Was bedeuten pre-order, in-order, post-order und level-order bei der Traversierung?","_seopress_robots_index":"","_seopress_robots_follow":"","_seopress_robots_imageindex":"","_seopress_robots_snippet":"","_seopress_robots_primary_cat":"none","_seopress_robots_breadcrumbs":"","_seopress_robots_freeze_modified_date":"","_seopress_robots_custom_modified_date":"","_seopress_robots_canonical":"","_seopress_social_fb_title":"","_seopress_social_fb_desc":"","_seopress_social_fb_img":"","_seopress_social_fb_img_attachment_id":0,"_seopress_social_fb_img_width":0,"_seopress_social_fb_img_height":0,"_seopress_social_twitter_title":"","_seopress_social_twitter_desc":"","_seopress_social_twitter_img":"","_seopress_social_twitter_img_attachment_id":0,"_seopress_social_twitter_img_width":0,"_seopress_social_twitter_img_height":0,"_seopress_redirections_value":"","_seopress_redirections_enabled":"","_seopress_redirections_enabled_regex":"","_seopress_redirections_logged_status":"both","_seopress_redirections_param":"","_seopress_redirections_type":301,"_seopress_analysis_target_kw":"bin\u00e4rbaum","_seopress_news_disabled":"","_seopress_video_disabled":"","_seopress_video":[],"_seopress_pro_schemas_manual":[{"_seopress_pro_rich_snippets_type":"none"}],"_seopress_pro_rich_snippets_disable_all":"","_seopress_pro_rich_snippets_disable":[],"_seopress_pro_schemas":[],"_uag_custom_page_level_css":"","_wp_convertkit_post_meta":{"form":"-1","landing_page":"","tag":"0","restrict_content":"0"},"_metis_text_type":"standard","_metis_text_length":22640,"_post_count":0,"footnotes":""},"categories":[127],"tags":[174],"class_list":["post-20900","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-datenstrukturen-baeume"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/05\/binary-tree-1770x986-1.jpg",1770,986,false]},"uagb_author_info":{"display_name":"Sven Woltmann","author_link":"https:\/\/www.happycoders.eu\/de\/author\/sven\/"},"uagb_comment_info":0,"uagb_excerpt":"Was ist ein Bin\u00e4rbaum und welche Arten gibt es? Wie implementiert man einen Bin\u00e4rbaum in Java? Welche Operationen gibt es? Was bedeuten pre-order, in-order, post-order und level-order bei der Traversierung?","public_identification_id":"6aaedcfdfd134021bd41786bcda967d0","private_identification_id":"cbc440c338d9483c90628af3d8fceab8","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/20900","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/comments?post=20900"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/20900\/revisions"}],"predecessor-version":[{"id":52485,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/20900\/revisions\/52485"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/30728"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=20900"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=20900"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=20900"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}