Clever Geek Handbook

Overriding a structure defined in a base class from a derived class

I have created a class (named BST) for a binary search tree in C ++ and am now trying to create a class (named AVL) for AVL trees that inherits from the BST class. I have defined a struct (called a node) inside my BST class and would now like to add extra member height to it when used in an AVL derived class. I cannot find a way to override the struct and add an extra member to it only when it is used for an AVL class. Here is my code for the BST class:

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);

};

And my incomplete code for the AVL class:

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)

};

I've tried using struct inheritance like this:

struct avlnode : node
{
    int height;
};

But the problem here avlnode->left

and avlnode->right

is it is type node*

instead of type avlnode*

and so I cannot access the height element from them.

Any help would be greatly appreciated: D

+3


source to share


2 answers


In the OP, the derived class was named AVLTree

. Unfortunately the OP is not an MCVE . "Fascinating" implementation details are not considered (or even not yet developed). After remembering how the AVL tree works , I decided to just ignore it. Thus, I just want to show how the classes could be obtained:

Note. I have split the example code to prevent nested scroll boxes.

Source trees.cc

:

First, some headers of the standard library I want to use:

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

Base class declaration BTree

:

class BTree {

starting with the built-in class for nodes:

  // 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 ...

  // variables:
  protected:
    Node *_pRoot;

... and methods.

  // 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);

};

Implementation of internal methods:

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);
}

Derived class for 2 nd tree :



class BTree2: public BTree {

starting with the built-in class for derived nodes:

  // 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 << ")";
      }
    };

... no variables, but some derived methods ...

  // 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);
};

... and implementation:

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);
}

Last but not least, with a little test:

// 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;
}

I have uploaded the sample to ideone.com .

I have compiled and tested it with gcc in cygwin on Windows 10:

$ 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...


$

Notes:

  • Representing virtual methods in struct Node

    allows you to use dynamic_cast<>()

    . AFAIK, dynamic_cast<>()

    can only be applied to pointer types. So I just did a C-cast (i.e. (Node*&)

    ), which C ++ purists really don't like.

  • insert()

    class BTree2

    does not use any attachments for class BTree

    . This is to ensure that every node in the tree actually exists BTree2::Node

    .

  • BTree::print()

    does not need to be overloaded due to virtual methods Node::print()

    .

This diagram just shows some ways to reuse code.

Templates are just another possibility. The standard library (like std :: set <> ) gives an example of what it might look like.

+1


source


If you are using structure inheritance, the Derived class inherits the struct node as is and you get node * instead of avlnode *.

You can now override the structure of the node in a derived class, which will hide the node in the parent and prefer



Perhaps you can declare a height variable in the node of the parent class and only use it in the derived class, or declare vector<int> heights

in the Derived class and store the heights there.

Also, declare the struct node outside the class and use an instance of it as a member of your classes.

0


source






More articles:


All Articles