Tree

前言

有些东西很有用，但是时间久了就容易忘记。

比如树的遍历，此处写一篇文章，记录多叉树的遍历。并于日后查阅和补充学习。

Tree

一、首先，定义一个树的节点。

• TaskNode.cs

  [c#]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/// <summary>
/// 树的节点
/// </summary>
class TaskNode
{
    /// <summary>
    /// 存放子节点
    /// </summary>
    private List<TaskNode> children = new List<TaskNode>();

    /// <summary>
    /// 节点名称
    /// </summary>
    public string Name
    {
        get;
        set;
    }

    /// <summary>
    /// bat文件路径
    /// </summary>
    public string BatPath
    {
        get;
        set;
    }

    /// <summary>
    /// 子节点
    /// </summary>
    public List<TaskNode> Children
    {
        get
        {
            return this.children;
        }
    }

    #region methods
    /// <summary>
    /// 添加节点
    /// </summary>
    /// <param name="childNode"></param>
    /// <returns></returns>
    public List<TaskNode> AddChild(TaskNode childNode)
    {
        this.children.Add(childNode);
        return this.children;
    }
    #endregion
}

二、其次，构建一颗树。

• BuildTaskNode()

  [c#]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/// <summary>
/// 构建任务节点
/// </summary>
/// <returns></returns>
private static TaskNode BuildTaskNode()
{ 
    TaskNode root = new TaskNode();
    root.BatPath = "";
    root.Name = "root"; //root node

    TaskNode bondEventNode = new TaskNode();
    bondEventNode.BatPath = "bondEventNode.bat";
    bondEventNode.Name = "bondEventNode";

    TaskNode bondCashflowNode = new TaskNode();
    bondCashflowNode.BatPath = "bondCashflowNode.bat";
    bondCashflowNode.Name = "bondCashflowNode";

    TaskNode bondNode = new TaskNode();
    bondNode.BatPath = "bondNode.bat";
    bondNode.Name = "bondNode";

    TaskNode fundNode = new TaskNode();
    fundNode.BatPath = "fundNode.bat";
    fundNode.Name = "fundNode";

    TaskNode stockNode = new TaskNode();
    stockNode.BatPath = "stockNode.bat";
    stockNode.Name = "stockNode";

    TaskNode companyNode = new TaskNode();
    companyNode.BatPath = "companyNode.bat";
    companyNode.Name = "companyNode";

    TaskNode regionNode = new TaskNode();
    regionNode.BatPath = "regionNode.bat";
    regionNode.Name = "regionNode";

    //bond children
    bondNode.AddChild(bondEventNode);
    bondNode.AddChild(bondCashflowNode);

    //company children
    companyNode.AddChild(bondNode);
    companyNode.AddChild(fundNode);
    companyNode.AddChild(stockNode);

    //root children
    root.AddChild(companyNode);
    root.AddChild(regionNode);
    
    return root;
}

这棵树的 JSON 如下：

  [json]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
{
    "Name":"root",
    "BatPath":"",
    "Children":[
        {
            "Name":"companyNode",
            "BatPath":"companyNode.bat",
            "Children":[
                {
                    "Name":"bondNode",
                    "BatPath":"bondNode.bat",
                    "Children":[
                        {
                            "Name":"bondEventNode",
                            "BatPath":"bondEventNode.bat",
                            "Children":[

                            ]
                        },
                        {
                            "Name":"bondCashflowNode",
                            "BatPath":"bondCashflowNode.bat",
                            "Children":[

                            ]
                        }
                    ]
                },
                {
                    "Name":"fundNode",
                    "BatPath":"fundNode.bat",
                    "Children":[

                    ]
                },
                {
                    "Name":"stockNode",
                    "BatPath":"stockNode.bat",
                    "Children":[

                    ]
                }
            ]
        },
        {
            "Name":"regionNode",
            "BatPath":"regionNode.bat",
            "Children":[

            ]
        }
    ]
}

三、我们要来遍历这棵树

1、递归深度遍历

优缺点就不废话了，这不是算法课。这个写起来最简单。

  [c#]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/// <summary>
/// 深度遍历-递归
/// </summary>
/// <param name="node"></param>
private static void RecursionTraverse(TaskNode node)
{ 
    if(node == null)
    {
        return;
    }

    //do sth useful
    Console.WriteLine(node.Name+", "+node.BatPath);

    for (int i = 0; i < node.Children.Count; i++)
    {
        TaskNode child = node.Children[i];
        RecursionTraverse(child);
    }
}

2、非递归层次遍历

  [c#]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/// <summary>
/// 层次遍历
/// </summary>
private static void LevelTraverse(TaskNode root)
{ 
    Queue<TaskNode> nodeQueue = new Queue<TaskNode>();
    nodeQueue.Enqueue(root);

    while (nodeQueue.Count > 0)
    {
        TaskNode node = nodeQueue.Dequeue();
        
        //do sth useful
        Console.WriteLine(node.Name + ", " + node.BatPath);

        for (int i = 0; i < node.Children.Count; i++)
        {
            TaskNode child = node.Children[i];
            nodeQueue.Enqueue(child);
        }
    }
}