![]() |
Create Binary Tree From Preorder input
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 |
Re: Create Binary Tree From Preorder input
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 |
Re: Create Binary Tree From Preorder input
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:
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.
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; |
Re: Create Binary Tree From Preorder input
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:
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?
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); 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 :kiss: Silvi |
Re: Create Binary Tree From Preorder input
What do you mean by 'two lists, one pre- the other one postorder' :gruebel: ?
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. |
Re: Create Binary Tree From Preorder input
sorry, my fault, i thought you cannot create an tree only from preorder or postorder input and need them both :cat:
how would an alghoritm for preorder input look like (and for postorder its then easy) we also learned alphabetical trees ,+-*/ tree and heap thanks |
Re: Create Binary Tree From Preorder input
:gruebel: 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; |
Re: Create Binary Tree From Preorder input
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 |
Alle Zeitangaben in WEZ +1. Es ist jetzt 14:36 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz