{"id":3014,"date":"2018-02-21T11:35:51","date_gmt":"2018-02-21T10:35:51","guid":{"rendered":"https:\/\/fernuni.digreb.net\/?p=3014"},"modified":"2019-04-29T12:25:59","modified_gmt":"2019-04-29T10:25:59","slug":"32561-erstellung-und-traversierung-von-in-binaerbaeumen","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=3014","title":{"rendered":"32561: Erstellung und Traversierung von\/in Bin\u00e4rb\u00e4umen"},"content":{"rendered":"

Erstellen von Bin\u00e4rb\u00e4umen aus B\u00e4umen der Ordnung $$k$$<\/h1>\n

Leider habe ich meine Bachelor-Unterlagen verlegt und musste mich f\u00fcr die Klausur f\u00fcr das Thema durch das Skript w\u00fchlen. Die Anleitung zur Baumtransformation beschr\u00e4nkt sich hier auf zwei richtige S\u00e4tze:<\/p>\n

    \n
  1. R1: S\u00f6hne von Knoten sind linke Nachfolger<\/li>\n
  2. R2: Br\u00fcder von Knoten sind rechte Nachfolger<\/li>\n<\/ol>\n

    Soweit so korrekt. F\u00fcr mich war es jedoch noch nicht greifbar und auch das Bild half mir nicht besonders weiter. Liegt aber wohl eher an meinem deliriumartigen Zustand durch den massiven Missbrauch von alkoholfreiem Hustensaft. Zuf\u00e4llig habe ich ein Beispiel gefunden, dass mir jedoch auf die Spr\u00fcnge half. Vielleicht hilft es euch auch:<\/p>\n

    Beispiel: Baumtransformation zum Bin\u00e4rbaum<\/strong><\/p>\n

    Ein Bin\u00e4rbaum ist ein Baum, dessen Knoten h\u00f6chstens zwei direkte Nachkommen haben. D. h. wir m\u00fcssen den Baum so transformieren, dass seine logische Struktur zwar erhalten bleibt, aber der neue Baum diesem Kriterium entspricht.<\/p>\n

    <\/p>\n

    \"\"<\/div>\n

    Schritt 1:<\/em><\/p>\n

    Wenden wir jetzt die zwei Regeln R1 und R2 von oben auf die ersten zwei Zeilen mit Knoten A, B, C und D an. A hat als S\u00f6hne B, C und D. Es wird immer<\/strong> zuerst der erste Sohn von links genommen. Dieser wird Nachfolger von A (Anwendung R1, Pfeil zw. A und B). Nun wenden wir R2 auf Knoten B an: seine Br\u00fcder werden seine rechten Nachfolger (Anwendung R2, Pfeile von B zu C und von C zu D). So sieht unser Baum nach dem 1. Schritt aus.<\/p>\n

    \n

    \"\"<\/p>\n<\/div>\n

    Schritt 2:<\/em><\/p>\n

    Das gleiche machen wir nun jetzt mit der n\u00e4chsten Zeile und Knoten E. Er ist erstes Kind von B und wird sein linker Nachfolger (R1). Knoten E hat einen Bruder und das wird sein rechter Nachfolger (R2).<\/p>\n

    \"\"<\/div>\n

    Schritt 3:<\/em><\/p>\n

    Ab zum rechten Teil des Baumes. Knoten G ist erstes Kind von D und wird sein linker Nachfolger (R1). Knoten G hat zwei Br\u00fcder, die seine rechten Nachfolger werden (R2).<\/p>\n

    \"\"<\/div>\n

    Schritt 4:<\/em><\/p>\n

    Bleiben die letzten zwei Knoten. J ist erster Sohn von H und wird sein linker Nachfolger (R1) und hat einen Bruder K, der sein rechter Nachfolger wird (R2).<\/p>\n

    \"\"<\/div>\n

    Das ist der finale Baum.<\/p>\n

    Meiner Meinung nach ist die gr\u00f6\u00dfte Denkblockade die Anwendung von R2. Denn „Br\u00fcder werden rechte Nachfolger<\/em>“ ist einfach gesagt, aber wenn der Knoten zwei Br\u00fcder hat, wer genau wird Nachfolger und wie sieht der Baum aus?<\/p>\n

    Hier sollte man einfach die Br\u00fcder auf einer Ebene belassen (siehe G, H und I) und sie einfach mit Pfeilen nach rechts verbinden. Den Teilbaum ist der n\u00e4chsten Ebene (J und K) l\u00e4sst man zun\u00e4chst wie er ist, um ihn im n\u00e4chsten Schritt dann bearbeiten zu k\u00f6nnen. Das hilft ungemein, wenn man unter Zeitdruck B\u00e4ume malen muss.<\/p>\n

    Traversierung<\/h2>\n

    Im Rahmen meiner Vorbereitungen auf die Klausur bin ich mangels \u00dcbungen zu Bin\u00e4rb\u00e4umen und Traversierung in Pre-, Post- und InOrder auf folgende Seite, die ich euch nicht vorenthalten m\u00f6chte. Tolle \u00dcbungsm\u00f6glichkeiten:<\/p>\n

    http:\/\/www.eex-online.de\/informatik\/binaerbaum.html<\/p>\n","protected":false},"excerpt":{"rendered":"

    Erstellen von Bin\u00e4rb\u00e4umen aus B\u00e4umen der Ordnung $$k$$ Leider habe ich meine Bachelor-Unterlagen verlegt und musste mich f\u00fcr die Klausur f\u00fcr das Thema durch das Skript w\u00fchlen. Die Anleitung zur Baumtransformation beschr\u00e4nkt sich hier auf zwei richtige S\u00e4tze: R1: S\u00f6hne von Knoten sind linke Nachfolger R2: Br\u00fcder von Knoten sind rechte Nachfolger Soweit so korrekt. … <\/p>\n

    \u201e32561: Erstellung und Traversierung von\/in Bin\u00e4rb\u00e4umen\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-3014","post","type-post","status-publish","format-standard","hentry","category-fernuni"],"_links":{"self":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/3014","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3014"}],"version-history":[{"count":6,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/3014\/revisions"}],"predecessor-version":[{"id":3139,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/3014\/revisions\/3139"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3014"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3014"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3014"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}