Your top-level predicate huffman(frequency_list, huffman_tree) should take a list of [item, frequency] lists and a Huffman tree of items. This predicate should evaluate to true if the provided huffman tree is the correct tree for the given frequency list. Some things to think about:
Technically speaking, you can define a datastructure in Prolog. However, you are not going to do that. You are going to use a multi-dimensional list structure to represent your tree at all times.
The strategy in building a Huffman tree is to initially turn each tuple into a single-node Huffman tree, then combine the two trees with the lowest values (frequencies) into a new tree. The value stored at the root of the new tree is the sum of the values of the two trees from which it is formed. This new tree is then put into list of trees, and again the two trees with the lowest values are combined, and the result reinserted into the list. This is repeated until the list holds a single tree. Note that implementing this is easy if you keep the list of trees sorted by value and maintain sorted order when inserting the newly formed trees. You cannot assume that the initial list of tuples is sorted!