I know this is very strange, but I've been searching for ages and I cannot find a Heracross.
There is no specific tree, it's just rare for a Heracross to appear and I'm assuming you're playing the original Johto games since the tags say "gold-silver"
It can appear in any tree, you just have to keep going until you find one Heracross. It is just a matter of luck.
You can also find Heracross in any of this routes: Routes 29, 30, 31, 32, 33, 42, 43, 44, 45, 46 (Headbutt trees)