LoginLogin
Might make SBS readonly: thread

Binary trees?

Root / Programming Questions / [.]

MZ952Created:
MZ952#1
Any clever ways to create binary trees in SB? I'm thinking strings with encoded left/right pointers is the way to go, but I'm still working out how to go about it.
12Me21#2
Well, each row has at most 2^n elements, so you could just make an array of size [1+2+4+8 ...] (that is, 2^(n+1)-1) Some space is wasted, but unless the tree is really big I don't think it matters too much. (you'll also need a way to represent nodes that don't exist (probably giving them a value that you never use, like -1, or using a separate array to keep track of that) for navigating the tree, it's easier if it's 1-indexed: ary[1] / \ ary[2] ary[3] / ary[4] ... movement: up: N>>1 left: N<<1 right: N<<1 OR 1 so, for example, the root node is index 1, so to move down the right branch you'd go to N<<1 OR 1, which is 3. moving left from there is N<<1, which is 6.
MZ952#3
Huh. My initial quick and dirty way was to create a huge 2D array, but this is obviously much better.
Yolkai#4
ninjagnu wrote a tree system for https://smilebasicsource.com/page?pid=1009 The system was something like - data array + implementations: * string: items can be length+chars. Resizing fields can be problematic and might mean memory management passes * <type>[]: don't have to worry about resizing. uhh wait are there even any disadvantages - tree array for binary tree structure + contains value "pointers"/indexes in data array + ninjagnu's probably had left/right pointers in the tree array but 12's solution might be okay for some applications
MZ952#5
DEF TOTREE(A[])
 DIM R[1]
 PUSH R,SHIFT(A)
 R[0]=1'Keeps number of rows
 DIM I,V
 WHILE LEN(A)
  V=SHIFT(A)
  N=1
  WHILE TRUE
   IF V<R[N] THEN
    N=N<<1
   ELSEIF V>=R[N] THEN
    N=N<<1 OR 1
   ENDIF
   IF N>LEN(R)-1 THEN
    FOR I=0 TO POW(2,R[0])-1
     PUSH R,-1'Placeholder value for empty nodes
    NEXT I
    INC R[0]
   ENDIF
   IF R[N]==-1 THEN
    R[N]=V
    BREAK
   ENDIF
  WEND
 WEND
 RETURN R
END
DIM A[0]
PUSH A,5
PUSH A,2
PUSH A,9
PUSH A,1
PUSH A,7
DIM TA[0]
COPY TA,TOTREE(A)
PRINTTREE TA
> [3]
> 5
> 2 9
> 1 -1 7 -1