Structures (trees like) spawning in mid air or half buried in the nether

You need to add spawning conditions to the tree structure like

If Block at X,Y,Z = Grass_Block

     Return True

Return False

Spawning structures underground is more difficult than simply putting them on the surface; In my experience, your best bet is to either:

• Add very specific generation conditions, (such as having the correct block below, and air above), and then turn up the generation check much higher than you would normally.
• Add a 'when generated' procedure that finds a nearby location that fits your conditions.