[R] binary tree construction in R

[Norm Matloff]

MK wrote:

> Hi all, 
>
> I'm very new to R and I'm trying to construct a threaded binary tree using
> recursive functions. 
>
> I'm very confused was wondering if anyone had any R sample code they would
> share. I've come across a lot of C++ code(nothing in R) and this is not
> helping. 
>
> best, 
>
> MK

Not sure what you mean by a "threaded" binary tree, but I am enclosing
code below.  It is from my forthcoming book on software development in
R.

Two caveats:

1.  It hasn't been checked yet.  There may be bugs, inefficiencies etc.

2.  It does search and insert, not delete.

Norm Matloff

# routines to create trees and insert items into them are included
# below; a deletion routine is left to the reader as an exercise

# storage is in a matrix, say m, one row per node of the tree; a link i
# in the tree means the vector m[i,] = (u,v,w); u and v are the left and
# right links, and w is the stored value; null links have the value NA;
# the matrix is referred to as the list (m,nxt,inc), where m is the
# matrix, nxt is the next empty row to be used, and inc is the number of
# rows of expansion to be allocated when the matrix becomes full

# initializes a storage matrix, with initial stored value firstval
newtree <- function(firstval,inc) {
   m <- matrix(rep(NA,inc*3),nrow=inc,ncol=3)
   m[1,3] <- firstval
   return(list(mat=m,nxt=2,inc=inc))
}

# inserts newval into nonempty tree whose head is index hdidx in the
# storage space treeloc; note that return value must be reassigned to
# tree; inc is as in newtree() above
ins <- function(hdidx,tree,newval,inc) {
   tr <- tree
   # check for room to add a new element
   tr$nxt <- tr$nxt + 1
   if (tr$nxt > nrow(tr$mat))
      tr$mat <- rbind(tr$mat,matrix(rep(NA,inc*3),nrow=inc,ncol=3))
   newidx <- tr$nxt  # where we'll put the new tree node
   tr$mat[newidx,3] <- newval
   idx <- hdidx  # marks our current place in the tree
   node <- tr$mat[idx,]
   nodeval <- node[3] 
   while (TRUE) {
      # which direction to descend, left or right?
      if (newval <= nodeval) dir <- 1 else dir <- 2
      # descend
      # null link?
      if (is.na(node[dir])) {
         tr$mat[idx,dir] <- newidx
         break
      } else {
         idx <- node[dir]
         node <- tr$mat[idx,]
         nodeval <- node[3] 
      }
   }
   return(tr)
}

# print sorted tree via inorder traversal
printtree <- function(hdidx,tree) {
   left <- tree$mat[hdidx,1]
   if (!is.na(left)) printtree(left,tree)
   print(tree$mat[hdidx,3])
   right <- tree$mat[hdidx,2]
   if (!is.na(right)) printtree(right,tree)
}