Pascal, Strings in A Binary Search tree

[Adz52]

Hi there i have the task of making a progam that sorts out a list of words from a text file, i need to take the text file and then take the words and but then in a binary search tree, then i need to display them on screen in alphbetical order

, any help would be great ,

so far i have made an empty tree but that is where i get stuck thanks

[Duoas]

Are you using Delphi or Pascal? (It makes a difference.)

All binary trees are just a fancy form of linked-list, so there is no reason why you can't include a string in your node record.

In Delphi:

type
  pNode = ^tNode;
  tNode = record
    word: string;
    left, right: pNode
    end;

In Pascal, I'd use a Schema type:

type
  pNode = ^tNode;
  tNode( wordsize: integer ) = record
    word: string( wordsize );
    left, right: pNode
    end;

If you can't use Schemata, then just make a simple character array:

type
  pNode = ^tNode;
  tNode = record
    word: array[ 1..80 ] of char;
    left, right: pNode
    end;

Hope this helps.

[Adz52]

I am using Delphi , thanks for the help but i need to use a binary search tree with the type declerations of

type
  WordTree = ^WordTreeDesc;
  WordTreeDesc = record 
                   word: String;
                   lineNumbers: LineLists.LineList;
                   left, right: WordTree
                 end;

how can i take the words from the text file and enter them into the tree sort them alphabetically
cheers

[Duoas]

I don't understand why you would need a binary tree to store an ordered list of words.

Can you give a short example of what you are trying to do?

[Adz52]

the whole program is in three units,

A) the main control, main menu
2) enters the word that are in part 3 into a binary search tree
3) reads names for a list and then stores them as a link list, converts it alapbetical order

that is how it is meant to be stored

the program is meant to take the word from a text file and then print to screen the words in alphebetical order, and also which line the appear from e.g

the shop is good
this is not good

results:=
good 2,2
is 2,2
not 2
shop 1
the 1
this 2

[Duoas]

I'm sorry, but I'm really tired right now and maybe I'm just missing something.

It looks to me like all you have is an ordered list.

Do you mean to have just a simple form of associative container, for example:

type
  p_integer   = ^integer;
  p_word_node = ^t_word_node;
  t_word_node = record
    word_key:   string;
    word_value: p_integer;
    next_node:  p_word_node
    end;

This is basically a degenerate tree, which is semantically the same as a single-linked list:

p_word_node = ^t_word_node;
  t_word_node = record
    word_key:   string;
    word_value: integer;  // the value is now part of the node, instead of a child
    next_node:  p_word_node
    end;

Did that make sense?

[Adz52]

here is the brief

You are required to construct a program that will generate a cross-reference listing of a text provided in a file. It should display each line of the text preceded by its line number (starting from 1) and then display a list, in alphabetic order, of each word in the text and the line numbers of the lines on which it appears. The line numbers should appear in ascending order and, if a word appears on a line of the text more than once, then the line number should appear only once for that word in the cross-reference list.

it contains two units, one the holds the inforamtion form the text file in a link lists and the orders it, then passes to the bianry tree , to store it ,
from there it is displyed onto the screen .

i have made the three units alrady but having huge difficulties with the coding of the tree and the passing of data

[Duoas]

Ah. This is called an "associative list", which is a degenerate form of S-expression.

Remember that a binary tree is nothing more than a collection of nodes where each node links to two other nodes (a left node and a right node) and optionally contains a value. In a true binary tree, a value would be a leaf node itself, and branch nodes would not contain anything but links.

The best way I can answer your question without just giving you the answer is that you should get out a piece of paper and draw your binary tree. Forgive the ASCII art, but this is what I drew:

word 1-------------------------------line 1--END
  |                                    |
word 2----------------line 1--END    line 2--END
  |                     |              |
word 3--line 1--END   line 2--END    line 3--END
  |       |             |              |
 END    line 2--END    END           line 4--END
          |                            |
        line 3                        END
          |
         END

For word nodes, in each case the left branch leads to the next word, while the right branch leads to line number nodes. And again, for line number nodes, each left branch leads to the next line number and the right branch is unused.

Hope this helps.