Okay, so, let me explain headbutt trees.
First off, not every tree is headbuttable. Now you may say, but I could headbutt them! I say that you can, but by headbuttable trees, I mean you headbutt them and Pokemon actually come out. So, if you headbutt a tree a few times, and no Pokemon come out, then there will never be Pokemon in that tree. Time to headbutt new ones. So, if you knew that, then you are just Unlucky. So I would try to just headbutt trees everywhere, and if Pokemon come out, keep headbutting the tree until the Pokemon you want comes out.
Hope this helps!
