C++

American Computer Science League Senior Division-PROGRAMMING 1992-93 Contest #4 Problem: An a-b tree is a binary tree in which each node can contain either one key or two keys. The children in a node's left subtree are all less than or equal to the largest key at the node. In the following example, the keys are al! single characters: Sv The root node contains 2 keys, d and g. It has a left child that contains a single node, c. The right child is a node with 2 keys, s and v. That node has two chidren, the left child has keys u and m, the right child, the key Inserting into an a-b tree is like inserting into a binary search tree, except when you come to a node containing only one key, you simply add the new key to the node containing one key. The node then contains two keys. For example, b would be added to the node containing c. More interestingly, consider what happens when an f is added to the tree. At the root, we go left (since f is less than or equal to the larger of the keys at the root), and then to the right of cb (since f is larger than the larger of the keys in the node). And so on. Input: Five strings. Each string will be less than 50 characters long and will contains the letters A through 2. Each letter is a key to be added to an initially empty a-b tree. Output: For each input string, print the tree using in in-order. That is, print a node's left subtree, then the node, and then the node's right subtree. Within a node with 2 keys, the keys are listed in the order in which they were added to the node. The in-order listing of the tree above (after b and f are added) is: c bfdgunsvw Sample Input: Line #1: INDIA Line #2: CANADA Line #3: PORTUGAL Line #4: SWITZERLAND Line 5: UNITEDKINGDOM Sample Output: Output #1: A D 1 1 N Output #2: A A C A N D Output #3: G A L P O R T U Output #4: D LANERITSWZ Output #5: D EDGKINNOITUN