0

我正在用 C# 编写一个区间树。我想做的只是扩展现有的二叉搜索树来存储间隔，而不必重写核心功能（添加、获取、删除）。

在 BST 内部，我有一Node堂课：

protected class Node 
{
    public KeyValuePair<TKey, TVal> Data;
    public Node Left, Right;

    public Node(KeyValuePair<TKey, TVal> data,
        Node left = null, Node right = null)
    {
        Data = data;
        Left = left; Right = right;
    }
}

在区间树内，我有一个IntervalNode扩展类Node：

private class IntervalNode : Node
{
    public Interval<TInterval> Interval;
    public override string ToString()
    {
        return string.Format("A={0}, B={1}", Interval.A, Interval.B);
    }

    public IntervalNode(KeyValuePair<TInterval, TVal> data, 
        Node left = null, Node right = null)
        : base(data, left, right)
    {
    }
}

我遇到的问题是试图存储IntervalNode在树中而不是Node. 我现在有什么方法可以使用现有的基础实现AddwithIntervalNode吗？

protected Node Add(Node root, KeyValuePair<TKey, TVal> data)
{
    // regular binary search tree insert
}

我想我想做的是这样的：

public void Add(Interval<TInterval> intvl, TVal val)
{
    _root = Add((Node)_root, new KeyValuePair<TInterval, TVal>(intvl.A, val));
    IntervalNode inserted = (IntervalNode)Get(_root, intvl.A);
    inserted.Interval = intvl;
}

// tree should store IntervalNodes, not Nodes
private IntervalNode _root;
4

1 回答 1

1

您的示例代码无法编译，但我认为您正在尝试获取以下内容：

protected class Node
    {
        public KeyValuePair<TKey, TVal> Data;
        public Node Left, Right;

        public Node(KeyValuePair<TKey, TVal> data,
            Node left = null, Node right = null)
        {
            Data = data;
            Left = left; Right = right;
        }

        public virtual void Add(Node root, KeyValuePair<TKey, TVal> data)
        {
            //Do whatever
        }
    }

然后在派生类中：

private class IntervalNode: Node
    {
        public Interval<TInterval> Interval;
        public override string ToString()
        {
            return string.Format("A={0}, B={1}", Interval.A, Interval.B);
        }

        public IntervalNode(KeyValuePair<TInterval, TVal> data, 
            Node left = null, Node right = null)
            : base(data, left, right)
        {
        }

        public override void Add(Node root, KeyValuePair<TInterval, TVal> data)
        {
            //Do whatever you need to, then
            base.Add(root, data);
        }
    }

您需要解决您遇到的泛型问题，但您应该能够明白这一点。

由于IntervalNode是 a Node，因此您可以将其存储在与基类相同的位置，因此无需强制转换或将存储分开。这是关于继承的一个很好的部分。

于 2015-05-13T13:30:05.843 回答