We propose a preorder tree which satisfies an order relation: Keys placed at nodes appear in lexicographic order, when the tree is traversed in preorder. Algorithms for search, insertion and deletion are given. The number of key comparisons in the search is investigated theoretically and by simulation studies and compared with the case of binary search trees. We also give an algorithm for constructing a preorder tree which minimizes the number of key comparisons. Simulation experiments confirm the effectiveness of optimization.