In order to investigate the structure of computable functions over (binary) trees, we define two classes of recursive tree functions by extending the notion of recursive functions over natural numbers in two different ways, and also define the class of functions computable by whileprograms over trees. Then we show that those classes coincide with the class of conjugates of recursive functions over natural numbers via a standard coding function (between trees and natural numbers). We also study what happens when we change the coding function, and present a necessary and sufficient condition for a coding function to satisfy the property above mentioned.