请问怎么构建最优化树?

Question

请问各位大侠,如何实现从键盘输入一些字符,接着统计出字符的个数(不算空格和标点符号),然后根据每个字符的出现频率构建一棵最优化树. 例如:输入一个句子: go, google, go.
字符个数: 10
每个字符的出现频率:
g = 4, o = 4, l = 1, e = 1.

Answer 1

我的想法是将l(1),e(1),o(4),和g（4）看成4棵树，将他们的值按大小排列后，存在一个数组中。先选最小直的2棵：l和e连成一棵，然后再和其它相连，但是有个问题，每棵树连成后，父节点的值就会有改变，数组就要重新排列。我觉得这种算法太没效率，请问有没有更好的方法？
还有个问题就是，当输入字符的时候，怎么可以更好的统计字符输入的个数，就是忽略标点符号和空格，我的笨办法是用一个数组存储输入的所有信息，然后比较数组每一个的内容是不是大于‘a’，小于‘z’，或大于‘A’，小于‘Z’。呵呵，好像太笨了。而且鉴于数组的缺陷，可不可以用或怎么用指针来实现？谢谢了