Trees
Linked lists and array-based lists work well for representing linear relationships, but not all relationships are linear. In this chapter, we are going to investigate one of the most nonlinear data structures: trees.
As the name implies, it looks like a tree, containing roots, branches, and leaves. In trees, items are organized in hierarchical way, with some nodes being "above" and some "below" others.
A tree is a general and natural model to describe the world. Just to name a few:
- Animals can be classified into 2 main groups: vertebrates and invertebrates. Vertebrates can even classified into warm-blooded and cool-blooded, while invertebrates can classified into: with jointed legs and without legs.
- HTML can be nested. For example,
<html>
is the root tag, and it has two major nested elements:<head>
and<body>
. Inside the head, typical elements include<title>
and<style>
; while inside the body, typical elements include<h1>
,<p>
.