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