Does every greedy algorithm have matroid structure? It is well established that for every matroid $M$ and any weight function $w$, there exits an algorithm $\mbox{GreedyBasis}(M,w)$ which returns a maximum weight basis of $M$. So, is the reverse direction also true? That is, if there is some greedy algorithm, then there must be some matroid structure also.
Actually, the complete and general description of a problem that can be solved by a greedy algorithm is a matroid embedding, which generalizes both the concept of a matroid and that of a greedoid. The answer is no—a problem solvable by a greedy algorithm need not have a matroid structure, but it will have the structure of a matroid embedding (which is, alas, much more complicated).

A mental model for some of this could be finding minimum spanning trees. The structure used by Kruskal's algorithm is a matroid, but that used by Prim's algorithm (which requires a start node) is not. (It is, however, a greedoid—and a matroid embedding.)

Helman et al. (1993), in their paper An Exact Characterization of Greedy Structures define their notion of a greedy algorithm in terms of set systems, which is the same formalism that is used for matroids and greedoids. A set system $(S,\mathcal{C})$ consists of a set $S$ and a collection $\mathcal{C}$ of subsets of $S$, the so-called feasible sets. A basis for the set system is a maximal feasible set, that is, a set that is feasible but not contained in any other feasible set. An objective function $f:2^S\rightarrow\mathbb{R}$ associates each subset of $S$ with a value. An optimization problem, in this formalism, consists in finding a basis of maximum objective value for a given set system and objective function.

The greedy algorithm, defined in terms of this formalism, is quite simple: You start with the empty set, and successively add a single element until you reach a basis, always ensuring that (i) your set is feasible at each step, and (ii) the element you add maximizes the objective function of the resulting result, wrt. all the alternative elements you could have added. (That is, conceptually, you try adding all feasible alternatives, and choose the one yielding the highest objective value.)

You could, perhaps, argue that there might be other forms of greedy algorithm, but there are several textbooks on algorithms and combinatorial optimization that describe this set-system based algorithm as the greedy algorithm. That doesn't prevent you from describing something that doesn't fit, but could still be called greedy, I suppose. (Still, this does cover anything that could potentially have a matroid structure, for example, though it is much more general.)

What Helman et al. do is that they describe when this algorithm will work. More specifically:


They show that for linear objective functions (where the objective value is the sum of element weights), the greedy algorithm will work exactly on the structure they define as a matroid embedding;
They give a similar characterization for so-called bottleneck objectives (where the objective value of a set is equal to the minimum over the individual element weights); and
They give an exact characterization of which objective functions (beyond linear ones) are optimized by the greedy algorithm on matroid embeddings.