c++ 如何在AVL-Tree中设计BST的继承

r6hnlfcb 于 2023-05-08 发布在其他

关注(0)|答案(2)|浏览(147)

我想知道如何正确地实现AVL树的基础上现有的二叉搜索树。
有一个模板Node类存储键和节点数据（如字典），指向子树的指针。

template <class T>
class Node
{
private:
    T _data;
    int _key;
    Node* _left, * _right;

public:
    friend class BinaryTree<T>;
}

模板类Tree存储指向树的根和不变量的指针。

template <class T>
class BinaryTree
{
private:
    Node<T>* _root;
    int _height,
        _order;
}

所以，我想通过简单地覆盖添加，删除（通过使函数虚拟）来继承这个树。很明显，AVL是二叉树，唯一的区别是它总是平衡的。
但是有一个问题-Node类。对于AVL，它应该包含一个相对于根的高度，对于BST，这是不必要的，我不知道如何解决这个冲突没有解决办法。

c++

来源：https://stackoverflow.com/questions/76148703/c-how-to-design-inheritance-of-bst-in-avl-tree

2条答案

按热度按时间

piah890a1#

您的BinaryTree类允许您将任意数据与每个节点相关联，因此只需使用它：

template<class T>
class AvlTree<T> : BinaryTree<std::pair<T,int>> {
 ...
}

赞(0）回复(0）举报 2023-05-08

umuewwlo2#

在所有的罪恶中，我选择了最少的：我在模板中添加了一个默认参数来接受节点类型，在类的主体中，我用模板类型替换了旧的Node类型：

template <typename T, class TypeNode = Node<T>>
class BinaryTree{
    ...
    BinaryTree(BinaryTree<T, TypeNode>&& other) noexcept;
    ...
    TypeNode* find(int) const;
    ...
};

与此同时，初始化保持不变：

BinaryTree<int> tree(key, data, 16); // 16 - size of arrays key & data

对于AVL树，我编写了自己的节点容器（最小代码重复）：

template <typename T>
class AVLNode
{
public:
    T _data;
    int _key;
    AVLNode* _left, * _right;
    int _height;

public:
    friend class AVLTree<T>;        
    ...
}

好吧，继承了树本身，将AVLNode替换为容器：

template <typename T, class TypeNode>
class AVLTree : public BinaryTree<T, AVLNode<T>>
{
public:
    AVLTree() : BinaryTree<T, AVLNode<T>>() {
    }
    ...
}

为了优化解决方案，您需要继承AVL节点本身。我遇到了以下问题：

template <typename T>
class AVLNode : public Node<T> 
{
protected:
    int _height;

public:
    friend class AVLTree<T>;
    ...
};

对于这种结构，节点指针仍然保持不是avl，因此存在两个选项：
1.要使它们私有，用正确的类型将它们添加到AVL和BST中-代码重复，那么继承的原因是什么呢？
1.为节点创建与BST相同的模板参数，但使用默认参数时会出现问题：它将是一个类，其模板参数是-编译错误。如何解决是一个问题。

赞(0）回复(0）举报 2023-05-08

我来回答

c++ 如何在AVL-Tree中设计BST的继承

2条答案

相关问题

热门标签

最新问答