Tree-men are a kind of giant or a description Hobbits of the Shire gave to what presumably were Ents.
Background
In Chapter 2 of the Fellowship of the Ring, while at The Green Dragon Sam tells of rumors of giant Tree-men up beyond the North Moors, saying that his cousin Hal actually saw one "as big as an elm tree, and walking - walking seven yards to a stride."
Earlier legends
Voronwë and Eärendel set sail in Wingilot and are driven south into dark regions with fire mountains. They encountered Tree-men, Sun-dwellers, pygmies, and the Sarqindi.
Behind the scenes
In an early draft of Lord of the Rings Frodo is captured by Treebeard. Treebeard was revised into a good character in later drafts.
Ent is a word for 'giant' in Old English.