An NNC-Tree is a decision tree (DT) with each non-terminal node containing a nearest neighbor classifier (NNC). Compared with the conventional axis-parallel DTs (APDTs), the NNC-Trees can be more efficient, because the decision boundary made by an NNC is more complex than an axis-parallel hyperplane. Compared with single-layer NNCs, the NNC-Trees can classify given data in a hierarchical structure that is often useful for many applications. This paper proposes an algorithm for inducing NNC-Trees based on the R4-rule, which was proposed by the author for finding the smallest nearest neighbor based multilayer perceptrons (NN-MLPs). There are mainly two contributions here. 1) A heuristic but effective method is given to define the teacher signals (group labels) for the data assigned to each nonterminal node. 2) The R4-rule is modified so that an NNC with proper size can be designed automatically in each nonterminal node. Experiments with several public databases show that the proposed algorithm can produce NNC-Trees effectively and efficiently.