Aheterochromatictreeisanedge-coloredtreeinwhichanytwoedgeshavedifferentcolors.Theheterochromatictreepartitionnumberofanr-edge-coloredgraphG,denotedbytr(G),istheminimumpositiveintegerpsuchthatwhenevertheedgesofthegraphGarecoloredwithrcolors,theverticesofGcanbecoveredbyatmostpvertex-disjointheterochromatictrees.Inthispaperwedeterminetheheterochromatictreepartitionnumberofr-edge-coloredcompletegraphs.Wealsofindatmosttr(Kn)vertex-disjointheterochromatictreestocoveralltheverticesinpolynomialtimeforagivenr-edge-coloringofKn.