The HOMM skill tree was not totally random. I made it a game within the game to try and develop the super skills such as Nature’s Luck or Rage of Elements which I accomplished often. There are a couple of tricks as to how you progress with your skill tree to make it more likely you’ll end up with what you want.

I refrained from it myself but in Tribes of the East you could also use the Memory Mentor (if the map has one) to adjust your skills at will.