The nodes of binary trees may be used to store information. For example, the nametable of Section 6.5 could be implemented by storing each of its records at a node of a binary tree. Just as lists are referred to by name, the tree can be named, say nametable. Obviously, nametable must have records inserted into it, deleted from it, and searched for in it. Insertion, deletion, search, and traversal are the basic tree operations.
Balanced trees and binary search trees (Chapter 9) and heaps (Chapter 8) are all binary trees with special properties that make them useful for storage of information. The properties that make them useful favor efficient searching, inserting, and deleting. Each of these types of binary tree requires its own algorithms for these operations, in order to take advantage of or to preserve their characteristics. For now, to get the flavor of these operations, consider some simple examples.
7.2.1 Insertion and Deletion of Records in Binary Trees
7.2.3 Three Preorder Traversals of a Binary Tree