Design a BST in C++
Required classes:
- Node
- Tree
- Iterator
Node
//BSTNodeInt.h
class BSTNodeInt{
public:
BSTNodeInt* left;
BSTNodeInt* right;
BSTNodeInt* parent;
int const data;
BSTNodeInt(const int & d);
};
Above is the header file of a node.
left, right, parent should be pointer, otherwise this data structure will be recursive and the compiler can never find out the size of a BSTNodeInt.
The variable "data" should be const, because we don't want people to change it. If data is changed, the structure of the BST should change at the same time.
The parameter of the constructer is pass by const references. This is not necessary. It can also be pass by value.
//BSTNodeInt.cpp
#include "BSTNodeInt.h"
BSTNodeInt::BSTNodeInt(const int & d)
: data(d) {
left = right = parent = nullptr;
}
Above is the cpp file of a node.
: data(d) is initializer list. It is used for initializing member variables.
We can't assign value to member variable data because it is const.
We can add more variable to the initializer list by separating them with commas.
//bstTest.cpp
#include "BSTNodeInt.h"
#include <iostream>
using namespace std;
int main(){
BSTNodeInt n1(5);
BSTNodeInt* n2 = new BSTNodeInt(5);
delete n2;
}
The first way of declaring a BSTNodeInt is by automatic memory allocation. -> source the object directly
The second way of declaring a BSTNodeInt is by dynamic memory allocation. -> store the memory address of this object
C++ Noted: In the second way, if I want to access the member variable in BSTNodeInt, I should use: n2 -> data, instead of n2.data