(42S,Free42,DM42) Binary Tree

[arhtur]

I searched for a binary tree implementation and didn't see one. How, you might ask, can a binary tree be implemented on the HP42s (or Free42 or DM42)? Some compromises were needed. I limited the tree to 99 elements and each element can have a value from 1 to 99. Each binary tree node is encoded with the left pointer in the thousands and hundreds digits and the right pointer in the tens and ones digits and the value encoded in the tenths and hundredths digits. On the Free42, I was able to make a binary tree with 50 nodes. On the DM42, I had to reduce the size to 25 nodes. This is perhaps due to there being less levels of recursion available on it. This was tested on the Free42 and DM42, but I assume it should also work on the HP42s.

First, in the program FIL, XEQ FIL to fill registers 150 to 199 with the numbers 1 to 50, and initialize registers 1 to 99 with 0.

Code:

00 { 95-Byte Prgm }
01▸LBL "FIL"
02 SIZE 200
03 130
04 STO "SP"
05 150.199
06 STO "A"
07 1
08 STO "B"
09▸LBL "FIL1"
10 RCL "B"
11 STO IND "A"
12 1
13 STO+ "B"
14 ISG "A"
15 GTO "FIL1"
16 1.099
17 STO "A"
18▸LBL "FIL2"
19 0
20 STO IND "A"
21 ISG "A"
22 GTO "FIL2"
23 RTN
24 END

Next, in the program MX, XEQ MX to randomly mix the numbers 1 to 25 in registers 150 to 174.

Code:

00 { 61-Byte Prgm }
01▸LBL "MX"
02 150.174
03 STO "A"
04▸LBL "MX1"
05 RAN
06 25
07 ×
08 IP
09 150
10 +
11 STO "B"
12 RCL IND "A"
13 RCL IND "B"
14 STO IND "A"
15 R↓
16 STO IND "B"
17 ISG "A"
18 GTO "MX1"
19 RTN
20 END

Third, in the program MINS (main insertion), XEQ MINS to fill the binary tree. MINS calls IT. IT uses register C for the address of the insertion point, register D for the data value to insert and register E holds the next free tree node.

1. If the insertion point has a 0 value, then we add the value of register D (divided by 100) to the insertion point.
2. If the insertion point is not 0, we go to IT1 and compare the node value to register D. If register D is greater than the node value, we go to IT2.

3. If register D is not greater than the node value, we check the left pointer (in the thousands and hundreds digits). If the left pointer is not 0, we go to IT3.
4. If the left pointer is 0, we store D in the tenths and hundredths digits of the new node register E points to. We set our current node left pointer to the register E points to, increment E and return.
5. In IT3, if the left pointer (in step 4) was not 0, we set C to the value of the left pointer of the node and recursively call IT.

6. In IT2 (register D > node value), we check the right pointer (in the tens and ones digits). If the right pointer is not 0, we go to IT4.
7. If the right pointer is 0, we store D in the tenths and hundredths digits of the new node register E points to. We set our current node right pointer to the register E points to, increment E and return.
8. In IT4, if the right pointer (in step 7) was not 0, we set C to the value of the right pointer of the node and recursively call iT.

Code:

00 { 64-Byte Prgm }
01▸LBL "MINS"
02 1
03 STO "E"
04 150.174
05 STO "A"
06▸LBL "MINS1"
07 RCL IND "A"
08 STO "D"
09 1
10 STO "C"
11 XEQ "IT"
12 ISG "A"
13 GTO "MINS1"
14 1
15 STO "C"
16 RTN
17 END

Code:

00 { 197-Byte Prgm }
01▸LBL "IT"
02 RCL IND "C"
03 X≠0?
04 GTO "IT1"
05 RCL "D"
06 100
07 ÷
08 STO+ IND "C"
09 1
10 STO+ "E"
11 RTN
12▸LBL "IT1"
13 RCL IND "C"
14 100
15 ×
16 100
17 MOD
18 RCL "D"
19 X>Y?
20 GTO "IT2"
21 RCL IND "C"
22 100
23 ÷
24 IP
25 X≠0?
26 GTO "IT3"
27 RCL "D"
28 100
29 ÷
30 STO+ IND "E"
31 RCL "E"
32 100
33 ×
34 STO+ IND "C"
35 1
36 STO+ "E"
37 RTN
38▸LBL "IT3"
39 RCL IND "C"
40 100
41 ÷
42 IP
43 STO "C"
44 XEQ "IT"
45 RTN
46▸LBL "IT2"
47 RCL IND "C"
48 100
49 MOD
50 IP
51 X≠0?
52 GTO "IT4"
53 RCL "D"
54 100
55 ÷
56 STO+ IND "E"
57 RCL "E"
58 STO+ IND "C"
59 1
60 STO+ "E"
61 RTN
62▸LBL "IT4"
63 RCL IND "C"
64 100
65 MOD
66 IP
67 STO "C"
68 XEQ "IT"
69 RTN
70 END

Last, we traverse the tree in the program TV with XEQ TV (in MINS, at the end, we set C to 1 (the root of the tree)). The in order tree traversal is basically to traverse left, print the node value and traverse right. Here, I found that a problem is the HP42s/DM42/Free42 does not save variables when a program is recursively called. So I wrote a PUSH function to store the value of C before each TV function call. Here, D is not to be confused with a data value to store (like in the IT program). D is the value of the left or right pointer we are traversing next. After a return from a recursive TV function call, we POP the value of C.

Code:

00 { 112-Byte Prgm }
01▸LBL "TV"
02 STO "C"
03 RCL IND "C"
04 100
05 ÷
06 IP
07 STO "D"
08 X=0?
09 GTO "TV1"
10 RCL "C"
11 XEQ "PUSH"
12 RCL "D"
13 XEQ "TV"
14 XEQ "POP"
15 STO "C"
16▸LBL "TV1"
17 RCL IND "C"
18 100
19 ×
20 100
21 MOD
22 IP
23 PSE
24 RCL IND "C"
25 100
26 MOD
27 IP
28 STO "D"
29 X=0?
30 RTN
31 RCL "C"
32 XEQ "PUSH"
33 RCL "D"
34 XEQ "TV"
35 XEQ "POP"
36 STO "C"
37 RTN
38 END

Code:

00 { 37-Byte Prgm }
01▸LBL "PUSH"
02 STO IND "SP"
03 1
04 STO+ "SP"
05 RTN
06▸LBL "POP"
07 1
08 STO- "SP"
09 RCL IND "SP"
10 RTN
11 END

If everything is working correctly, you will see the numbers 1 to 25 displayed.