well, in HG and SS the move HEADBUTT can be used outside of battle, to knock pokemon out of trees, and start a wild encounter. This person demonstrates this in their video, actually using headbutt to catch a starly ( yayz ) http://www.youtube.com/watch?v=b3A3xC9fY_k
so that's what the trees look like, just do what that person did XD
hope this helps you get your starly =)