题目来自一个搜索公司的笔试题：
http://www.lietu.com/joinus/
http://www.lietu.com/joinus/ClassTree.htm
http://www.lietu.com/joinus/ClassTree.htm
一、层次树(ClassTree.txt)：
分类号 | 分类名 | 父分类 | 是否是末级 |
001 | 图书 | 0 | 1 |
001001 | 计算机 | 001 | 1 |
001001001 | 硬件 | 001001 | 0 |
001001002 | 计算机理论 | 001001 | 0 |
001001003 | 网络 | 001001 | 0 |
001001004 | 语言与编程 | 001001 | 1 |
001001004001 | C/C++/VC/C# | 001001004 | 0 |
001001004003 | Basic/VB/VB Script | 001001004 | 0 |
001001004004 | Pascal/Delphi/Fortran | 001001004 | 0 |
001001004005 | Java/Java Script/JSP/EJB | 001001004 | 0 |
001001004008 | Power Builder | 001001004 | 0 |
001001004009 | HTML/XML/ASP/PHP/Perl | 001001004 | 0 |
001001004011 | Director | 001001004 | 0 |
001001004012 | 汇编语言 | 001001004 | 0 |
001001004014 | Foxpro | 001001004 | 0 |
001001004015 | .Net技术 | 001001004 | 0 |
001001004016 | 其他 | 001001004 | 0 |
001001004017 | WAP | 001001004 | 0 |
001001005 | 操作系统 | 001001 | 0 |
001001006 | 数据库 | 001001 | 1 |
001001006001 | Oracle | 001001006 | 0 |
001001006002 | Informix | 001001006 | 0 |
001001006003 | DB2 | 001001006 | 0 |
001001006004 | Sybase | 001001006 | 0 |
001001006005 | SQL Server | 001001006 | 0 |
001001006006 | Foxpro | 001001006 | 0 |
001001006007 | Access | 001001006 | 0 |
001001006008 | 数据仓库 | 001001006 | 0 |
001001006009 | 数据库原理 | 001001006 | 0 |
001001006010 | PowerBuilder | 001001006 | 0 |
001001007 | 认证、等级考试 | 001001 | 0 |
001001008 | 图形图像/网页制作 | 001001 | 1 |
001001008001 | 3DStudio/Max | 001001008 | 0 |
001001008002 | MAYA | 001001008 | 0 |
……
二、参考答案（C#版本,一共两个文件，CategoryNode.cs和Program.cs）：
1 //CategoryNode.cs
2
3 using System.Collections.Generic;
4
5 namespace Tree
6 {
7 class CategoryNode
8 {
9 private String no;// 分类号
10
11 private String name;// 分类名
12
13 private bool isLeaf;// 是否为末级
14
15 List<CategoryNode> children =null;
16 //记录此类别的所有子类
17
18 public CategoryNode(String no, String name, bool isLeaf)
19 {
20 this.no = no;
21 this.name = name;
22 this.isLeaf = isLeaf;
23 if (!isLeaf)
24 {
25 children = new List<CategoryNode>(5);
26 }
27 }
28
29 public void addChildren(CategoryNode node)//给此条目增加一个子条目
30 {
31 if (isLeaf)
32 {
33 throw new Exception("add child error to leaf node:" + no );
34 }
35 children.Add(node);
36 }
37
38 public bool leaf()
39 {
40 return isLeaf;
41 }
42
43 public String getName()
44 {
45 return name;
46 }
47
48 public String getNo()
49 {
50 return no;
51 }
52
53 public override String ToString()
54 {
55 String temp = "";
56 foreach (CategoryNode child in children)
57 {
58 temp += child.name+"\n";
59 }
60 temp += "\n";
61 return temp;
62 }
63 }
64 }
1 //Program.cs
2 using System;
3 using System.IO;
4 using System.Collections.Generic;
5
6 namespace Tree
7 {
8 class TreeFind
9 {
10 [STAThread]
11 static void Main(string[] args)
12 {
13 Dictionary<String, CategoryNode> ht = new Dictionary<String, CategoryNode>();
14 StreamReader sr;
15 string line;
16 string temp;
17 try
18 {
19 sr = new StreamReader(@"D:\lg\work\d1\ClassTree.txt", System.Text.Encoding.Default);
20 //ommit head line
21 sr.ReadLine();
22 CategoryNode node = new CategoryNode("0", "ROOT", false);
23 ht.Add("0", node);
24 while ((line = sr.ReadLine()) != null)
25 {
26 line = line.Replace(" ", "");
27 string[] strarray = line.Split(new char[] { '\t' });
28 bool isLeaf = ("0".Equals(strarray[3]));
29
30 node = new CategoryNode(strarray[0], strarray[1], isLeaf);
31 ht.Add(strarray[0], node);
32
33 //if (!"0".Equals(strarray[2]))
34 {
35 ht[strarray[2]].addChildren(node);
36 }
37 }
38 }
39 catch (Exception e)
40 {
41 Console.WriteLine(e.Message);
42 }
43 Console.WriteLine("Please Enter a father node：");
44 temp = Console.ReadLine();
45 while (temp != "exit")
46 {
47 if (ht.ContainsKey(temp))
48 {
49 if (ht[temp].leaf())
50 {
51 Console.WriteLine("The father node haven't any childs！");
52 }
53 else
54 {
55 Console.Write(ht[temp]);
56 }
57 }
58 else
59 {
60 Console.WriteLine("The father node dosn't exists！");
61 }
62 Console.WriteLine("Please Enter a father node：");
63 temp = Console.ReadLine();
64 }
65 }
66 }
67 }
三、自己的理解和体会
因为前段时间一直在学习二叉树和判定树，所以对这个有点敏感。有了二叉树的基础，这个看了一下明白了。就是定义了一个Node类，然后很技巧的定义了一个Hashtable，通过这个Hashtable就可以每次读入一行数据，根据data[3]（父类的no）设置该父类的孩子结点了。
这个Hashtable运用得太有技巧了，赞！自己也长见识了！
要是自己去实现这个程序，肯定想不出办法来。只能用很笨的方法实现，也就是定义Node类时定义四个字段，（因为一行中有四个字段）其中包括一个father结点，然后搜索时全部遍历一篇匹配这个father的no，然后再取出该结点。但是这样效率肯定大大降低了，因为要全文遍历。
呵呵，今天又长见识了，对hashtable的作用有了更深的了解。以前只是因为正好符合一对一的key-value关系，所以用到它了；今天总算看到它的最根本的用处了，建立索引！
ok！
jiang，加油哦！