Liste zu einem binären Baum umformen

[Medium]

Das ist doch schon fast fertig. Du müsstest dann nur noch wenn eine Liste zerteilt wird, je eine Hälfte an einen Baumknoten hängen der dann das Token bzw. den Wert enthält an dem zerteilt wurde. Das ganze rekursiv durchexerzieren bis nur noch 1-elementige Listen rumbaumeln, die du dann auch noch in einen Baumknoten ohne Nachfolger umwandeln könntest.

Es macht zudem Sinn entweder die Liste gleich mit den Baumstrukturen zu basteln (z.B. immer nur "links" anhängen), oder aber etwas OOP ins Spiel zu bringen in dem du etwas der Art nimmst:

Delphi-Quellcode:

type
  TElement = class
  private
    FValue: String;
    FToken: TToken;
  public
    property Value: String read FValue write FValue;
    property Token: String read FToken write FToken;
  end;

  TElementArray = array[0..1] of TElement;

  TElementListNode = class(TElement)
  private
    FNext: TElementListNode;
  public
    property Next: TElementListNode read FNext write FNext;
  end;

  TElementTreeNode = class(TElement)
  private
    FNext: TElementArray ;
  public
    property Next: TElementArray read FNext write FNext;
  end;

Die Verbindungen im Baumknoten könnte man zudem auch noch als Liste statt als Array ausführen, und man könnte Baum- und Listenknoten in eine weitere Klasse verpacken die dann diverse Operationen zur Verfügung stellt, etc. Da sind dann der Phantasie wenig Grenzen gesetzt wie weit man es treiben könnte wenn man wollte, wobei ein gemeinsamer Vorfahre in dieser Art schon einiges vereinfachen könnte, da man dann ja auf die Nutzdaten beider Knotenklassen über das selbe Interface heran kommt ohne große Spagate.