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"
<johnsmith@microsoft.com> 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