c++ - 从派生类重新定义基类中定义的结构

我为C++中的Binary Search Tree创建了一个类(名为BST)，现在尝试为继承BST类的AVL树创建一个类(名为AVL)。我已经在BST类中定义了一个结构(命名节点)，现在想在派生的AVL类中使用它时，为其添加一个额外的成员“高度”。我找不到一种方法来重新定义该结构并仅在将其用于AVL类时向其添加额外的成员。
这是我的BST类代码:

class BST
{
protected:
struct node
{
    int val;
    node* left;
    node* right;
};
node* root;

public:
BST()
{
    this->root = NULL;
}
void insert(int val);
void display();
void displayPretty();
void displaySorted();
int min();
int max();
int height();
void remove(int val);
int after(int val);
int before(int val);
static bool isBST(BST tree);
~BST()
{
    removeAll(this->root);
}

protected:
node* create(int val);
node* insertInto(node* root,int val);
void displayLevelOrder(queue<node*>* q);
void displayPretty(node* p, int indent);
void displayInorder(node* root);
node* getMin(node* root);
node* getMax(node* root);
int heightOf(node* root);
node* removeFrom(node* root,int val);
void removeAll(node* root);
node* getSuccessorOf(int val,node* root,node* prev);
node* getPredecessorOf(int val,node* root,node* next);
static bool isBST(node* root,int min,int max);

};

我对AVL类的不完整代码是:

class AVL : public BST
{
protected:
struct node
{
    // redefine node here (by adding the 'height' member)
    // such that all the node variables/pointers in BST (e.g. root)
    // also get created with this new definition
};

public:
AVL() : BST(){}
void insert(int val);
void remove(int val);

private:
node* insertInto(node* root,int val);
node* removeFrom(node* root,int val)

};

我试过像这样使用结构继承:

struct avlnode : node
{
    int height;
};

但是这里的问题是avlnode->left和avlnode->right是node*类型而不是avlnode*类型，因此我无法从它们访问height成员。

任何帮助，将不胜感激:D

最佳答案

在OP中，派生类名为AVLTree。不幸的是，OP不是 MCVE 。 “令人兴奋的”实现细节被遗漏了(甚至尚未开发)。回顾了 AVL Tree 的工作原理后，我决定忽略它。因此，我只想简单地说明如何派生类:

注意:我拆分了示例代码，以防止嵌套滚动框。

源trees.cc:

首先，我要使用的标准库的一些 header :

#include <iostream>
#include <iomanip>
#include <string>

基类BTree的声明:

class BTree {

从节点的嵌入式类开始:

  // types:
  protected:
    struct Node {
      int value;
      Node *pLeft, *pRight;

      // constructor.
      Node(int value): value(value), pLeft(nullptr), pRight(nullptr) { }
      // destructor.
      virtual ~Node() { delete pLeft; delete pRight; }
      // disabled:
      Node(const Node&) = delete;
      Node& operator=(const Node&) = delete;

      // prints node.
      virtual void print(std::ostream &out)
      {
        out << "Node " << value;
      }
    };

...变量...

  // variables:
  protected:
    Node *_pRoot;

...和方法。

  // methods:
  public:
    // constructor.
    BTree(): _pRoot(nullptr) { }
    // destructor.
    ~BTree() { delete _pRoot; }
    // disabled:
    BTree(const BTree&) = delete;
    BTree& operator=(const BTree&) = delete;

    // inserts a node.
    bool insert(int value) { return insert(_pRoot, value); }
    // prints the tree.
    void print(std::ostream &out, bool inOrder)
    {
      if (_pRoot) {
        if (inOrder) printInfix(out, _pRoot, 0);
        else print(out, _pRoot, 0);
      } else out << "EMPTY." << std::endl;
    }

  // internal methods:
  protected:
    // creates and inserts a node.
    bool insert(Node *&pNode, int value);
    // prints a sub-tree.
    void print(std::ostream &out, Node *pNode, int indent);
    // prints a sub-tree in order.
    void printInfix(std::ostream &out, Node *pNode, int indent);

};

内部方法的执行:

bool BTree::insert(Node *&pNode, int value)
{
  if (!pNode) {
    pNode = new Node(value);
    return true;
  }
  if (value == pNode->value) return false; // ERROR!
  return insert(
    value < pNode->value ? pNode->pLeft : pNode->pRight, value);
}

void BTree::print(std::ostream &out, Node *pNode, int indent)
{
  out << std::setw(indent) << "";
  pNode->print(out);
  out << std::endl;
  indent += 2;
  if (pNode->pLeft) print(out, pNode->pLeft, indent);
  if (pNode->pRight) print(out, pNode->pRight, indent);
}

void BTree::printInfix(std::ostream &out, Node *pNode, int indent)
{
  if (pNode->pLeft) printInfix(out, pNode->pLeft, indent + 2);
  out << std::setw(indent) << "";
  pNode->print(out);
  out << std::endl;
  if (pNode->pRight) printInfix(out, pNode->pRight, indent + 2);
}

第二棵树的派生类:

class BTree2: public BTree {

从派生节点的嵌入式类开始:

  // types:
  protected:
    struct Node: public BTree::Node {
      int height;

      // constructor.
      Node(int value, int height):
        BTree::Node(value), height(height)
      { }
      virtual ~Node() = default;
      // disabled:
      Node(const Node&) = delete;
      Node& operator=(const Node&) = delete;

      // prints node.
      virtual void print(std::ostream &out)
      {
        out << "Node " << value << " (height: " << height << ")";
      }
    };

...没有变量，但有一些派生方法...

  // methods:
  public:
    // constructor.
    BTree2(): BTree() { }
    // destructor.
    ~BTree2() = default;
    // disabled:
    BTree2(const BTree2&) = delete;
    BTree2& operator=(const BTree2&) = delete;

    // inserts a node.
    bool insert(int value)
    {
      return insert((Node*&)_pRoot, value, 0);
    }

  // internal methods:
  protected:
    // creates and inserts a node.
    bool insert(Node *&pNode, int value, int height);
};

...以及实现:

bool BTree2::insert(Node *&pNode, int value, int height)
{
  if (!pNode) {
    pNode = new Node(value, height);
    return true;
  }
  if (value == pNode->value) return false; // ERROR!
  return insert(
    (Node*&)(value < pNode->value ? pNode->pLeft : pNode->pRight),
    value, pNode->height + 1);
}

最后但并非最不重要的一点是，主要功能有一个小测试:

// main function
int main()
{
  // some test data
  int data[] = { 3, 7, 21, 2, 12, 1, 104, 13 };
  enum { nData = sizeof data / sizeof data[0] };
  // binary tree
  { std::cout << "Binary Tree:" << std::endl;
    BTree bTree;
    std::cout << "Build..." << std::endl;
    for (int value : data) bTree.insert(value);
    std::cout << "Print Hierarchy..." << std::endl;
    bTree.print(std::cout, false);
    std::cout << "Print Sorted..." << std::endl;
    bTree.print(std::cout, true);
    std::cout << "Destroy..." << std::endl;
    std::cout << std::endl;
  }
  // derived binary tree
  { std::cout << "Derived Binary Tree:" << std::endl;
    BTree2 bTree;
    std::cout << "Build..." << std::endl;
    for (int value : data) bTree.insert(value);
    std::cout << "Print Hierarchy..." << std::endl;
    bTree.print(std::cout, false);
    std::cout << "Print Sorted..." << std::endl;
    bTree.print(std::cout, true);
    std::cout << "Destroy..." << std::endl;
    std::cout << std::endl;
  }
  // done
  return 0;
}

我将样本上传到 ideone.com 。

我在Windows 10上的cygwin中使用gcc进行了编译和测试:

$ g++ -std=c++11 -o trees trees.cc

$ ./trees.exe
Binary Tree:
Build...
Print Hierarchy...
Node 3
  Node 2
    Node 1
  Node 7
    Node 21
      Node 12
        Node 13
      Node 104
Print Sorted...
    Node 1
  Node 2
Node 3
  Node 7
      Node 12
        Node 13
    Node 21
      Node 104
Destroy...

Derived Binary Tree:
Build...
Print Hierarchy...
Node 3 (height: 0)
  Node 2 (height: 1)
    Node 1 (height: 2)
  Node 7 (height: 1)
    Node 21 (height: 2)
      Node 12 (height: 3)
        Node 13 (height: 4)
      Node 104 (height: 3)
Print Sorted...
    Node 1 (height: 2)
  Node 2 (height: 1)
Node 3 (height: 0)
  Node 7 (height: 1)
      Node 12 (height: 3)
        Node 13 (height: 4)
    Node 21 (height: 2)
      Node 104 (height: 3)
Destroy...


$

笔记:

在struct Node中引入虚拟方法可启用dynamic_cast<>()。 AFAIK，dynamic_cast<>()只能应用于指针类型。因此，我只是做了C-cast(即(Node*&))，这是C++纯粹主义者实际上不喜欢的。

insert()的class BTree2不使用class BTree的任何插入内容。必须确保树中的每个节点实际上都是BTree2::Node。

由于使用了虚拟的BTree::print()方法，因此无需重载Node::print()。

该设计仅显示了一些重用代码的方法。

模板只是一个不同的机会。标准库(例如std::set<>)提供了一个外观示例。

关于c++ - 从派生类重新定义基类中定义的结构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44062603/