使用派生类型实现递归树方法的类型兼容问题咨询

问题描述 #

我定义了泛型基类BinaryTree<T>（T实现IComparable接口），包含左右子节点、根节点属性及前序、中序、后序遍历方法：

class BinaryTree<T> 
    where T : IComparable
{
    protected BinaryTree<T>? _left;
    protected BinaryTree<T>? _right;
    protected BinaryTree<T>? _root;
    protected T _value;

    public T Value
    {
        get { return _value; }
        set { _value = value; }
    }

    public BinaryTree<T>? Left
    {
        get { return _left; }
        set { _left = value; }
    }

    public BinaryTree<T>? Right
    {
        get { return _right; }
        set { _right = value; }
    }

    public BinaryTree<T>? Root
    {
        get { return _root; }
        set { _root = value; }
    }
  
    public BinaryTree() { }

    public BinaryTree(T value, BinaryTree<T>? left = null, BinaryTree<T>? right = null, BinaryTree<T>? root = null)
    { ... }
    public List<T> PreOrder()
    { ... }

    public List<T> InOrder()
    { ... }

    public List<T> PostOrder()
    { ... }
}

随后实现了继承自BinaryTree<int>的派生类BinarySearchTree，并添加了Search方法：

class BinarySearchTree : BinaryTree<int>
{
    public BinarySearchTree() : base() { } 

    public Boolean Search(int value)
    {
        if (Value.CompareTo(value) == 0) return true;
        if ((Left is not null) && (Value.CompareTo(value) > 0)) { return Left.Search(value); }
        else if ((Right is not null) && (Value.CompareTo(value) > 0)) { return Right.Search(value); }
        else { return false; }
    }
}

但Left.Search和Right.Search无法正常调用，因为Left和Right的类型是BinaryTree<int>而非BinarySearchTree。我不想通过在派生类中重写_left、_right、Left和Right来解决（冗余），也不想将Search方法移到基类中，希望找到更合理的实现方式。

最初想让基类中_left和_right的类型自动适配派生类类型，但无法通过GetType()定义属性类型，请问该如何解决？

解决方案 #

1. 递归泛型（CRTP/奇异递归模板模式） #

这是解决这类“基类引用派生类类型”问题的经典方案，通过让基类接受派生类作为泛型参数，让左右节点直接绑定到派生类类型：

修改基类定义：

class BinaryTree<TNode, T> 
    where TNode : BinaryTree<TNode, T>
    where T : IComparable
{
    protected TNode? _left;
    protected TNode? _right;
    protected TNode? _root;
    protected T _value;

    public T Value
    {
        get { return _value; }
        set { _value = value; }
    }

    public TNode? Left
    {
        get { return _left; }
        set { _left = value; }
    }

    public TNode? Right
    {
        get { return _right; }
        set { _right = value; }
    }

    public TNode? Root
    {
        get { return _root; }
        set { _root = value; }
    }
  
    public BinaryTree() { }

    public BinaryTree(T value, TNode? left = null, TNode? right = null, TNode? root = null)
    {
        _value = value;
        _left = left;
        _right = right;
        _root = root;
    }

    // 遍历方法保持原有实现
    public List<T> PreOrder() { ... }
    public List<T> InOrder() { ... }
    public List<T> PostOrder() { ... }
}

调整派生类的继承关系：

class BinarySearchTree : BinaryTree<BinarySearchTree, int>
{
    public BinarySearchTree() : base() { } 

    public BinarySearchTree(int value, BinarySearchTree? left = null, BinarySearchTree? right = null, BinarySearchTree? root = null)
        : base(value, left, right, root) { }

    public bool Search(int value)
    {
        if (Value.CompareTo(value) == 0) return true;
        
        return Value.CompareTo(value) > 0 
            ? Left?.Search(value) ?? false 
            : Right?.Search(value) ?? false;
    }
}

此时Left和Right的类型为BinarySearchTree，可直接调用Search方法，避免了冗余的属性重写。

2. 安全类型转换（快速解决方案） #

如果不想修改基类结构，可以在派生类中对Left和Right做安全类型校验后再调用方法：

class BinarySearchTree : BinaryTree<int>
{
    public BinarySearchTree() : base() { } 

    public bool Search(int value)
    {
        if (Value.CompareTo(value) == 0) return true;
        
        if (Value.CompareTo(value) > 0)
        {
            if (Left is BinarySearchTree leftNode)
            {
                return leftNode.Search(value);
            }
        }
        else
        {
            if (Right is BinarySearchTree rightNode)
            {
                return rightNode.Search(value);
            }
        }
        
        return false;
    }
}

这种方式无需改动基类，但每次调用都要做类型检查，适合快速修复问题，但扩展性较差。

3. 抽象基类+重写方法（折中方案） #

如果后续有多个派生类需要类似自定义方法，可在基类定义抽象方法，让派生类实现：

abstract class BinaryTree<T> 
    where T : IComparable
{
    // 原有属性、构造函数和遍历方法保持不变...

    // 定义抽象搜索方法
    public abstract bool Search(T value);
}

class BinarySearchTree : BinaryTree<int>
{
    public BinarySearchTree() : base() { } 

    public override bool Search(int value)
    {
        if (Value.CompareTo(value) == 0) return true;
        return Value.CompareTo(value) > 0 
            ? Left?.Search(value) ?? false 
            : Right?.Search(value) ?? false;
    }
}

该方案需将基类改为抽象类，所有派生类都要实现Search方法，适合需要统一接口的场景，但不符合“仅在派生类实现复杂方法”的需求，可根据实际场景选择。

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