Binary tree

Binary tree --- бинарное дерево.

An [math]\displaystyle{ n }[/math]-node binary tree is defined to be a rooted tree where each of the [math]\displaystyle{ n }[/math] nodes has zero, one or two descendants, and a distinction is made between the left and right subtrees.

One class of operation which may be performed on binary trees is that of traversing the whole tree: each node in the tree is "visited", or "processed", exactly once in some predefined order. The three most natural traversal orders are known as preorder, inorder and postorder (Knuth, 1975). Preorder and postorder traversals are also commonly called depth-first and bottom-up traversals, respectively, though these latter terms are normally used in connection with more general types of trees.