------------------------------------------------------------------------------- - SECTION ONE PART A PART 1 - (The Regular Wrox Press article) ---------------- ------------------------------------------------------------------------------- Here's a PowerBasic program for all of you PB users.. I wish I had it but I spent my money on Turbo Pascal, bah... ;-) Binary Tree Search Earlier in the book we used a binary tree in the pyramidal sort to help order an array. The unordered keys of the array were partially sorted into a heap, using HeapSort. In this section the order of the elements in the array is already fixed, although not necessarily in order of the magnitude of the key. What we have to do is assign these elements (for example, the characters of a word) to the nodes of a binary tree, so that they are searchable. Representing data in the form of a binary tree is convenient when you are constantly adding new records, or deleting records or parts of records from the array. But there is very little point in using the binary tree search on a strictly ordered array, because changing one record would cause many others to move, in order to retain the order. The binary tree we use here differs subtly from that used in the pyramid sort. In the pyramid sort, the keys are ordered by magnitude, within each branch traced from the root node. In the binary search tree an arbitrary node A(i) has a 'left' and a 'right' son, as before, but they are related by the following conditions: A(L) < A(i); A(R >= A(i) So a left son has a key of lesser magnitude than its father, while the right son has a key of greater magnitude. This gives us a tree consisting of partially ordered elements: node A (i) / \ / \ / \ left right son A (L) son A (R) The algorithm for building a tree, with the keys 14, 3, 27, 19, 5, 4, 1, 16 is as follows. The first key element, 14 in our case, is set as a root node. The next value, 3, being less than 14, is inserted in the tree as the left "son". Since 27 is greater than 14 it is inserted into the tree as the right "son" of 14. The number 19 is bigger than 14, and so would normally be the right "son" of 14. But we already have 27 in its place, so we go down another level, and compare 19 to l be the left son of "27", and therefore one of 14's "grandsons". If you look at our next program \CHAP5\CH5_18.BAS (on the disk accompanying the book) you'll find a sub-routine Tree which constructs a binary search tree for the array TreeArray. Each record is a node of the tree. The variable i, as the ordinal number, or index, of a record in the array, corresponds to the number of the node. A record must contain the three fields used by the sub-program: Info A key field of any type, e.g. String or Integer. Left & Right Integer type fields where the numbers of the nodes corresponding to the left and right sons are formed while the tree is being created. The sub-routine fills the fields Left and Right according to the aforementioned algorithm. Here is the subroutine that performs this task: SUB Tree FOR i = 2 TO MaxRec 'i-number of a pass q = 1 ' start value of the index of a mimimum key DO p = q IF TreeArray(i).Info < TreeArray(p).Info THEN q = TreeArray(p).Left ELSE q = TreeArray(p).Right END IF LOOP WHILE q IF TreeArray(i).Info < TreeArray(p).Info THEN TreeArray(p).Left = i ELSE TreeArray(p).Right = i END IF NEXT i END SUB The following Search subroutine sequentially compares the key KeyTree with the key fields of the records. The index of a record (the node number) is selected from the fields Left or Right depending on the result of the comparison. SUB Search PRINT PRINT " SEARCH ON THE TREE" INPUT "Name of the city"; KeyTree p = 1 ' start value of the index of the minimum key DO IF KeyTree = TreeArray(p).Info THEN PRINT PRINT " Search is successful" PRINT p; TreeArray(p).Info; PRINT " Year of foundation: "; TreeArray(p).Date; EXIT DO END IF IF KeyTree < TreeArray(p).Info THEN p = TreeArray(p).Left ELSE p = TreeArray(p).Richt END IF LOOP WHILE p IF p = 0 THEN PRINT "Record not found" END IF END SUB We'll demonstrate how useful these sub-routines are with an example which searches for the first chronicled mention of a city. The demo program \CHAP\CH5_19.BAS (also on the disk with the book) uses the following sub-program together with the ones we've already described: InArray inputs the unordered information about the cities from the DATA into an array. PrintArray displays the values of the nodes (names of the cities) in their tree order, and also the values of their left and right sons. The tree search algorithm can be used to our advantage for developing sub- -programs to add or remove records. We have seen in this section how, given an array which will regularly have records added to it, or whose initial order we want to keep, we can still order its keys by relative magnitude in order to perform a binary tree search, and locate them quickly. That was from Wrox Press. They are a computer book publishing firm based in Birmingham UK.. If you want to contact Wrox Press then use snail mail to: Editorial : Unit 16, 20 James Road, Tyseley, Birmingham, B28 0EE, UK Or in America you could try: Marketing : 2710 W. Touhy, Chicago, Illinois, 60645, USA Or via the internet you can: Internet : adrians@wrox.com or try our Web site : WWW.WROX.COM Cool book. Learn how to program machine code in BASIC, loads of graphics stuff , program designing, programming the SB.... ;-) Great! -------------------------------------------------------- * EDITOR'S NOTE: * This article was originally printed in Peter Cooper's BASIX Fanzine, * Issue #3 from December 1995.