C#使用栈实现二叉搜索树非递归遍历出现空引用异常如何解决

错误原因分析 #

1. 空引用异常直接诱因：你定义了类级别的字段Stack<BinarySearchTree> stacks;，但从未对该字段进行实例化，调用stacks.Push时访问的是null对象，自然抛出空引用错误。
2. 设计不合理点：栈不应该作为类的成员变量，多线程同时遍历、多次调用遍历方法时会出现栈状态冲突，完全可以将栈作为GetEnumerator方法内的局部变量使用，不需要单独创建树存储类。
3. 现有遍历逻辑错误：当前你写的中序遍历逻辑流程有问题，无法正确输出所有节点的升序结果。
4. Add方法逻辑缺陷：while循环的判断条件错误，当节点某一侧子节点为空、另一侧不为空时，无法正确向下遍历到目标插入位置，会出现节点覆盖的问题。

修复后的完整代码 #

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class BinarySearchTree : IEnumerable<int>
{
    public int value;
    public BinarySearchTree left;
    public BinarySearchTree right;
    
    public BinarySearchTree(int value)
    {
        this.value = value;
    }

    public BinarySearchTree(IEnumerable<int> values)
    {
        this.value = values.First();
        foreach (var val in values.Skip(1))
        {
            this.Add(val);
        }
    }
    public int Value
    {
        get
        {
            return this.value;
        }
    }

    public BinarySearchTree Left
    {
        get
        {
            return this.left;
        }
    }

    public BinarySearchTree Right
    {
        get
        {
            return this.right;
        }
    }

    public void Add(int value)
    {
        BinarySearchTree current_node = this;
        while (true)
        {
            if (value <= current_node.value)
            {
                if (current_node.left == null)
                {
                    current_node.left = new BinarySearchTree(value);
                    break;
                }
                current_node = current_node.left;
            }
            else
            {
                if (current_node.right == null)
                {
                    current_node.right = new BinarySearchTree(value);
                    break;
                }
                current_node = current_node.right;
            }
        }
    }

    public IEnumerator<int> GetEnumerator()
    {
        // 栈改为方法内局部变量，使用前实例化
        Stack<BinarySearchTree> stacks = new Stack<BinarySearchTree>();
        BinarySearchTree current_node = this;
        
        // 标准非递归中序遍历逻辑
        while (current_node != null || stacks.Count > 0)
        {
            // 一直遍历到最左子节点
            while (current_node != null)
            {
                stacks.Push(current_node);
                current_node = current_node.left;
            }

            current_node = stacks.Pop();
            yield return current_node.value;
            
            // 处理右子树
            current_node = current_node.right;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

验证 #

修复后运行你提供的单元测试，会正常通过，输出结果和预期的[1,2,3,5,6,7]一致。

内容的提问来源于stack exchange，提问作者aldo