stinkey
Forum adept
- Joined
- Sep 8, 2020
- Messages
- 225
- Reaction score
- 74
Every day, you stumble across a problem that is only solvable with binary tree inversion. Every second of your life, of your being, you must invert binary trees. Today I will show you how to do so in the Minecraft coding server known as DiamondFire, or DF for short.
First, how do we store a binary tree?
We can create a list like this:
At first, this may just seem like a series of random numbers. But the pattern is this: the memory is divided into arrays of length 3, the first value being the node value, the second value being the pointer to the left child, and the third value being the pointer to the right child. When the pointer is 0, or null, it points to nothing, or an invalid location.
We can see it as such:
Now that we have successfully stored our binary tree, we must actually write the function.
Process "tree_invert" is like a void function; rather than returning a tree, it mutates a tree. We edit the pre-existing tree rather than making a copy of the tree. This way, we can easily use processes with local variables on copy to pass in arguments and we don't have to worry about processes interfering with one another.
We take in the pointer, the location of the tree's root in the memory. We then get the value at that location, and see if its null; if so, we just end the process since there's nothing else to invert.
Then, we get the values of the left and right child, which themselves are pointers to other smaller trees. We are recursively inverting trees.
After this, we swap the left and right children, to invert the tree.
Finally, we call the process again, instead with the children's pointers.
Thus, we invert the binary tree.
I'm sure this will help you in your daily lives, even outside of programming. You will walk the streets knowing that you have the ability to invert binary trees. Deep down inside, you will truly realize how great this simple function is; it shall become your personal mantra, the rope you follow to enlightenment.
First, how do we store a binary tree?
We can create a list like this:
Code:
MEMORY: [ 1, 4, 7, 2, 10, 13, 3, 16, 19, 4, 0, 0, 5, 0, 0, 6, 0, 0, 7, 0, 0, ]At first, this may just seem like a series of random numbers. But the pattern is this: the memory is divided into arrays of length 3, the first value being the node value, the second value being the pointer to the left child, and the third value being the pointer to the right child. When the pointer is 0, or null, it points to nothing, or an invalid location.
We can see it as such:
Code:
MEMORY: [
[ 1, 3(1)+1, 3(2)+1 ],
[ 2, 3(3)+1, 3(4)+1 ],
[ 3, 3(5)+1, 3(6)+1 ],
[ 4, NULL, NULL ],
[ 5, NULL, NULL ],
[ 6, NULL, NULL ],
[ 7, NULL, NULL ],
]Now that we have successfully stored our binary tree, we must actually write the function.
Code:
// where variable "memory" is the memory that we store the binary tree in
// where we receive variable "args" as the pointer to the tree node to invert, initially 1
PROCESS tree_invert:
SET VARIABLE SetToValue ( LOCAL ptr, LOCAL args )
IF VARIABLE Equals ( LOCAL ptr, NUMBER 0 ):
CONTROL End
SET VARIABLE AddNumbers ( LOCAL ptr_left, LOCAL ptr, NUMBER 1 )
SET VARIABLE AddNumbers ( LOCAL ptr_right, LOCAL ptr, NUMBER 2 )
SET VARIABLE GetListValue ( LOCAL val_left, GAME memory, LOCAL ptr_left )
SET VARIABLE GetListValue ( LOCAL val_right, GAME memory, LOCAL ptr_right )
SET VARIABLE SetListValue ( GAME memory, LOCAL ptr_left, LOCAL val_right )
SET VARIABLE SetListValue ( GAME memory, LOCAL ptr_right, LOCAL val_left )
SET VARIABLE SetToValue ( LOCAL args, LOCAL val_left )
START PROCESS tree_invert { Local Variables: Copy }
SET VARIABLE SetToValue ( LOCAL args, LOCAL val_right )
START PROCESS tree_invert { Local Variables: Copy }Process "tree_invert" is like a void function; rather than returning a tree, it mutates a tree. We edit the pre-existing tree rather than making a copy of the tree. This way, we can easily use processes with local variables on copy to pass in arguments and we don't have to worry about processes interfering with one another.
We take in the pointer, the location of the tree's root in the memory. We then get the value at that location, and see if its null; if so, we just end the process since there's nothing else to invert.
Then, we get the values of the left and right child, which themselves are pointers to other smaller trees. We are recursively inverting trees.
After this, we swap the left and right children, to invert the tree.
Finally, we call the process again, instead with the children's pointers.
Thus, we invert the binary tree.
I'm sure this will help you in your daily lives, even outside of programming. You will walk the streets knowing that you have the ability to invert binary trees. Deep down inside, you will truly realize how great this simple function is; it shall become your personal mantra, the rope you follow to enlightenment.
