#!/bin/bash # binsort - prototype binary tree build and traverse # webshells.com/cgi-bin/web2shell/bash.cgi by J. Doug Ohmans # Copyright (C) 2006 Free Software Foundation, Inc. # This program is free software; you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation. fill () { if [ ! -e datfil ]; then touch datfil fi while read data; do let cnt=$cnt+1 field[$cnt]=$data done < datfil } append () { echo -n "Pls enter field: " while read data; do let cnt=$cnt+1 if [ "$cnt" \=\= "9" ]; then rm datfil touch datfil exit fi echo -n "Pls enter field: " if [ "$cnt" \=\= "8" ]; then echo "**Ctl-D now" echo "8-level maximum" echo "(delete datfil)" fi field[$cnt]=$data echo $data >> datfil done } spin () # non-recursive { cnt=0 count=${#field[@]} while [ "$cnt" \< "$count" ]; do zero=0 flag=0 left[$cnt]=0 right[$cnt]=0 while [ "$flag" \=\= "0" ]; do if [ "${field[$cnt]}" \> "${field[$zero]}" ]; then if [ "${right[$zero]}" \> "0" ]; then zero=${right[$zero]} else right[$zero]=$cnt let cnt=$cnt+1 flag=1 fi elif [ "${left[$zero]}" \> "0" ]; then zero=${left[$zero]} else left[$zero]=$cnt let cnt=$cnt+1 flag=1 fi done done } display () { cnt=0 echo while [ "$cnt" \< "$count" ]; do echo ${left[$cnt]}\|${field[$cnt]}\|${right[$cnt]} let cnt=$cnt+1 done } traverse () # recursive { local cnt=$1 if [ "${left[$cnt]}" \=\= "0" ] &&\ [ "${right[$cnt]}" \=\= "0" ]; then echo ${field[$cnt]} fi if [ "${left[$cnt]}" \> "0" ] &&\ [ "${right[$cnt]}" \> "0" ]; then traverse ${left[$cnt]} echo ${field[$cnt]} traverse ${right[$cnt]} fi if [ "${left[$cnt]}" \> "0" ] &&\ [ "${right[$cnt]}" \=\= "0" ]; then traverse ${left[$cnt]} echo ${field[$cnt]} fi if [ "${left[$cnt]}" \=\= "0" ] &&\ [ "${right[$cnt]}" \> "0" ]; then echo ${field[$cnt]} traverse ${right[$cnt]} fi } cnt=0 echo "**Ctl-D to exit" echo -n 'root pattern - ' read root field[0]=$root fill append spin display traverse "0" exit 0