Create Binary Tree From Preorder input

[sk.Silvia]

hi there
does somebody know an algorithm for creating a binary tree from an preorder input? Thank you, i searched the web, but with no result i know the algortithm for outputing a binnar tree to an preorder output, but that isnt a much big help.

Thanks

[sk.Silvia]

so nobody? can be any combination of 2 grade of pre-post-in order input

can be also code in C, VB or any language

[alzaimar]

Hi,

Try something like this:
Divide the list into two halves. The mid element is your root.
Now do a recursive call to create a tree out of the left sub list and return the root as the left child of the above mentioned root. Do the same with the right sub list.

Delphi-Quellcode:

Procedure CreateTree (aList : TList; aLeft, aRight : Integer; Var aRoot : TNode);
Begin
  If aLeft >= aRight Then
     aRoot := aList [aLeft]
  Else Begin
     m := (aLeft + aRight) div 2;
     aRoot := aList [m];
     if m > aLeft  Then CreateTree (aList, aLeft,  m - 1, aRoot.Left);  // Not sure about this, you might have to test
     if m < aRight Then CreateTree (aList, m + 1, aRight, aRoot.Right);//                  -"-
  End
End;

One question: Why do you use something antique like a binary tree? Use Skiplists or Hashmaps for fast retrieval of keyed data, they are much much faster.

[sk.Silvia]

wooow, thats great, youare so claver, thanks a million, i had to modify the code a little bit but without you i wouldnt have a chance

Delphi-Quellcode:

  procedure TBinTree.CreateInorder(aList :TField; aLeft, aRight : Integer; Var aRoot : TBinTree);
  var m:integer;
        begin
        if aLeft>=aRight then aRoot:=TBinTree.Create(aList[aLeft],nil,nil)
                         else
                            begin
                            m:=(aLeft+aRight) div 2;
                            aRoot:=TBinTree.Create(aList[m],nil,nil);

                            if m>aLeft  then CreateInorder(aList, aLeft,  m-1, aRoot.Left);
                            if m<aRight then CreateInorder(aList, m+1, aRight, aRoot.Right);
                            end;
        end;

Call In Prog ->
BinTree.CreateInorder(TreeInput,Low(TreeInput),High(TreeInput),BinTree);

So ok, this creates a tree from an Inorder input, but lets say we have two inputs Preorder and Postorder, how can i create an tree from them?

i have to use binary tree cause of uni...but thats abit overwork (not neccessary needed to know for school), but iam trying hard to be the best and to know smt. more to be one day so clever as you again thank you

Silvi

[alzaimar]

What do you mean by 'two lists, one pre- the other one postorder' ?
If Yo have the list in reversed order, simply reverse 'left' and 'right'.

BTW: If you must deal with binary trees, ever tried AVL-Trees or Red-Black-Trees? They are self-balancing.

[sk.Silvia]

sorry, my fault, i thought you cannot create an tree only from preorder or postorder input and need them both
how would an alghoritm for preorder input look like (and for postorder its then easy)

we also learned alphabetical trees ,+-*/ tree and heap

thanks

[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;

[sk.Silvia]

i mean, lets have 1,2,3,4,5,6,7,8 as input to this code, its genarets the tree and when we read the tree by 3 types, we get this result

PreOrder :
4;2;1;3;6;5;7;8;
Inorder :
1;2;3;4;5;6;7;8; <-what was our input
Postorder :
1;3;2;5;8;7;6;4;


and now, lets have 1;3;2;5;8;7;6;4; as input

PreOrder :
5;3;1;2;7;8;6;4;
Inorder :
1;3;2;5;8;7;6;4; <-that was our input again
Postorder :
1;2;3;8;4;6;7;5;

and i will to enter a preorder 4;2;1;3;6;5;7;8; (and maybe also an Postorder 1;3;2;5;8;7;6;4; when needed) so i gen an output

PreOrder :
4;2;1;3;6;5;7;8; <-what was our input
Inorder :
1;2;3;4;5;6;7;8;
Postorder :
1;3;2;5;8;7;6;4;

Thanks