Binary tree implementation in batch (and other data structures?)

Discussion forum for all Windows batch related topics.

Moderator: DosItHelp

Post Reply
Message
Author
npocmaka_
Posts: 512
Joined: 24 Jun 2013 17:10
Location: Bulgaria
Contact:

Binary tree implementation in batch (and other data structures?)

#1 Post by npocmaka_ » 07 Jan 2017 15:52

I think I saw somewhere here some data structures implemented by Aacini in pure batch(?)

Here's an attempt to create a binary tree (with holding only numbers and without safety checks).
Only insert and find method (now I'm wondering how to implement delete)

Code: Select all

@echo off
setlocal enableDelayedExpansion

:::--- some tests -----
call ::insert test_tree6 1
call ::insert test_tree6 5
call ::insert test_tree6 8
call ::insert test_tree6 9999

color
echo searching for value 8
call ::find test_tree6 8
echo %errorlevel% - if 0 element is found
echo searching for value 123
call ::find test_tree6 123
echo %errorlevel% - if 1 element is not found
set test_tree6
::::::::::::::::::::::::::::::

exit /b 0


:find three_name value
setlocal enableDelayedExpansion
set /a value=%~2
set node=%1

if %value% equ !%1! (
   endlocal & (
      echo %1
      exit /b 0
   )
)


if %value% GTR !%1! (
   if defined %1r (
      endlocal & (
         call ::find %1r %value%
      )
   ) else (
      endlocal & exit /b 1
   )
)

if %value% LSS !%1! (
   if defined %1l (
      endlocal & (
         call ::find %1l %value%
      )
   ) else (
      endlocal & exit /b 1
   )
)


exit /b



:insert three_name value
setlocal
::set "three_name=%~1"
set /a value=%~2

if not defined %~1 (
   endlocal & (
      set "%~1=%value%"
      exit /b 0
   )
)

if %value% GEQ %~1r (
 if not defined  %~1r (
   endlocal & (
      set %~1r=%value%
      exit /b 0
   )
  ) else (
   endlocal & (
      call ::insert %~1r %value%
      rem exit /b 0
   )
  )
)

if %value% LSS %~1l (
  if not defined  %~1l (
   endlocal & (
      set %~1l=%value%
      exit /b 0
   )
   ) else (
   endlocal & (
      call ::insert %~1r %value%
      rem exit /b 0
   )
   )
)

exit /b 0

:delete




As batch files does not support things like objects or structures I'm just using the tree name as the root variable name (e.g. test_tree). The less elements go to 'left' and test_treel variable is created for the bigger elements test_treer and so on. And these variable names are used as root elements in the next recursion calls.

Some things like calculating the tree depth will be pretty easy in this case as you'll need the length of the name biggest variable associated with this tree.
Or number of the nodes will require to count all variables associated with the tree.

At the moment balancing a tree looks like mission impossible...

As for delete a node - it should be fairly easy (I think). If I want to delete test_treelrrl element in theory I'll have delete the last L for all elements under that node.

Aacini
Expert
Posts: 1885
Joined: 06 Dec 2011 22:15
Location: México City, México
Contact:

Re: Binary tree implementation in batch (and other data structures?)

#2 Post by Aacini » 07 Jan 2017 17:17

Take a look at this thread, below 2- STRUCTURES AND LINKED LISTS IN BATCH FILES

Antonio

Aacini
Expert
Posts: 1885
Joined: 06 Dec 2011 22:15
Location: México City, México
Contact:

Re: Binary tree implementation in batch (and other data structures?)

#3 Post by Aacini » 07 Jan 2017 21:00

Ok. Here it is my own example of an ordered binary tree:

Code: Select all

@echo off
setlocal EnableDelayedExpansion

set "letter=ABCDEFGHIJKLMNOPQRSTUVWXYZ"

< NUL (for /L %%i in (1,1,10) do (
   set /A num=!random!%%10
   for %%n in (!num!) do set "char=!letter:~%%n,1!"
   set /P "=Insert !char!: "
   call :insert !char!
   if errorlevel 1 (echo Duplicated data) else echo Data inserted
))

echo/
set node[
echo/

< NUL (for /L %%i in (1,1,10) do (
   set /A num=!random!%%12
   for %%n in (!num!) do set "char=!letter:~%%n,1!"
   set /P "=Search !char!: "
   call :find !char!
   if errorlevel 1 (echo Not found) else echo Found
))

goto :EOF


:insert value
set "value=%1"
set "node=0"
:insertLoop
if not defined node[%node%].data (
   set "node[%node%].data=%value%"
   set "heap=%node%"
   exit /B 0
)
if %value% equ !node[%node%].data! exit /B 1
if %value% lss !node[%node%].data! (
   if defined node[%node%].left (
      set /A "node=node[%node%].left"
   ) else (
      set /A "node=heap+1, node[%node%].left=node"
   )
) else (
   if defined node[%node%].right (
      set /A "node=node[%node%].right"
   ) else (
      set /A "node=heap+1, node[%node%].right=node"
   )
)
goto :insertLoop


:find value
set "value=%1"
set "node=0"
:findLoop
if not defined node[%node%].data exit /B 1
if %value% equ !node[%node%].data! exit /B 0
if %value% lss !node[%node%].data! (
   if defined node[%node%].left (
      set /A "node=node[%node%].left"
      goto :findLoop
   )
) else (
   if defined node[%node%].right (
      set /A "node=node[%node%].right"
      goto :findLoop
   )
)
exit /B 1

Output example:

Code: Select all

Insert G: Data inserted
Insert J: Data inserted
Insert C: Data inserted
Insert H: Data inserted
Insert C: Duplicated data
Insert E: Data inserted
Insert A: Data inserted
Insert F: Data inserted
Insert A: Duplicated data
Insert A: Duplicated data

node[0].data=G
node[0].left=2
node[0].right=1
node[1].data=J
node[1].left=3
node[2].data=C
node[2].left=5
node[2].right=4
node[3].data=H
node[4].data=E
node[4].right=6
node[5].data=A
node[6].data=F

Search A: Found
Search H: Found
Search A: Found
Search D: Not found
Search K: Not found
Search G: Found
Search E: Found
Search J: Found
Search E: Found
Search J: Found

Antonio

Aacini
Expert
Posts: 1885
Joined: 06 Dec 2011 22:15
Location: México City, México
Contact:

Re: Binary tree implementation in batch (and other data structures?)

#4 Post by Aacini » 08 Jan 2017 20:15

I implemented the display of the binary tree in a pleasant, aligned way! :D

Code: Select all

@echo off
setlocal EnableDelayedExpansion

set "letter=ABCDEFGHIJKLMNOPQRSTUVWXYZ"

cls
< NUL (for /L %%i in (1,1,26) do (
   set /A num=!random!%%26
   for %%n in (!num!) do set "char=!letter:~%%n,1!"
   set /P "=Insert !char!: "
   call :insert !char!
   if errorlevel 1 (echo Duplicate data) else echo Data inserted
))

echo/
set node[
echo/

< NUL (for /L %%i in (1,1,10) do (
   set /A num=!random!%%26
   for %%n in (!num!) do set "char=!letter:~%%n,1!"
   set /P "=Search !char!: "
   call :find !char!
   if errorlevel 1 (echo Not found) else echo Found
))

echo/
call :showTree
goto :EOF


:insert value
set "value=%1"
set "node=0"
:insertLoop
if not defined node[%node%].data (
   set "node[%node%].data=%value%"
   set "heap=%node%"
   exit /B 0
)
if %value% equ !node[%node%].data! exit /B 1
if %value% lss !node[%node%].data! (
   if defined node[%node%].left (
      set /A "node=node[%node%].left"
   ) else (
      set /A "node=heap+1, node[%node%].left=node"
   )
) else (
   if defined node[%node%].right (
      set /A "node=node[%node%].right"
   ) else (
      set /A "node=heap+1, node[%node%].right=node"
   )
)
goto :insertLoop


:find value
set "value=%1"
set "node=0"
:findLoop
if not defined node[%node%].data exit /B 1
if %value% equ !node[%node%].data! exit /B 0
if %value% lss !node[%node%].data! (
   if defined node[%node%].left (
      set /A "node=node[%node%].left"
      goto :findLoop
   )
) else (
   if defined node[%node%].right (
      set /A "node=node[%node%].right"
      goto :findLoop
   )
)
exit /B 1


:showTree
for /F "delims==" %%a in ('set leve 2^>NUL') do set "%%a="
setlocal EnableDelayedExpansion
set /A "node=0, thisLevel=-1, level=-1"
call :getLevel
set /A "node=0, thisLevel=-1"
set /P "=Please wait" < NUL
call :fillTree
echo/

echo/
echo Binary Tree (level=%level%):
echo/
set /A "node=heap+1"
set "node[%node%].data=_"
set "spaces= "
for /L %%i in (1,1,%level%) do set "spaces=!spaces!!spaces!"
for /L %%i in (0,1,%level%) do (
   set /A "left=(1<<(level-%%i))-1, sep=(1<<(level-%%i+1))-1"
   for %%n in (!left!) do set "sep0=!spaces:~0,%%n!"
   for %%n in (!sep!) do set "sep1=!spaces:~0,%%n!"
   set "line="
   for %%j in (!level[%%i]!) do (
      set "line=!line!!sep0!!node[%%j].data!"
      set "sep0=!sep1!"
   )
   echo !line!
)
exit /B


:getLevel
setlocal EnableDelayedExpansion
if defined node[%node%].data (

   set /A thisLevel+=1
   if !thisLevel! gtr %level% set "level=!thisLevel!"

   if defined node[%node%].left (
      set /A "node=node[%node%].left"
      call :getLevel
   )

   if defined node[%node%].right (
      set /A "node=node[%node%].right"
      call :getLevel
   )

)
endlocal & set "level=%level%"
exit /B


:fillTree
set /P "=." < NUL
setlocal EnableDelayedExpansion
set /A thisLevel+=1

if %thisLevel% leq %level% (

   set "level[%thisLevel%]=!level[%thisLevel%]! %node%"

   if defined node[%node%].left (
      set /A "node=node[%node%].left"
   ) else (
      set /A "node=heap+1"
   )
   call :fillTree

   if defined node[%node%].right (
      set /A "node=node[%node%].right"
   ) else (
      set /A "node=heap+1"
   )
   call :fillTree

)
set "leve=1"
for /F "delims=" %%a in ('set leve') do (
   if defined leve (endlocal) else set "%%a"
)
exit /B

Here there are some examples of the binary tree output:

Code: Select all

Binary Tree (level=5):

                               E
               D                               P
       C               _               K               X
   _       _       _       _       J       M       U       Z
 _   _   _   _   _   _   _   _   I   _   L   O   S   V   _   _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ H _ _ _ _ _ _ _ Q _ _ _ _ _ _ _


Binary Tree (level=5):

                               G
               C                               P
       B               D               K               R
   A       _       _       F       J       M       Q       U
 _   _   _   _   _   _   E   _   _   _   L   _   _   _   T   V
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ S _ _ X


Binary Tree (level=6):

                                                               O
                               N                                                               T
               K                               _                               S                               Y
       B               M               _               _               R               _               _               Z
   _       I       L       _       _       _       _       _       Q       _       _       _       _       _       _       _
 _   _   E   J   _   _   _   _   _   _   _   _   _   _   _   _   P   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _
_ _ _ _ C G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _


Binary Tree (level=6):

                                                               J
                               G                                                               O
               F                               H                               M                               S
       D               _               _               I               K               _               Q               U
   _       _       _       _       _       _       _       _       _       L       _       _       P       _       _       W
 _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   V   Z
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ X _

Antonio

npocmaka_
Posts: 512
Joined: 24 Jun 2013 17:10
Location: Bulgaria
Contact:

Re: Binary tree implementation in batch (and other data structures?)

#5 Post by npocmaka_ » 08 Jan 2017 20:39

That's impressive , tough I still hadn't checked your code :)

Post Reply