modify a record in a tree

[ringo]

hi i'm doing a little dictionnary ,and i want to add a procedure that modifies a word by deleting it and inserting the new one with new spelling.
i want to use a tree. how can i proceed ?
anybody have any suggestion to help me please ?

here is my beginning

Quote:

type Entry :
record
english : string( 50 )
definition : array 1..10 of string( 100 )
n : int
end record

[Martin]

Well, are you familiar with binary search trees? For now, don't worry about making the tree balanced, as balancing a search tree can seem complicated at first.

Using numbers, here is how a binary search tree works:

We insert a value, let's say 10. Since the tree is initially empty, this becomes the root of the tree. Our tree now looks like this:

code:

10

Now, we insert a value 5. Because 5 is less than 10, it goes to the left of 10. Our tree now looks like this:

code:

10    /  5

Now, we insert the value 7. 7 is less than 10, so it goes to the left of 10. 7 is greater than 5 though, so it goes to the right of 5. Our tree looks like this:

code:

10    /  5    \     7

The basic idea is that whenever you want to insert a value into the tree, you do the following:

code:

Make a pointer to the root of the tree, call it current. set value to the value you want to insert. loop    if current.data > value then       if current.left not= NULL then            current = current.left  %move down the tree       else %it's null, insert it here            %insert the new node to the left            exit       end if     elsif current.data < value then        %do the same as above, only moving right         ...     end if end loop

Searching is done in a similar fasion to inserting. Now, to delete an element in a tree, simply find it in a tree, get rid of it, and reinsert all of the values that would get severed.

[ringo]

thank you martin , i'm working on it with this method

[ringo]

sorry for my english
hi i want to change the spelling of a word without getting rid of the definitions , is it possible without a delete function and without loading the entry record in an array ?
or if someone have a better idea ,it would be good
thank you

here is my updated code and i'm lost with the proc modify

Quote:

proc Wait
put "Press a key to continue ..." ..
var s : string( 1 )
getch( s )
put skip
end Wait

type entry :
record
english : string( 30 )
definition : array 1..5 of string( 50 )
n : int
end record

function emptyentry : entry
var RetVal : entry
RetVal.english := ""
for i:lower( RetVal.definition )..upper( RetVal.definition )
RetVal.definition( i ) := ""
end for
RetVal.n := 0
result RetVal
end emptyentry

function valid( e : entry ) : boolean
result e.english not= ""
end valid

function GetEntry( bGetInfo : boolean ) : entry
var e : entry := emptyentry
put "enter the english word : " ..
get e.english:*
if bGetInfo and valid( e ) then
var i : int := 1
loop
exit when i > upper( e.definition )
var d : string( 100 )
put "Enter the definition no ", i, "- " ..
get d:*
exit when d = ""
e.definition( i ) := d
i += 1
end loop
end if
result e
end GetEntry

procedure PutEntry( e : entry )
if valid( e ) then
var i : int := 1
put e.english
put "Definitions:"
loop
exit when i > upper( e.definition )
exit when e.definition( i ) = ""
put "\t", i, "- ", e.definition( i )
i += 1
end loop
end if
end PutEntry

type DocEntry :
record
info : entry
g : pointer to DocEntry
d : pointer to DocEntry
end record

type DocType : pointer to DocEntry

function Empty: DocType
result nil
end Empty

function isnil( Doc : DocType ) : boolean
result Doc = nil
end isnil

function root( Doc : DocType ) : entry
pre not isnil( Doc )
result Doc->info
end root

function left( Doc : DocType ) : DocType
pre not isnil( Doc )
result Doc->g
end left

function right( Doc : DocType ) : DocType
pre not isnil( Doc )
result Doc->d
end right

function cons( e : entry, g, d : DocType ) : DocType
var nn : DocType
new nn
nn->info := e
nn->g := g
nn->d := d
result nn
end cons

function insert( e : entry, Doc : DocType ) : DocType
if Doc = nil then
result cons( e, Doc, Doc )
elsif e.english <= Doc->info.english then
result cons( Doc->info, insert( e, Doc->g ), Doc->d )
else
result cons( Doc->info, Doc->g, insert( e, Doc->d ) )
end if
end insert

function GetBow( e : entry, Doc : DocType ) : DocType
if Doc = nil or Doc->info.english = e.english then
result Doc
elsif Doc->info.english > e.english then
result GetBow( e, Doc->g )
else
result GetBow( e, Doc->d )
end if
end GetBow

procedure FreeDoc( Doc : DocType )
if Doc not= nil then
var n : DocType := Doc
FreeDoc( n->g )
FreeDoc( n->d )
free n
end if
end FreeDoc

function depth( Doc : DocType ) : int
if Doc = nil then
result 0
else
result max( depth( Doc->g ), depth( Doc->d ) ) + 1
end if
end depth


const DicoFile : string := "C:\\Documents and Settings\\...\\dico.txt"


function Initialise : DocType
var Doc : DocType := Empty


var nFile : int
open: nFile, DicoFile, read
if nFile not= 0 then
loop
exit when eof( nFile )
var e : entry
read: nFile, e
Doc := insert( e, Doc )
end loop
close: nFile
end if
put "depth of the document is ", depth( Doc )
Wait
result Doc
end Initialise

procedure SaveDocument( Doc : DocType, nFile : int )
if not isnil( Doc ) then
var e : entry := root( Doc )
write: nFile, e
SaveDocument( Doc->g, nFile )
SaveDocument( Doc->d, nFile )
end if
end SaveDocument

procedure EditDocument( Doc : DocType )
if not isnil( Doc ) then
EditDocument( Doc->g )
PutEntry( Doc->info )
EditDocument( Doc->d )
end if
end EditDocument


procedure Quit( Doc : DocType )
put "Exit"
var nFile : int

open: nFile, DicoFile, write
if nFile not= 0 then
SaveDocument( Doc, nFile )
close: nFile
end if
FreeDoc( Doc )
end Quit

procedure add( var Doc : DocType )

loop
var e : entry := GetEntry( true )
exit when not valid( e )
Doc := insert( e, Doc )
end loop
end add

procedure display( Doc : DocType )

EditDocument( Doc )
loop
var e : entry := GetEntry( false )
exit when not valid( e )
var bow : DocType := GetBow( e, Doc )

if isnil( bow ) then
put "not found "
Wait
else
PutEntry( root( bow ) )
end if
end loop
end display

%-----------------------------------MODIFY--------------------
procedure modify(var Doc:DocType)
var nFile:int
open:nFile,DicoFile,write,mod

EditDocument(Doc)
var k:entry

var e:entry:=GetEntry(true)


put "Enter new Name: " ..
get k.english: *
for i : 1 .. (15 - length (k.english))
k.english:= e.english+ ""



end for
Doc:=insert(k,Doc)
close :nFile

end modify
%-------------------------------------

procedure putMenu
cls
put "1-display"
put "2-add a word"
put "3-modify"
put "4-quit"
put "your choice : " ..
end putMenu

function choice : int
loop
putMenu
var choice : string( 1 )
getch( choice )
put skip
case choice( 1 ) of
label '1':
result 1
label '2':
result 2
label '3':
result 3
label '4':
result 0
label:
end case
end loop
end choice


var Document : DocType := Initialise


loop
var nChoice : int := choice
exit when nChoice = 0
case nChoice of
label 1:
display( Document )
label 2:
add( Document )
label 3:
modify(Document)
label:
end case
Wait
end loop


Quit( Document )

[Martin]

Don't modify a record, just delete it and insert the new record into the tree. Modifying it runs the potential of ruining your tree.

I'll check it out more when I get home.

[ringo]

thank u martin

i know how to delete the whole text file ,and to insert a new record ,
but i don't know how to delete only one record ????
i have some problems when i open the file to write on it ,everything erase
somebody has an idea please ?