Just to nitpick a little - trees are graphs. Acyclic directed graphs to be specific Regarding your question, it is probably not a good idea to stuff every kind of information you need into a single data structure. Rendering requires a different graph (tree) structure and data to be efficient than path finding or collision detection. Your initial scene graph may contain all the required data, but for real time use it's best to split that data up into separate layers (render nodes, path finding nodes, collision information, objects, etc.) and data structures that are optmised with regards to their respective usage.
Yet another thing to consider is the way your data will be used in general. A streaming file format and data structure has different requirements from a static graph that is loaded once (like using zones for larger patches of terrain). A http://en.wikipedia.org/wiki/Quadtree might provide a relatively simple way of subdividing larger scenes into smaller parts. It can be pre-calculated in an offline step so your heightmap can initially be quite large. By storing the tree in a linear fashion to a file and using an index into each level of the tree you can then easily locate and deserialise the data you need at runtime if you need to.