当时想这个算法的时候，是先想好了extjs的格式转换方法后才写的，写完后也没有考虑extjs是不是可以直接用{ ‘id’:’’,’pid’:’’,’text’:’’}格式的方式来表示呢？呵呵，如果是的话那就郁闷了~~，不管了。为了使用Extjs实现在客户端显示树形节点，需要获得节点的孩子节点集合。于是，花了三个小时时间写出了一个遍历算法（囧，代码编写能力还有待提高啊，有时候这中间的关系搞得我晕头转向的，不得不一边画图以便写代码~~），由children字段为空的List<TreeNode> 分析并返回一个包含children的根节点树以便生成json数据。
算法思想如下：
1)当nodelist中还有节点存在时，取出nodeList中的一个节点，并将其从nodeList中移除，进行2)
2)采用深度遍历算法，每取一个节点，将其压入堆栈，因为nodelist中不包含根节点，故建立一个root节点,进行3)
3)在循环中判断当前节点是否为空（即已加入为root节点的children集合），不为空则进行4)，否则到exit)。
4)取出栈顶节点。判断该节点是否有未加入children集合的孩子节点（即在nodeList中能否找到
pid为节点id的节点），有则进行5)，否则进行6)
5)将该节点取出，并将其从nodeList中删除，入栈，继续查找，返回3)
6)若当前节点没有孩子结点，到7)
7)此时，判断堆栈是否为空，若为空（表示此时当前节点所有的子节点已找完)，到8)，若栈不为空，到9)
8)当前节点为叶子节点，栈顶节点即为当前节点的父节点。出栈，将子节点加入到父节点的children集合中。父节点再入栈。到3）
9)判断当前节点是否还有父节点(即判断nodeList中是否还有id为当前节点pid的节点)，若有，到10),否则到11)
10)取出该节点为pNode，并将pNode从nodeList中删除，将当前节点cNode加入到pNode的children集合中，
即作为父节点的孩子节点，父节点入栈（父节点还可能有别的孩子结点）。到3)
11)表示当前节点为顶级节点，将其直接加入到root的children中。到3)
因为每找到一个子节点均将齐从nodelist中移除，故当前节点的子节点最终都会找完
exit)程序结束。此时返回的root节点即为完整的多叉树的根节点，可通过其孩子集合来对节点进行访问，并
通过json的方法进行树形数据格式的转换。
public class TreeNodeHelper
{
/// <summary>
/// 生成一个根节点的树
/// </summary>
/// <param name="nodeList">节点列表，包含未连接的树节点，节点中给出id,pid,text字段</param>
/// <returns></returns>
public TreeNode GenerateTreeRoot(List<TreeNode> nodeList)
{
TreeNode root = new TreeNode();
TreeNode cNode;
TreeNode chNode;
TreeNode pNode;
Stack<TreeNode> stack = new Stack<TreeNode>();
while(nodeList.Count>0)
{
cNode = nodeList[0];
nodeList.Remove(cNode);
stack.Push(cNode);
while (cNode != null)
{
cNode = stack.Pop();
if ((chNode = getChildren(cNode, nodeList)) != null)
{
stack.Push(cNode);
nodeList.Remove(chNode);
stack.Push(chNode);
}
else
{
if (stack.Count > 0)
{
pNode = stack.Pop();
pNode.Children.Add(cNode);
stack.Push(pNode);
}
else
{
if((pNode=getParent(cNode,nodeList))!=null)
{
nodeList.Remove(pNode);
stack.Push(pNode);
pNode.Children.Add(cNode);
}
else
{
root.Children.Add(cNode);
cNode = null;
}
}
}
}
}
return root;
}
public TreeNode getChildren(TreeNode node, List<TreeNode> list)
{
return list.Find(delegate(TreeNode n) { return n.Pid == node.Id; });
}
public TreeNode getParent(TreeNode node, List<TreeNode> list)
{
return list.Find(delegate(TreeNode n) { return n.Id == node.Pid; });
}
}
下面是节点类的定义：
public class TreeNode
{
public TreeNode()
{
m_Id = String.Empty;
m_Pid = String.Empty;
m_Text = String.Empty;
m_Children = new List<TreeNode>();
}
public TreeNode(string id, string pid, string text)
{
m_Id = id;
m_Pid = pid;
m_Text = text;
m_Children = new List<TreeNode>();
}
private string m_Id;
public string Id
{
get { return m_Id; }
set { m_Id = value; }
}
private string m_Pid;
public string Pid
{
get { return m_Pid; }
set { m_Pid = value; }
}
private string m_Text;
public string Text
{
get { return m_Text; }
set { m_Text = value; }
}
private List<TreeNode> m_Children;
public List<TreeNode> Children
{
get { return m_Children; }
set { m_Children = value; }
}
public bool HasChildren
{
get {
if (this.Children != null)
return m_Children.Count > 0 ? true : false;
else
return false;
}
}
/// <summary>
/// 生成根节点的json格式字符串
/// </summary>
/// <returns></returns>
public string ToJsonTreeString()
{
if (!this.HasChildren)
return "";
StringBuilder sb = new StringBuilder();
sb.Append("[");
foreach (TreeNode node in this.Children)
{
sb.Append("{");
sb.Append("'id':'");
sb.Append(node.Id);
sb.Append("','text':'");
sb.Append(node.Text);
sb.Append("',");
//有孩子节点时添加children字段,否则令leaf字段为true
if (node.HasChildren)
{
sb.Append("'children':");
sb.Append(node.ToJsonTreeString());
}
else
{
sb.Append("'leaf':true");
}
sb.Append("},");
}
//去掉最后一个逗号
if(this.Children.Count>0)
sb.Remove(sb.ToString().LastIndexOf(','), 1);
sb.Append("]");
return sb.ToString();
}
}
代码写的比较菜，欢迎扔砖，共同进步
