Almost every project that has some editable model or document will have a hierarchical structure to it. It can come in handy to implement the 'hierarchical node' as a base-class for different entities. Often the linked-list (child sibling, 2nd model) is the natural way many class libraries grow, however the children may be of diverse types, and probably an "object model" is not what we consider when talking about trees in general.
My favorite implementation of a tree(node) of your first model is a one-liner (in C#):
public class node : List<node> { /* props go here */ }
Inherit from a generic List of your own type (or inherit from any other generic collection-of-your-own-type). Walking is possible in one direction: form the root downward (items do not know their parents).
Parent only tree's
Another model you did not mention is the one where every child has a reference to it's parent:
null
|
+---------+---------------------------------+
| parent |
| root |
+-------------------------------------------+
| | |
+---------+------+ +-------+--------+ +--+-------------+
| parent | | parent | | parent |
| node 1 | | node 2 | | node 3 |
+----------------+ +----------------+ +----------------+
Walking this tree is only possible the other way round, normally all these nodes will be stored in a collection (array, hashtable, dictionary etc..) and a node will be located by searching the collection on criteria other than the hierarchical position in the tree which would typically not be of primary importance.
These parent-only tree's are usually seen in database applications. It's quite easy to find the children of a node with "SELECT * WHERE ParentId=x" statements. However we seldom find these transformed into tree-node class objects as such. In statefull (desktop) applications they may be wrapped into existing tree-node controls. In stateless (web)applications even that may be unlikely. I've seen ORM-mapping class-generator tools throw stack overflow errors when generating classes for tables that have a relation with themselves (chuckle), so maybe these tree's are not that common after all.
bidirectional navigable trees
In most practical cases however, it's convenient to have the best of both worlds. Nodes that have a list of children and in addition know their parent: bidirectional navigable trees.
null
|
+--------------------+--------------------+
| parent |
| root |
| child1 child2 child3 |
+--+------------------+----------------+--+
| | |
+---------+-----+ +-------+-------+ +---+-----------+
| parent | | parent | | parent |
| node1 | | node2 | | node3 |
| child1 child2 | | child1 child2 | | child1 child2 |
+--+---------+--+ +--+---------+--+ +--+---------+--+
| | | | | |
This brings along many more aspects to consider:
- Where to implement the linking and unlinking of parent's?
- let the bussiness logic take care, and leave the aspect out of the node (they will forget!)
- nodes have methods for creating children (does not allow re-ordering) (Microsofts choice in their System.Xml.XmlDocument DOM implementation, which almost drove me crazy when I first encountered it)
- Nodes take a parent in their constructor (does not allow re-ordering)
- in all add(), insert() and remove() methods and their overloads of the nodes (usually my choice)
- Persistance
- How to walk the tree when persisting (leave out parent-links for example)
- How to rebuild the two-way linking after de-serializing (setting all the parents again as a post-deserialization action)
- Notifications
- Static mechanisms (IsDirty flag), handle recursively in properties?
- Events, bubble up through parents, down through children, or both ways (consider the windows message pump for example).
Now to answer the question, bidirectional navigable trees tend to be (in my career and field so far) the most widely used. Examples are Microsofts implementation of System.Windows.Forms.Control, or the System.Web.UI.Control in the .Net framework, but also every DOM (Document Object Model) implementation will have nodes that know their parent as well as an enumeration of their children.
The reason: ease of use over ease of implementation. Also, these are usually base classes for more specific classes (XmlNode may be the base of Tag, Attribute and Text classes) and these base classes are natural places to put generic serialization and event-handling architectures.
Tree's lay at the heart of many architectures, and being able to navigate freely means being able to implement solutions faster.
O(n)
factor in the algorithm.