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.
