4.2.5.1 - Trees, rooted trees and binary trees (VB.NET)
Recognise trees, describe rooted relationships, and represent binary nodes in VB.NET. This route uses written code with no Run: incomplete: runnable support pending.
Trees without cycles
A tree connects all of its nodes without providing a cycle.
Tree
A connected, undirected graph with no cycles.
Connected means that a path exists between every pair of nodes. A cycle is a closed path that returns to its starting node without simply retracing the same edge. In a tree there is exactly one simple path between any two nodes. A disconnected acyclic graph is a forest, not one tree. A tree need not have a root: designating a root adds a way to interpret an existing tree.
Consider the undirected edges M—F, M—T, F—B, F—H and T—R. All six nodes are connected, and no edge creates a cycle. Adding B—H would create the cycle B—F—H—B. Removing M—T would disconnect T and R from the remaining nodes. These are separate ways to fail the definition.
A finite tree with nodes has edges, but counting edges alone is insufficient: a disconnected graph containing a cycle can have the same count. Check the actual connectivity and cycle conditions.
Rooted parent-child relationships
Choosing a root gives a tree a hierarchy of parent-child relationships.
Designate M as root in the example. F and T are its children; B and H are F's children; R is T's child. The root is the only node with no parent. Every other node has exactly one parent and is a descendant of the root. A node's ancestors lie on the path from the root to it. A leaf has no children; B, H and R are leaves. F and T are siblings because they share parent M.
Depth counts edges from the root when the root is at depth 0. M has depth 0; F and T depth 1; B, H and R depth 2. Rooted trees model folders, organisational hierarchies, menu categories and expression structure. A real folder link can introduce a second path or a cycle, so distinguish a pure tree model from a filesystem with links.
Changing the root changes parent-child descriptions without changing the undirected edges. If F becomes root, M becomes F's child and T becomes M's child. A root is therefore not defined by being drawn at the top or having the greatest numeric value.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account