Limpiar TreeView Manual de Referencia
Repito lo que se encuentra en esa página para mayor comodidad.
Eliminar todos los nodos de un TreeView:
TreeView1.Nodes.Clear
Eliminar un determinado nodo de un TreeView:
TreeView1.Nodes.Remove 123 TreeView1.Nodes.Remove "abc" '(donde 123 y "abc" representan el índice o la clave del nodo a eliminar)
No agradezco directamente en esa página porque es un foro de un tema cerrado desde hace mucho tiempo.