A tempting approach to maintaining a balanced binary search tree is to maintain two binary search trees and to insert each new key into the tree that will be more balanced. More specifically, do the following: The first key is the root of the left tree. The second key is the root of the right tree. To add a new key, insert it into the tree where it would have a smaller depth. If the depths of both trees are the same, then add it to the first tree.The input will be 5 strings (ignore everything but the letters A through Z and a through z; uppercase and lowercase are the same). For each input string, build the two trees with each string as described above. Print contents of the first tree in preorder (root, then the left child, then the right child).
Sample Input:
Line #1: AMERICAN COMPUTER SCIENCE
Line #2: I must say that I find television very educational
Line #3: INTERMEDIATE DIVISION
Sample Output:
Output #1: A A E C C E E N I P S
Output #2: I A A A A I D D C E E I U T T S R U Y V Y
Output #3: I E E A I I I T T V
维护一个平衡的二叉搜索树的一个诱人的方法是维护两个二叉搜索树，并将每个新键插入树中，这样会更加平衡。更具体地说，执行以下操作:第一个键是左树的根。第二个键是右树的根。若要添加新键，请将其插入到树中其深度较小的位置。如果两棵树的深度相同，则将其添加到第一棵树上。
输入将是5个字符串(忽略除了字母A到Z和A到Z;大写和小写是一样的)。对于每个输入字符串，使用上面描述的每个字符串构建两个树。按顺序打印第一个树的内容(根，然后左子树，然后右子树)。
样例输入:
第一行:美国计算机科学
我得说我觉得电视很有教育意义
第3行:中间部分
样例输出:
输出#1:A A E C C E E N I P S
输出#2:I A A A I D D C E E I U T S R U Y V Y
输出#3:ieia I I T T V
基本要求:算法合理，结果准确
