From: pandeng@telepath.com (Steve Schafer (TeamB)) Subject: Re: Binary Search Tree Tutorial Date: 01 Aug 1999 00:00:00 GMT Message-ID: <37af8bd1.416105680@90.0.0.40> Content-Transfer-Encoding: 7bit References: <7nuds1\$e2014@forums.borland.com> Content-Type: text/plain; charset=us-ascii Organization: TeamB Mime-Version: 1.0 Reply-To: pandeng@telepath.com Newsgroups: borland.public.turbopascal On Sat, 31 Jul 1999 11:03:23 +0200, "John Smith" wrote: >Does anyone know where I can find a tutorial on the net for binary search >trees and traversing them using recursion? There are "binary trees," and there is a search method called "binary searching." But I don't know quite what you mean by "binary search trees." Binary search: Assuming your data are ordered according to some key, and are stored in an array A of length N, the basic search algorithm goes like this: begin I <- N div 2 Done <- False repeat if A[N] = SearchTarget then Done <- True else if A[N] < SearchTarget then I <- I + I div 2 else I <- I - I div 2 until Done This assumes that the target exists; you'll have to add some additional code to terminate the loop if the target can't be found. Binary tree: The basic binary tree data structure looks like this: type PNode = ^TNode; TNode = record Value: TSomeType; { whatever type is appropriate } LeftChild, RightChild: PNode; end; The manner of adding and deleting nodes to a binary tree depends a lot on what you're storing, so I can't cover that here without more information. Recursively traversing a binary tree is quite simple: procedure Traverse(Tree: PNode); begin if Tree^.LeftChild <> nil then Traverse(Tree^.LeftChild); Process(Tree^.Value); { "Process" does something with the node } if Tree^.RightChild <> nil then Traverse(Tree^.RightChild); end; -Steve