History of biomes and generated structures
Prior to the Halloween Update, a map had either a Snowy or Grassy theme which was randomly determined when creating the world. After the update, a world includes all biome themes generated in a distribution range that is determined from the biomes graph.
The triangular-looking fern (also known as "living shrub") was rare, and only found in Rain Forest biome pre-1.8. At present, since Rain Forests removed entirely, "living shrubs" generate naturally since 1.2.1, where they spawn in the new jungle biomes.
 World saves from before the Halloween and Adventure Updates
Worlds generated prior to the update remained unchanged except for changes in grass color. New chunks generated (by the player moving outside of the pre-biome world's generated bounds) do generate biomes, similar to the Nether being generated when you first enter it from a portal. Moving from 1.7.3 or earlier to 1.8 or later, the previous generated terrain stays the same but is in a different 1.8 biome. This is shown by the grass and leaf colors. A 1.7.3 forest biome could have the grass and leaf colors of a desert biome.
 Taiga and Tundra biomes in 1.8
In 1.8, Notch said the Taiga and Tundra biomes would be left out until 1.9 because of problems in the biome generation code, but it only concerns the snow weather and snow layers as the other common features of this type of land can still be generated. Tundra biome was readded in 1.0, but Taiga didn't have snow before 1.1.
 Pre-1.8 Biomes
The below screenshot shows several of the "old" biomes from before the Adventure Update. As you can see, the biomes were much smaller and less distinct. While there was less variation between different biomes, some players argue that the terrain within individual biomes was much more varied and interesting. Biome placement was controlled by temperature and humidity values, allowing interface biomes and making it impossible to generate desert near taiga or rainforest near tundra while making transitions from biome to biome smoother.
|Rain Forest||A biome with many trees and lakes. Some trees may also have leaves extending to the ground, covering the entire trunk. Has a 33% chance to create branched trees, compared to the usual 10%. Rain forests have lots of tall grass as well as ferns (living shrubs) that are found exclusively in rain forests.|
|Seasonal Forest||Seasonal forests are wetter than forests and are usually found between forests and rain forests.|
|Forest||A biome with many trees and a fair amount of tall grass. Wolves are also found on this biome more commonly than others.|
|Swampland||A biome with many small pools. Stalks of Sugar Cane are commonly found.|
|Savanna||A biome with mostly flat terrain, almost no trees, and dull colored grass.|
|Shrubland||A biome with some trees and dull colored grass. Usually found at the interface between forest and savanna. No tall grass can be generated here.|
|Taiga||A snowy biome composed of mostly mountainous terrain and very few tall grass. Ice, spruce and pine trees can be found in this region. Wolves also appear more commonly on this biome than others. Snow is a common weather in taiga biomes. In Beta 1.8 and 1.0, Taiga biomes generated without ice and/or snow due to a bug.|
|Desert||A biome consisting mostly of sand, dead shrubs and cacti. Trees do not generate in deserts unless the player brings in dirt. No rain occurs in this biome.
Since Beta 1.0 and before Beta 1.4 desert borders were rotated and didn't line up because of a bug.
|Plains||A very flat biome with a very large amount of tall grass (more than in any other type of land). The occasional trees do exist, though very rarely.|
|Tundra||snowy, barren terrain with very few trees. The occasional trees do exist, though very rarely. Ice can be found over water. Snow is a common weather in tundras.
In 1.8, Notch also said this biome would be left out until 1.9. This is because snow was causing problems with the new biome generator.
|Sky||A hidden biome before 1.9pre4, this biome was exclusive to, and the sole biome of the Sky Dimension. It would generate floating islands with oceans of air surrounding them. Trees were uncommon. No weather occurred here. It had small patches of snow, although it would not accumulate again. It had green with some extra blue hue for foliage colors.
This biome was introduced in Beta 1.6 along with the Sky Dimension itself. It was reintroduced for The End's biome though.
|Ice Desert (corner case biome)||A biome in the code before 1.8 that was supposed to generate at maximum coldness and dryness, but did not actually generate due to bugs. It was a biome of sand with snow on top of it and had snowfall and ice.|
 Pre-1.8 generated structures
|Mountain||Mountains are hills with extreme slopes. Prior to the 1.8 update, these highly mountainous landforms were found in all type of biomes, but from the Adventure Update onwards are very rare outside the Extreme Hills biome. They were generated as part of the terrain generation algorithm.|
|Ocean||Seas/oceans are huge bodies of water with every single water tile being a spring. Prior to the Adventure Update, oceans were generated as part of the terrain generation algorithm, but since then they are part of the Ocean biome.|
Beaches are usually generated next to oceans or lakes and covered all nearby low elevated shorelines. Before Beta 1.8 they could be found in any biome. They came in two varieties: sand beach and gravel beach. Sandstone was located below sand in sand beaches. Gravel beaches had no such border and thus posed dangers like falling into caverns located right underneath them. Due to the changes in the terrain generation algorithm in the Beta 1.8 update beaches were removed completely from the game. Beaches were later re-added in 1.1.0, although this new version is not the same type as the ones generated before the Adventure Update.
Cliffs are carved into hills, and sometimes have caves protruding into them. These caves contain the same blocks which one would find at the same layer in the hill they are carved out of. This may include Ores, Stone, Gravel, Sand, Sandstone and Dirt. As of Beta 1.8, these no longer generate randomly, but can be seen as part of the Extreme Hills biome.