Trying to get Heracross.
Okay so I assume you are talking about the Johto games here.
The Johto games have a special mechanic where you can actually headbutt trees in the overworld.
First, find the area where the Pokemon can be found in the game. Then have a Pokemon know headbutt (a move tutor will teach it to your Pokemon in Ilex Forest). After that, go to any tree in the area and you will be able to use headbutt with your Pokemon on that tree. There is a chance that a Pokemon might attack you when you headbutt the tree. For the list of Pokemon that can be encountered here's a link that might help:
Hope I helped:))