设计继承二叉树类的二叉搜索树类

本文关键字:搜索树 继承 二叉树 | 更新日期: 2023-09-27 17:49:24

我正在c#中创建一个二叉搜索树类。我创建这个类是从一个二叉树类派生出来的因为二叉搜索树也是一种二叉树。因此,我将在二叉树类中使用大多数常用方法,并在二叉搜索树中共享它们。

:BinaryTree类有两个方法"addtolleft"answers"AddToRight"方法,这两个方法必须能够访问类外,即在Main方法中添加节点到二叉树。所以我把它们公开了。这两个方法也应该可以在二叉搜索树类中访问(重用),以便根据条件向二叉搜索树添加节点。

但是现在因为Insert方法是候选的二进制搜索树插入节点到BST,但addtolleft和AddToRight不是。所以这两个方法不应该暴露给BST对象上的二进制搜索树的客户端(外部世界)。如何设计这门课?

I tried:

  1. 使这两个方法在binarytree类中密封,它没有帮助。
  2. 在base中声明为public,在派生中声明为protected。这也没有帮助,因为public不能作为protected在派生类中继承。

请帮忙设计类。

public class BTNode
{
    public int data;
    public BTNode Left { get; set; }
    public BTNode Right { get; set; }
    public BTNode(int data)
    {
        this.data = data;
    }
}
public class BinaryTree
{
    public BTNode Root { get; set;}
    public BinaryTree() : this(null) { }
    public BinaryTree(BTNode node) { Root = node; }
    // this method common for its derived class too
    public void AddToLeft(BTNode current, BTNode node) 
    {
        current.Left = node;
    }
    // this method common for its derived class too
    public void AddToRight(BTNode current, BTNode node)
    {
        current.Right = node;
    }
}
public class BinarySearchTree : BinaryTree
{       
    public BinarySearchTree(int val)
    {
        Root = new BTNode(val);    
    }
    public void Insert(int val)
    {
        BTNode node = new BTNode(val);
        if (Root.data >= val)
            base.AddToLeft(Root, node); // I should be able to call this method here
        else
            base.AddToRight(Root, node); // I should be able to call this method here
    }
}
class Program
{
    static void Main(string[] args)
    {
        BinaryTree bt = new BinaryTree();
        BTNode root = new BTNode(3);
        BTNode node1 = new BTNode(4);
        BTNode node2 = new BTNode(7);
        bt.AddToLeft(root,node1); // i should be able to access this method here.
        bt.AddToLeft(root, node2); // i should be able to access this method here.
        BinarySearchTree bst = new BinarySearchTree(6);
        bst.Insert(4);
        bst.Insert(8);
        // This is the problem.
        // these two methods should not be visible on the bst object.
        // insertion to bst is done only through insert() method
        // but these two methods should be accessible inside the binarysearchtree class
        // to add the nodes.
        bst.AddToLeft(root,node1); // i should not access this method here on this object
        bst.AddToRight(root, node2); // i should not access this method here on this object
    }
}

设计继承二叉树类的二叉搜索树类

当你键入代码时,你想做的是一个矛盾。你说你的类是一种BinaryTree,但你不想履行使其成为BinaryTree的合同。

我可能会做的不是从BinaryTree派生,而是在BinarySearchTree类中拥有BinaryTree的私有字段,并在BinaryTree中通过公共访问器暴露您想要暴露的功能(因此BinarySearchTree不再是二叉树的类型,但仍然可以通过BinaryTree实例初始化的私有字段访问该功能)

我当然可以理解将BinarySearchTree作为BinaryTree类型的吸引力,但是您要么放弃这两个方法的封装,要么放弃基类型的分类。当你没有提供与基本类型相同的外部API时,你不能声称满足基本类型的分类需求。

如果你真的想做你上面所做的事情,你可以覆盖你不希望客户端使用的方法,并从这些方法中抛出InvalidOperationException。但是这不是很优雅,因为它在编译时没有帮助,并且只会在运行时发出抱怨,这是不谨慎的设计。

尝试使用addtolleft和AddToRight方法的private关键字而不是public。因为私有方法只对基类可见。

谢谢

更多的矛盾——这是一个形而上学的问题:如果BinaryTree的定义是它必须能够执行左加和右加,那么BinarySearchTree就不是BinaryTree。如您所知,BinaryTree是一个结构,每个节点有两个子节点。BinarySearchTree不是BinaryTree,而是一个基于键的排序列表,使用 BinaryTree作为内部存储。

第一个是结构,第二个是更高级的结构,具有特定的内部存储结构和相应的算法。BinarySearchTree可能是Dictionary的最好子类,其中KeyType是索引类型,ValueType是存储在每个节点上的类型(可以是一个集合)。您希望能够将具有键的元素添加到集合中,并在稍后通过该键将它们拉回,这还有一些额外的好处(可能是排序遍历等)。这是一个字典扩展,而不是BinaryTree扩展,所以你把它包装起来的方法是正确的,我将实现字典。