二叉树

DFS 与 BFS

• DFS：Depth-First-Search 深度优先搜索
• BFS：Breadth-First Search 广度优先搜索 ```csharp using System; using System.Collections.Generic; using System.Linq;

namespace ConsoleTemp { // 注：为了方便理解，很多变量命名都用的全称 class Program { static void Main(string[] args) { // 生成 [0,10) 的自然数数组 var values = Enumerable.Range(0, 10).ToArray(); var binarySearchTree = GetTree(values, 0, values.Length - 1); DFS(binarySearchTree); Console.WriteLine(“============================”); BFS(binarySearchTree); }

    static Node GetTree(int[] values, int lowIndex, int highIndex)
    {
        if (lowIndex > highIndex) return null;
        var middleIndex = lowIndex + (highIndex - lowIndex) / 2;
        var node = new Node(values[middleIndex]);
        node.Left = GetTree(values, lowIndex, middleIndex - 1);
        node.Right = GetTree(values, middleIndex + 1, highIndex);
        return node;
    }
    static void DFS(Node node)
    {
        if (node == null) return;
        DFS(node.Left);
        Console.WriteLine(node.Value);
        DFS(node.Right);
    }
    static void BFS(Node root)
    {
        var q = new Queue<Node>();
        q.Enqueue(root);
        while (q.Count > 0)
        {
            var node = q.Dequeue();
            Console.WriteLine(node.Value);
            if (node.Left != null) q.Enqueue(node.Left);
            if (node.Right != null) q.Enqueue(node.Right);
        }
    }
}
class Node
{
    public int Value { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }
    public Node(int value)
    {
        Value = value;
    }
}

} ```