首页 文章

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

提问于
浏览 次
1

我在c＃中创建了一个二叉搜索树类 . 我是通过从二叉树类派生来创建类的，因为二叉搜索树是一种二叉树 . 所以我将在二叉树类中包含大多数常用方法，并在二叉搜索树中共享它们 .

现在：BinaryTree类有两个方法“AddToLeft”和“AddToRight”方法，这两个方法必须能够在这个类之外访问，即在Main方法中将节点添加到二叉树中 . 所以我把它们公之于众 . 并且这两个方法也应该可以在二进制搜索树类（重用）中访问，以根据条件将节点添加到binarysearchtree .

但是现在因为Insert方法是binarysearchtree将节点插入BST但是AddToLeft和AddToRight不是 . 所以这两个方法不应该暴露给BST对象上我的二叉搜索树的客户端（外部世界） . 如何设计这个课程 .

我试过了：

  • 使这两个方法密封在binarytree类中，它没有帮助 .

  • 在基础上声明它们是公共的并且在派生中受到保护 . 这也没有帮助，因为公共不能在派生类中被继承为受保护 .

请帮助设计课程 .

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
    }
}
c# oop data-structures binary-tree binary-search-tree

3 回答

  • 0

    键入代码时要尝试做的是一个矛盾 . 你说你的 class 是 BinaryTree 的类型，但是你不想遵守使它成为 BinaryTree 的 Contract .

    我可能会做的不是从 BinaryTree 派生而是有一个私有字段，在 BinarySearchTree 类中保存 BinaryTree 并在 BinaryTree 中公开要通过公共访问器公开的功能（所以 BinarySearchTree 不再是一种二叉树，但是仍然可以通过使用 BinaryTree 实例初始化的私有字段访问该功能 . ）

    我当然可以理解使 BinarySearchTree 成为 BinaryTree 类型的吸引力，但要么放弃这两种方法的封装，要么放弃基类型的分类 . 您可以't claim to meet the requirements of classification of the base type when you aren' t提供相同的外部API .

    如果你真的想要尝试像上面那样做，你可以覆盖你不希望客户端使用的方法，并从这些方法中抛出 InvalidOperationException . 但是这不是在编译时帮助你，而只会在运行时抱怨，这不是谨慎的设计 .

    回复于
  • 0

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

    谢谢

    回复于
  • 2

    更多关于矛盾 - 它是一个形而上学问题：BinarySearchTree不是BinaryTree，如果BinaryTree的定义是它必须能够执行左右添加 . 如您所知，BinaryTree是一个结构，每个节点有两个子节点 . BinarySearchTree不是BinaryTree，而是基于密钥的排序列表，它使用BinaryTree进行内部存储 .

    第一个是结构，第二个是更高级别的结构，具有特定的内部存储结构和算法 . BinarySearchTree可能是Dictionary的最佳子类，其中KeyType是索引类型，ValueType是存储在每个节点（可以是一组）的类型 . 您希望能够将具有键的元素添加到集合中，并稍后通过该键将其拉回，并带来一些额外的好处（可能需要排序遍历等） . 这是一个字典扩展，而不是BinaryTree扩展，所以你的方法是将它包装起来，我将实现IDictionary .

    回复于

相关问题