Task

Implement a binary tree where each node carries an integer,   and implement:

   pre-order,
   in-order, 
   post-order,     and 
   level-order   traversal. 


Use those traversals to output the following tree:

         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9

The correct output should look like this:

preorder:    1 2 4 7 5 3 6 8 9
inorder:     7 4 2 5 1 8 6 9 3
postorder:   7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9



See also

   Wikipedia article:   Tree traversal.


left=()
right=()
value=()
 
# node node#, left#, right#, value
#
# if value is empty, use node#
 
node() {
  nx=${1:-'Missing node index'}
  leftx=${2}
  rightx=${3}
  val=${4:-$1}
  value[$nx]="$val"
  left[$nx]="$leftx"
  right[$nx]="$rightx"
}
 
# define the tree
 
node 1 2 3
node 2 4 5
node 3 6
node 4 7
node 5
node 6 8 9
node 7
node 8
node 9
 
# walk NODE# ORDER
 
walk() {
  local nx=${1-"Missing index"}
  shift
  for branch in "$@" ; do
    case "$branch" in
      left)  if [[ "${left[$nx]}" ]];      then walk ${left[$nx]}  $@ ; fi ;;
      right) if [[ "${right[$nx]}" ]];     then walk ${right[$nx]} $@ ; fi ;;
      self)  printf "%d " "${value[$nx]}"  ;;
    esac
  done
}
 
apush() {
  local var="$1"
  eval "$var=( \"\${$var[@]}\" \"$2\" )"
}
 
showname() {
  printf "%-12s " "$1:"
}
 
showdata() {
  showname "$1"
  shift
  walk "$@"
  echo ''
}
 
preorder()  { showdata $FUNCNAME $1 self left right ; }
inorder()   { showdata $FUNCNAME $1 left self right ; }
postorder() { showdata $FUNCNAME $1 left right self ; }
levelorder() {
  showname 'level-order'
  queue=( $1 )
  x=0
  while [[ $x < ${#queue[*]} ]]; do
    value="${queue[$x]}"
    printf "%d " "$value"
    for more in "${left[$value]}" "${right[$value]}" ; do
      if [[ -n "$more" ]]; then
	apush queue "$more"
      fi
    done
    : $((x++))
  done
  echo ''
}
 
preorder   1
inorder    1
postorder  1
levelorder 1