I have some information that needs to be represented as a full binary tree. How can I represent such a tree in a non-ambiguous way?
Consider, as an example, the three full binary trees bellow, and the respectively traversal algorithms:
A A A
____|____ ____|____ ____|____
| | | | | |
B C C B C B
__|__ __|__ __|__
| | | | | |
D E D E E D
INORDER DBEAC CADBE CAEBD
PREORDER ABDEC ACBDE ACBED
POSTORDER DEBCA CDEBA CEDBA
LEVELORDER ABCDE ECBDE ECBED
Looking to the 3 examples, the diagrams looks different and the traversal are also different. However, I can see that they represent the same information. They just had some position swaping between branches taking place. Is there a way to take any of the trees and output some representation that is the same independently of the different diagram or traversal output?
What is on my mind.
-
Consider that I have some physical phenomena that can be modeled by a binary tree and from that model I can extract a time series which would be my observable quantity. That can be used to generate a training data for machine learning by randomly creating different trees and its respectively time series. Than, after training, I would like to feed a time series and have the tree as a output. Now, one can see that both as input and as output, having an ambiguous tree representation is likely a bad thing.
-
I’m using python for coding this and I know that I can represent a tree using a class. The part where I randomly generate the tree and the time series is easy. I plan to use LSTM NNs for the job but I have no experience. So I don’t know how this non-ambiguous tree is really a necessity to avoid problems with the ML proccess.
-
I think some reversable hash in which the output is the same for the ambiguous tree is the answer but I had no luck so far in devising one.