Decision Trees change result at every run, how can I trust of my results?
how can I trust of my results?


You probably shouldn't trust your results, because the large variation is likely caused by overfitting. Basically your model is not very reliable.

My guess is that you have either too many features or not enough instances, or any combination of these two issues.


  I am not sure If it's correct to take the best result on the test set, or maybe I should consider an average of the results


It is definitely not correct to take the best result. The average result is more representative of the true performance, but you should also provide the standard deviation.


  Second, would not it be better to use CV on all data, instead of just splitting at the beginning the dataset in test and train just one time?


Yes, that's a good idea: as far as I understand, currently you're just manually running the program several times and obtaining different performance each time. You can indeed use Cross-validation instead.


  I read about random_state but the problem is that the results depend on which value I use.. example random_state = 2 --> accuracy 0.6 (on test set) random_state = 6 --> accuracy 0.79 (on test set) so basically this does not resolve my problem. How can I validate my model if I dont know which one to use?


That's normal: the split function separates the training and test set randomly according to a random sequence. Setting the random seed to a particular value guarantees the exact same sequence every time, but you don't want that since it makes the splitting non-random. 

Instead you should work on reducing the variation. Usually it's not possible to add instances, so you should probably try to reduce the number of features, or simplify them.