C#实现二叉树等递归数据结构时如何正确避免空引用

问题核心 #

开发C#二叉树结构时，若希望参考string.Empty的实现思路，用全局静态空节点实例替代null作为叶子节点的默认子节点，会遇到两个典型问题：

• 静态Empty实例初始化时调用无参构造函数，构造函数内又需要访问尚未完成初始化的Empty字段，触发无限递归
• 若单独给空节点逻辑赋值null，Visual Studio的可空引用分析会弹出大量空引用警告，即使实际运行时不会触发空引用

初始存在缺陷的实现 #

基础Node类定义：

class Node
{
   int Data;
   Node Left;
   Node Right;
}

传统子节点默认赋值null的构造函数：

public Node(int Data)
{
  this.Data = Data;
  Left = null;
  Right = null;
}

存在递归初始化问题的改造版本：

public static readonly Node Empty = new Node();

public Node(int Data)
{
  this.Data = Data;
  Left = Node.Empty;
  Right = Node.Empty;
}

public Node()
{
  Data = int.MinValue;
  Left = Node.Empty;
  Right = Node.Empty;
}

推荐实现方案 #

方案1：引用类型实现（性能最优，适配绝大多数场景） #

核心思路是为空节点设计独立的私有构造逻辑，从根源避免静态字段初始化递归，同时让空节点的子节点指向自身，彻底消除null值，配合可空引用类型注解消除IDE警告。
完整可运行代码：

#nullable enable
class Node
{
    public int Data { get; }
    public Node Left { get; }
    public Node Right { get; }

    // 全局唯一空节点实例
    public static readonly Node Empty = new Node(isEmptyNode: true);

    /// <summary>
    /// 构造普通数据节点
    /// </summary>
    /// <param name="data">节点存储的数值</param>
    public Node(int data)
    {
        Data = data;
        // 普通节点默认子节点为空节点，永远不赋值null
        Left = Empty;
        Right = Empty;
    }

    /// <summary>
    /// 空节点专用私有构造函数，不对外暴露
    /// </summary>
    private Node(bool isEmptyNode)
    {
        Data = int.MinValue;
        // 空节点的左右子节点指向自身，无需访问Empty字段，无递归问题，也无null值
        Left = this;
        Right = this;
    }

    /// <summary>
    /// 统一判断当前节点是否为空节点
    /// </summary>
    public bool IsEmpty() => ReferenceEquals(this, Empty);
}
#nullable restore

关键设计说明：

• 空节点使用独立私有构造函数生成，构造过程中直接将左右子节点指向自身，完全不访问静态Empty字段，彻底解决初始化递归问题
• 所有对外公开的构造函数仅在Empty静态字段初始化完成后才会被调用，子节点默认赋值Empty，公开访问路径上永远不会出现null值
• 使用ReferenceEquals做空节点判断，无需重写Equals方法，判断为引用级别的性能开销，远低于值相等判断
• 空节点判断逻辑统一封装为IsEmpty()方法，树遍历、节点操作时直接调用该方法即可，无需编写node == null类判断
• 全链路无null赋值，Visual Studio可空引用分析不会产生警告

注意：空节点的子节点指向自身不会导致遍历死循环，只要遍历逻辑在进入节点后第一时间判断IsEmpty()并终止当前分支递归即可，实际运行逻辑和传统null判断完全一致。

方案2：值类型实现（类型层面强制null安全） #

如果希望从类型约束层面彻底杜绝null的出现，可以将Node定义为结构体，从类型系统层面强制开发者处理空节点场景：

#nullable enable
public struct Node
{
    private readonly int _data;
    private readonly Node? _left;
    private readonly Node? _right;

    public static readonly Node Empty = new Node(0, null, null, isEmpty: true);

    /// <summary>
    /// 当前节点是否为空节点
    /// </summary>
    public bool IsEmpty { get; }

    /// <summary>
    /// 节点存储的数据，空节点访问会抛出异常
    /// </summary>
    public int Data => IsEmpty ? throw new InvalidOperationException("空节点不存在数据值") : _data;
    /// <summary>
    /// 左子节点，默认返回空节点
    /// </summary>
    public Node Left => _left ?? Empty;
    /// <summary>
    /// 右子节点，默认返回空节点
    /// </summary>
    public Node Right => _right ?? Empty;

    private Node(int data, Node? left, Node? right, bool isEmpty)
    {
        _data = data;
        _left = left;
        _right = right;
        IsEmpty = isEmpty;
    }

    /// <summary>
    /// 构造叶子节点
    /// </summary>
    public Node(int data) : this(data, null, null, false)
    {
    }

    /// <summary>
    /// 构造带左右子节点的内部节点
    /// </summary>
    public Node(int data, Node left, Node right) : this(data, left, right, false)
    {
    }
}
#nullable restore

该方案的优势是结构体默认不可为null（除非显式声明Node?可空类型），类型系统会强制开发者处理空节点场景；缺点是结构体存在值拷贝开销，仅适合节点规模较小的场景。 #

遍历逻辑适配示例 #

改造后的树遍历逻辑无需null判断，直接通过IsEmpty()方法终止分支即可：

public static void PreOrder(Node node)
{
    if (node.IsEmpty()) return;
    Console.WriteLine(node.Data);
    PreOrder(node.Left);
    PreOrder(node.Right);
}

内容的提问来源于stack exchange，提问作者Lasse Michael Mølgaard