0

好的，所以我已经制作了一个基本的二叉搜索树类，它依赖于一个内部节点类来存储数据。它是这样的（只是在这里展示了裸露的骨头）：

public class TreeSet<T> where T : IComparable<T>
{
    private Node root = null;

    public void Insert(T t)
    {
        if (root == null)
            root = new Node(t);
        else
            root.Insert(t);
    }

    internal class Node
    {
        protected Node left, right;
        private T data;

        public Node(T t)
        {
            data = t;
        }

        public virtual void Insert(T t)
        {
            int compare = t.CompareTo(data);
            if (compare < 0)
            {
                if (left == null)
                    left = new Node(t);
                else
                    left.Insert(t);
            }
            else if (compare > 0)
            {
                if (right == null)
                    right = new Node(t);
                else
                    right.Insert(t);
            }
        }
    }
}

还有更多，显然是搜索方法、枚举器等，但这些都是相关的部分。现在这只是一个基本的 BST，并没有做任何事情来尝试确保它是平衡的或任何东西，但它处理所有的插入和搜索逻辑。如果我要尝试扩展它以制作 AVL 树或红黑之类的东西，我们会遇到问题......

public class AvlTree<T> : TreeSet<T> where T : IComparable<T>
{
    internal new class Node : TreeSet<T>.Node
    {
        public Node(T t) : base(t) {}

        public int Depth
        {
            get
            {
                if (left == null && right == null)
                    return 0;
                else if (left == null)
                    return right.Depth + 1;
                else if (right == null)
                    return left.Depth + 1;
                else
                    return Max(left.Depth, right.Depth) + 1;
            }
        }

        public override void Insert(T t)
        {
            base.Insert(t);

            //Do the AVL balancing stuff
        }
    }
}

已经有一个问题 -left和right变量在父类中声明为 be TreeSet<T>.Node，而不是AvlTree<T>.Node。但我需要Depth变量来确定是否需要平衡。当然，我可以投射它们，但这不起作用，因为节点是在父节点中创建的Insert()函数，并且不会是正确的类。我当然可以将所有代码复制到一个新的非扩展类中，但这是很多重复的代码，而且大部分都是相同的。（我也可能制作一棵红黑树或 Splay 树，除了平衡算法之外，它们也基本相同。）最终，为所有此类 BST 拥有一个父类可能很有用，因此我可以更改哪棵树我正在使用的类型而不使用树更改代码。（在这完全实现之前，很难说哪种平衡算法会表现得更好。）

有什么好的方法来处理这种事情吗？也就是说 - 确保left和right变量存储适当的子类，并创建为正确的类，即使它们是由父类创建的？或者在这种情况下甚至尝试重用代码只是一个错误，尽管有重复的代码，我还是最好将 AvlTree 与 TreeSet 完全分开？

4

0 回答 0