題目來自一個搜索公司的筆試題：
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，加油哦！