What is the difference between regular trees and phylogenetic trees in terms of graph theory? If I am not mistaken, a tree is any graph that does not contain cycles.
However, I am currently taking a bioinformatics course where we deal a lot with algorithms on phylogenetic trees. Usually you are given a phylogenetic tree with $n$ leafs, and then you run some algorithm that can do something trivial like simple traversing of the tree, and then you get a $O(n)$ time bound, without saying anything about the number of internal nodes.
However given a regular tree with $n$ leafs, the total number of internal nodes can be infinite.
For example the following is a tree with one leaf (two if you consider it to be rooted) and infinite number of internal nodes:

So what are phylogenetic trees that you can express the running time of various algorithms in terms of the number of leafs, even though your algorithm actually traverses the entire phylogenetic tree?
Phylogenetic trees are usually "full binary trees", that is rooted trees in which every internal node has exactly two children. A full binary tree having $n$ leaves has exactly $2n-1$ nodes.