Building Branching Structures
Added 31 Jul 2008
Visual Studio is chock full of classes to implement exotic data
structures such as collections, hash tables, and dictionaries. One
notable data structure that's missing is the tree. Trees are useful for
storing hierarchical data where each node has one or more children.
Many developers use a TreeView control or XML objects to build trees in
.NET, but both of those methods are rather heavyweight and come with
additional baggage that you may not need or want.
This article explains what trees are, how to build your own trees, how to work with them, and how to get them to do useful things such as drawing themselves, or listing their items in various sequences.
Before getting started, however, you need to understand some tree terminology.
Tree Terminology
Tree terminology is a cross between horticulture and genealogy. Horticulture supplies terms such as tree, node, root, branch, and leaf, while other tree terms come from genealogy, such as ancestor, parent, and child.
A tree is made up of nodes that are connected by branches. A node can have only one parent, but each node may have zero, one, or more child nodes. The branches are directed, which means you can tell which way they are pointing—so you can always discern which node is the parent and which node(s) are the children.
One node, called the root node has no parent. All other nodes in the tree are connected directly or indirectly to the root node. Normally, when you draw a tree, you draw the root at the top. That's the opposite direction from the way an ash tree or an elm tree grows in nature, but it's easier for most people to draw trees that way. With the root at the top, all branches are directed downward, so it's easy to see which nodes are the children and parents of the others.
A node's degree is its number of children. The degree of the tree is equal to the largest degree of any of the nodes. A tree with a degree of 2 is called a binary tree; a tree with a degree of 3 is called ternary. Beyond that, people usually call the tree "N-ary" (if they call it anything at all). For example, a degree 7 tree would be "7-ary."
A node at the bottom of the tree that has no children is called a leaf node. By definition, a leaf is a node with degree 0.
A node's level is its distance from the root node. To some people, that means the number of branches between the node and the root. Others count the nodes (including the node and the root), resulting in a level that's larger by one than you would get using the other method. The difference is whether you consider the root to be at level 0 or 1. (Much like the way the bottom floor of a building is floor 0 in the UK and floor 1 in the US.) For no particularly good reason, I'm going to consider the root node level to be 1.
The height or level of the entire tree is the same as the largest level of any of its leaf nodes.
Note that branches can only connect parent nodes with child nodes. Branches cannot connect "sibling" nodes (nodes with the same parent) and cannot connect nodes across "generations" or levels in the tree.
This article explains what trees are, how to build your own trees, how to work with them, and how to get them to do useful things such as drawing themselves, or listing their items in various sequences.
Before getting started, however, you need to understand some tree terminology.
Tree Terminology
Tree terminology is a cross between horticulture and genealogy. Horticulture supplies terms such as tree, node, root, branch, and leaf, while other tree terms come from genealogy, such as ancestor, parent, and child.
A tree is made up of nodes that are connected by branches. A node can have only one parent, but each node may have zero, one, or more child nodes. The branches are directed, which means you can tell which way they are pointing—so you can always discern which node is the parent and which node(s) are the children.
One node, called the root node has no parent. All other nodes in the tree are connected directly or indirectly to the root node. Normally, when you draw a tree, you draw the root at the top. That's the opposite direction from the way an ash tree or an elm tree grows in nature, but it's easier for most people to draw trees that way. With the root at the top, all branches are directed downward, so it's easy to see which nodes are the children and parents of the others.
A node's degree is its number of children. The degree of the tree is equal to the largest degree of any of the nodes. A tree with a degree of 2 is called a binary tree; a tree with a degree of 3 is called ternary. Beyond that, people usually call the tree "N-ary" (if they call it anything at all). For example, a degree 7 tree would be "7-ary."
A node at the bottom of the tree that has no children is called a leaf node. By definition, a leaf is a node with degree 0.
A node's level is its distance from the root node. To some people, that means the number of branches between the node and the root. Others count the nodes (including the node and the root), resulting in a level that's larger by one than you would get using the other method. The difference is whether you consider the root to be at level 0 or 1. (Much like the way the bottom floor of a building is floor 0 in the UK and floor 1 in the US.) For no particularly good reason, I'm going to consider the root node level to be 1.
The height or level of the entire tree is the same as the largest level of any of its leaf nodes.
Note that branches can only connect parent nodes with child nodes. Branches cannot connect "sibling" nodes (nodes with the same parent) and cannot connect nodes across "generations" or levels in the tree.