(42S,Free42,DM42) Binary Tree
01-18-2022, 04:08 AM (This post was last modified: 01-18-2022 06:24 AM by arhtur.)
Post: #1
 arhtur Junior Member Posts: 14 Joined: Jun 2021
(42S,Free42,DM42) Binary Tree
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.
 « Next Oldest | Next Newest »