Data Structures/Tree Axioms

An axiomatic development of trees is very important for their systematic study.

There are two fundamental definitions of trees in use: a set-theoretic one and a graph-theoretic one. They are not equivalent. The graph-theoretic definition calls trees "graphs without cycles" or "graphs with unique paths between vertices". In set theory, a tree is just a set with a partial order such that there is always a "least element"; you can conceive a tree in this definition which does not fit the graph theoretic definition.

In what follows, I take the middle road. I define trees constructively, but in the same abstract way as defines almost every inductive set in algebra. By eschewing to view trees as subsets of graph I am, of course, neglecting some very important conclusions about the relationship of trees to other kinds of graphs; but the narrow definition as it is presented here maintains focus on the fundamental properties of trees. To compensate, a short section at the beginning introduces the graph-theoretic definition of the trees we will be studying.

Trees as graphs

The kinds of trees described below are directed graphs. They are rooted: that is, there is an element from which all elements eventually stem and to which no elements go. (The general definition of a graph-theoretic tree applies also, viz., a tree is a graph with no cycles).