一道面试题
本人才疏学浅，望大家多给意见，有更好的做法大加分享分享
下面是题目：
已知表table_department中有两个字段，分别为d_id,d_name。d_id记录的是部门编码， d_name记录的是部门名称，各部门的组织方式如下：
A为顶级部门，A部门的下级部门使用AA、BA、CA……表示
AA的下级部门使用AAA、BAA、CAA……表示
BA的夏季部门使用ABA、BBA、CBA……表示
以此类推。
新建一个应用程序，写一个页面或窗体，讲table_department表中的数据，按树状排列显示，如下所示：
A总经办
-AA生产部
--AAA保修部
--BAA非保部
-BA物流部
--ABA物流一部
--BBA物流二部
--CBA物流三部
-CA市场部
--ACA市场拓展
--BCA营销部
---ABCA电器营销部
---BBCA电子营销部
…………
………… 加分项：
表table_department用XML实现
===================================================
这个问题我觉得会有比较多的解法，我这里暂且考虑面试的问题，所以给出的解法不会考虑太多严谨的东西
首先建库建表添加数据
SQL脚本为
=================================================
1 -- 创建数据库 2 if db_id ( ' testdb ' ) is not null 3 drop database testdb; 4 go 5 create database testdb; 6 7 -- 使用数据库 8 use testdb; 9 -- 创建数据表 10 if object_id ( ' table_department ' , ' U ' ) is null 11 create table table_department 12 ( 13 d_id varchar ( 10 ), 14 d_name nvarchar ( 50 ) 15 ); 16 go 17 -- 添加数据 18 insert into table_department(d_id, d_name) values ( ' A ' , ' 总经办 ' ); 19 insert into table_department(d_id, d_name) values ( ' AA ' , ' 生产部 ' ); 20 insert into table_department(d_id, d_name) values ( ' BA ' , ' 物流部 ' ); 21 insert into table_department(d_id, d_name) values ( ' CA ' , ' 市场部 ' ); 22 insert into table_department(d_id, d_name) values ( ' AAA ' , ' 保修部 ' ); 23 insert into table_department(d_id, d_name) values ( ' BAA ' , ' 非保部 ' ); 24 insert into table_department(d_id, d_name) values ( ' ABA ' , ' 物流一部 ' ); 25 insert into table_department(d_id, d_name) values ( ' BBA ' , ' 物流二部 ' ); 26 insert into table_department(d_id, d_name) values ( ' CBA ' , ' 物流三部 ' ); 27 insert into table_department(d_id, d_name) values ( ' ACA ' , ' 市场拓展 ' ); 28 insert into table_department(d_id, d_name) values ( ' BCA ' , ' 经营部 ' ); 29 insert into table_department(d_id, d_name) values ( ' ABCA ' , ' 电器经营部 ' ); 30 insert into table_department(d_id, d_name) values ( ' BBCA ' , ' 电子经营部 ' );
========================================
第一种解法
也是最简单傻瓜式的解法，使用ADO.Net读取数据. 并将读到的数据，根据d_id字段的数据创建TreeView节点，并加载数据
观察树节点的规律，每个节点只有d_id的现实，只有最后一个节点现实完整的d_id和d_name，并且每个d_id的字符表示一个层次结构
因此可以写一个方法，根据包含d_id和d_name的字符串创建节点和添加数据
简单步骤：
1、 首先该方法要往TreeView添加数据，因此该方法一定要有一个TreeNode参数(鉴于根节点只有一个，可以将A添加为根节点，或直接就将"公司"作为根节点)
2、 观察d_id的字符串，根节点在最右边，子节点在左边(估计是为了故意设计的面试题，这样不好排序)
实际这个很简单，将d_id字符串转换成字符数组，从后往左遍历，并在TreeNode中创建节点，如果节点存在就不用创建
3、 因此方法原型可以定义为：
1 private void ShowFromString( string d_id, string id, string d_name, TreeNode tn)
2 {
3 // 实现代码
4 // d_id创建结构使用
5 // id记录部门id号
6 // d_name记录部门名称
7 // tn表示当前节点
8 }
4、 接下来看方法如何实现
由于TreeNode是有层次显示的，所以这里使用递归最为容易(循环感觉也可以实现)
4.1 首先将d_id编程字符数组，并得到最后一个字符，这个顶级节点
1 char [] chs = d_id.ToCharArray(); 2 string nodeStr = chs[chs.Length - 1 ].ToString();
4.2 在TreeNode中检索是否存在这个节点. 检索存在就是看TreeNode的子节点中是否有Tag与nodeStr匹配的(这里可使用Linq，不过既然简单用最原始的)
写一个方法，由于部门的名字是不会重复的，所以这么写
1 private bool IsExist( string nodeText, TreeNode tn)
2 {
3 bool isTrue = false ;
4 for ( int i = 0 ; i < tn.Nodes.Count; i++ )
5 {
6 if (tn.Nodes[i].Tag as string == nodeText)
7 {
8 isTrue = true ;
9 break ;
10 }
11 }
12 return isTrue;
13 }
该方法只要找到TreeNode直接子节点中存在与给定字符串相同的节点就返回true，否则返回false
4.3 判断是否存在节点，如果不存在就创建，如果存在就得到这个节点
这里需要注意的是，所有节点的逻辑结构均有Tag属性来确认，而Text属性最终使用d_id与d_name替换，因此这里是一个临时的值
TreeNode tnObj = null ;
if (! IsExist(nodeStr, tn))
{
tnObj = tn.Nodes.Add(nodeStr);
tnObj.Tag = nodeStr;
}
else
{
// 得到这个节点
}
4.4 考虑如果存在就得到该节点，但是不要写循环一次了，太麻烦，因此修改IsExist方法
1 private bool IsExist( string nodeText, TreeNode tn, out TreeNode tnObj)
2 {
3 tnObj = null ;
4 bool isTrue = false ;
5 for ( int i = 0 ; i < tn.Nodes.Count; i++ )
6 {
7 if (tn.Nodes[i].Tag as string == nodeText)
8 {
9 isTrue = true ;
10 tnObj = tn.Nodes[i]; // 将找到的节点直接返回
11 break ;
12 }
13 }
14 return isTrue;
15 }
因此4.3步的代码可以改为
1 if (!IsExist(nodeStr, tn, out tnObj))
2 {
3 tnObj = tn.Nodes.Add(nodeStr);
4 tnObj.Tag = nodeStr;
5 }
这个方法的思路来自int.TryParse方法，如果找到了，那么返回true，那么tnObj中就有了该节点
如果没有找到那么创建一个，反正tnObj中就有当前子节点
4.5 这里应该判断是不是最后一个节点，如果是最后一个节点那么就应该将id和d_name加到Text属性上
由于使用递归完成，因此再次调用这个方法的时候，会将存储d_id的char数组最后一个字符去掉
因此使用chs.Length == 1即可判断是否为最后一个节点
1 if (chs.Length == 1 )
2 {
3 // 将当前节点即为结束节点
4 tnObj.Text = string .Format( " {0} {1} " , id, d_name);
5 }
6 else
7 {
8 // 如果不是最终节点，则递归
9 ShowFromString( new string (chs, 0 , chs.Length - 1 ), id, d_name, tnObj);
10 }
5、 整合一下方法
1 private void ShowFromString( string d_id, string id, string d_name, TreeNode tn)
2 {
3 char [] chs = d_id.ToCharArray();
4 string nodeStr = chs[chs.Length - 1 ].ToString();
5 TreeNode tnObj = null ;
6 if (!IsExist(nodeStr, tn, out tnObj))
7 {
8 tnObj = tn.Nodes.Add(nodeStr);
9 tnObj.Tag = nodeStr;
10 }
11 if (chs.Length == 1 )
12 {
13 tnObj.Text = string .Format( " {0} {1} " , id, d_name);
14 }
15 else
16 {
17 ShowFromString( new string (chs, 0 , chs.Length - 1 ), id, d_name, tnObj);
18 }
19 }
20 private bool IsExist( string nodeText, TreeNode tn, out TreeNode tnObj)
21 {
22 tnObj = null ;
23 bool isTrue = false ;
24 for ( int i = 0 ; i < tn.Nodes.Count; i++ )
25 {
26 if (tn.Nodes[i].Tag as string == nodeText)
27 {
28 isTrue = true ;
29 tnObj = tn.Nodes[i]; // 将找到的节点直接返回
30 break ;
31 }
32 }
33 return isTrue;
34 }
6、 添加窗体的Load事件，并添加代码
1 private void Form1_Load( object sender, EventAges e)
2 {
3 // 添加根节点公司， 就是在公司下面添加节点
4 TreeNode tn = tvCompany.Nodes.Add( " 公司 " );
5 // 处理数据库，读数据
6 using (SqlConnection conn = new SqlConnection( @" server=.\sqlexpress;database=testdb;integrated security=true " ))
7 {
8 using (SqlCommand cmd = new SqlCommand( " select d_id, d_name from table_department " , conn))
9 {
10 conn.Open();
11 using (SqlDataReader reader = cmd.ExecuteReader())
12 {
13 if (reader.HasRow)
14 {
15 while (reader.Read())
16 {
17 string d_id = reader.GetString( 0 );
18 string d_name = reader.GetString( 1 );
19 ShowFromString(d_id, d_id, d_name, tn);
20 }
21 }
22 }
23 }
24 }
25 }
7、 最后要用XML存储，递归遍历节点，创建XML数据，就像遍历文件夹一样
7.1 添加递归方法
1 private void GetXML(TreeNode tn, XElement ele)
2 {
3 // 得到tn下的数据，并加到ele中
4 for ( int i = 0 ; i < tn.Nodes.Count; i++ )
5 {
6 // 创建对应节点
7 XElement ele1 = new XElement(tn.Nodes[i].Text.Replace( " " , " _ " )); // 由于XML中节点名中不允许有空格，所以去掉
8 ele.Add(ele1);
9
10 // 递归
11 GetXML(tn.Nodes[i], ele1);
12 }
13 }
7.2 添加按钮事件
1 private void createXML_Click( object sender, EventArgs e)
2 {
3 XDocument xDoc = new XDocument();
4 xDoc.Add( new XElement( " Company " ));
5
6 GetXML(tvCompany.Nodes[ 0 ], xDoc.Root);
7
8 xDoc.Save( " company.xml " );
9 }
========================================
第二种方法
第一种方法比较简单，关键在于如何处理d_id结构而已，而且顺序读取和创建
实际上TreeNode与XML结构一致，是可以同样处理的，也就是说先从数据库中取出数据，生成XML数据，在递归遍历XML数据创建TreeNode
1、 从数据库中读取数据，并创建XML文件
树形结构有一个特点，就是每一个节点只允许有一个父节点和一个子节点，所以可以从数据库中取出所有数据，得到所有数据的节点片段数据
在根据一定算法将节点连起来
1.1 添加一个方法，该方法完成从数据库中读取数据，并得到XML集合(数组也行，个人比较喜欢集合)
1 private List<XElement> GetElementByDatabase()
2 {
3 // 代码
4 }
1.2 读取数据库，创建XML集合
1 private List<XElement> GetElementByDatabase()
2 {
3 List<XElement> list = new List<XElement> ();
4 using (SqlConnection conn = new SqlConnection( @" server=.\sqlexpress;database=testdb;integrated security=true " ))
5 {
6 using (SqlCommand cmd = new SqlCommand( " select d_id, d_name from table_department " , conn))
7 {
8 conn.Open();
9 using (SqlDataReader reader = cmd.ExecuteReader())
10 {
11 if (reader.HasRows)
12 {
13 while (reader.Read())
14 {
15 string d_id = reader[ 0 ].ToString();
16 string d_name = reader[ 1 ].ToString();
17 // 开始生成XML数据
18 list.Add( new XElement( " department " ,
19 new XAttribute( " d_id " , d_id),
20 new XAttribute( " d_name " , d_name)
21 ));
22 }
23 }
24 }
25 }
26 }
27 return list;
28 }
2、 处理XML片段集合的结构，这个结构没有构成树状结构，因此写一个方法将这个XML片段集合变成一个XML树片段
这里算法有很多，也可以使用Linq查询，但是我不打算详细描述算法，因为有些比较抽象
这里用一个不一定最快，但是很直观的算法
2.1 添加一个方法
1 public XElement GetXMLTree(List<XElement> listXML)
2 {
3 // 代码
4 }
2.2 了解到XML每一个节点至多只有一个父节点和子节点，因此只要将处理好节点的去掉即可
同时每一个节点都是通过d_id分层次，而这个层次很有规律，父节点刚好比子节点多一个字符，也就是说
父节点的d_id与子节点的d_id.Substring(1)相同
所以就可以从最长的节点开始找，依次为每一个节点找父节点即可
1 public XElement GetXMLTree(List<XElement> listXML)
2 {
3 // 先为listXML降序排序，因为d_id越长，节点越深
4 listXML.Sort((XElement x1, XElement x2) => { return x2.Attribute( " d_id " ).Value.Length - x1.Attribute( " d_id " ).Value.Length; });
5 // 从左开始为每一个节点找父节点，很显然，最长的节点最深
6 // 一旦找到父节点，添加进去，就可以将该节点从集合中移除
7 for ( int i = 0 ; i < listXML.Count; i++ )
8 {
9 XElement curr = listXML[i];
10 for ( int j = i + 1 ; j < listXML.Count; j++ )
11 {
12 // 判断是否为父子关系
13 if (curr.Attribute( " d_id " ).Value.Substring( 1 ) == listXML[j].Attribute( " d_id " ).Value)
14 {
15 listXML[j].Add(curr);
16 }
17 }
18 }
19 return listXML[listXML.Count - 1 ];
20 }
3、 XML结构有了，那么就可以保存该数据了
另外遍历XML结构，加载到TreeView控件中
1 private void ShowTreeNode(TreeNode tn, XElement ele)
2 {
3 foreach (XElement item in ele.Elements())
4 {
5 TreeNode tn1 = tn.Nodes.Add( string .Format( " {0} {1} " , item.Attribute( " d_id " ).Value, item.Attribute( " d_name " ).Value));
6 if (item.HasElements)
7 {
8 ShowTreeNode(tn1, item);
9 }
10 }
11 }
4、 添加Load方法
1 XElement element = null ; // 记录要保存的XML数据
2 private void Form1_Load( object sender, EventArgs e)
3 {
4 List<XElement> xelements = GetElementByDatabase();
5
6 element = GetXMLTree(xelements);
7
8 ShowTreeNode(tvCompany.Nodes.Add( " 公司 " ), element);
9 }
5、 添加保存XML的代码(添加XElement字段)
1 private void btnSave_Click( object sender, EventArgs e)
2 {
3 XDocument xDoc = new XDocument(element);
4 xDoc.Save( " xml.xml " );
5 MessageBox.Show( " OK " );
6 }
第三种方法
写了第二种方法就不太想写第三种方法了，介绍一下基本思想吧
为数据表创建一个对象模型，但是多出一个字段，就是记录反序的d_id
那么就可以利用排序等手段创建对象集合
同时解析每一个字符创建TreeView节点了
=================================================
好了，就给出成型的两个算法吧！如果有时间在慢慢看. 本人见识有限，还请大家多提意见，如果有更好的思路，借鉴一下啊！！！
2012年10月10日晚
分类: C/C++/C# Programming , DataBase
作者： Leo_wl
出处： http://HdhCmsTestcnblogs测试数据/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息