음.. 해당 Node에서 Child가 있는지 Check해서..
해당 Node의 Child가 존재하면..
Node의 Child를 제거하면 될 거 같네여..
단, Child가 있는데.. 그 Child에  Child가 있다면..
그 Child도 제거해야 합니다..
즉, 재귀호출을 해서.. 제거해야 한다는 이야기입니다..
재귀호출은 알꺼라구 생각하구여..
아래 내용이 맞는진 모르겠지만..(빨리 쓸려니..  *^^*)
대략적으로 썼으니깐... 뭐 이런식으로 하면 제 의도는 파악될겁니다.
이렇게 해서..
자식노드를 모두 제거하는 방법을 취한 후에..
다시 추가하는 루틴을 쓰면 될겁니다..
(추가는 성공하셨다니.. 그거 쓰면 될테니.. 제가 안써도 되져? *^^*)

Procedure NodeChildRemove(CurNode: TTreeNode)
Var
     ChildNode, RmNode: TTreeNode;
     ll_Cnt: LongInt;
Begin
       If Not CurNode.HasChild Then Exit;

       ChildNode := CurNode.FirstChild; //FirstChild가 맞는가?
       While (ChildNode <> Nil) Do
       Begin      
              If ChildNode.HasChild Then
                      NodeChildRemove(ChildNode);

             RmNode :=  ChildNode;
             RmNode제거;
             ChildNode := CurNode.NextChild;
       End;
End;