Create Binary Tree From Preorder input

[alzaimar]

The mentioned algorithm constructs a perfectly balanced tree out of *any* list, no matter how it is sorted.
If the list is sorted in ascending order, the resulting tree is exactly what you expect: The left part is always smaller than the root, the right side is larger.

Now, if the list is sorted in descending order, but you want to remain the left-right order, you have to reverse the 'left' and 'right' parts of the algorithm. Here's how it would look like to create a binary tree from a list in reverse order (e.g.: (5,4,3,2,1):

Delphi-Quellcode:

procedure TBinTree.CreateDescending (aList :TField; aLeft, aRight : Integer; Var aRoot : TBinTree);
var 
  m:integer;

begin
  if aLeft>=aRight then 
    aRoot:=TBinTree.Create(aList1[aLeft],nil,nil)
  else begin
     m:=(aLeft+aRight) div 2;
     aRoot:=TBinTree.Create(aList [m],nil,nil);
     if m > aLeft Then CreateDescending (aList, aLeft, m-1, aRoot.Right); 
     if m < aRight Then CreateDeseinding(aList, m+1, aRight, aRoot.Left);
  end;
end;