Data Structures/Tree Axioms

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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[edit]

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).