Insert and delete of binary search tree

Title: create a class, the data member of the class when a binary search tree, the external interface has to add nodes and delete nodes these two methods. Users don't care about binary trees. We are asked to give the structure of the class and the methods in the implementation class.

Train of thought
Add node:
It is very easy to add nodes, we just need to find the corresponding position of the node line, and there is no requirement to be a balanced binary search tree, so every time to add nodes are on the leaf node operation, do not need to modify the overall structure of the binary search tree. To find out where the added node is in the binary search tree, you can do this in a loop. Determine the size of the insertion node and the current header node. If the size is greater than the header node, continue to search the right subtree; if the size is less than the header node, continue to search the left subtree. Until the leaf node is found, insert node operation. If the inserted node is equal to the value of the current node in the binary search tree, the insert operation exits and the user is informed that the node already exists.

Delete node:
Deleting nodes is tricky because you need to adjust the structure of the tree, because deleting nodes does not necessarily occur on the leaf. If you delete a leaf node, then the operation is very simple, just do the corresponding delete can be, but if you delete a non-leaf node, then you need to adjust the structure of the binary search tree. There are two strategies to adjust. Suppose that the node that needs to be deleted is A,

1. Find the maximum node B in the left subtree of node A and adjust B to the original position of node A.
2. Find the minimum value of node C in the right subtree of node A and adjust it to the original position of node A.

There are a lot of complex pointer operations involved. In the following code example, the node deletion operation is not completed. I will make a further study when I have time.

Code sample

#include<iostream>
#include<stdlib.h>
#include<cassert>
using namespace std;
//Binary tree node
struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};
class BST
{
public:
    BST(int value);//The constructor
    ~BST();//The destructor
    void AddNode(int value);//Add a node
    void DeleteNode(int value);//Delete nodes
    BinaryTreeNode* CreateBinaryTreeNode(int value);// To create a Binary tree node
    void InOrderPrintTree();//In the sequence traversal
    void InOrderPrintTree(BinaryTreeNode* pRoot);//In the sequence traversal
    BinaryTreeNode* GetMaxNode(BinaryTreeNode* pNode);//Find the maximum value of the binary search tree
    BinaryTreeNode* GetMinNode(BinaryTreeNode* pNode);//Find a binary search tree minimum
private:
    BinaryTreeNode* pRoot;
};
//The constructor
BST::BST(int value)
{
    pRoot=CreateBinaryTreeNode(value);
}
//The destructor
BST::~BST()
{
    delete pRoot;
    pRoot=NULL;
}
// create Binary tree node
BinaryTreeNode* BST::CreateBinaryTreeNode(int value)
{
    BinaryTreeNode* pNode=new BinaryTreeNode();
    pNode->m_nValue=value;
    pNode->m_pLeft=NULL;
    pNode->m_pRight=NULL;
    return pNode;
}
//Find the maximum value of the binary search tree
BinaryTreeNode* BST::GetMaxNode(BinaryTreeNode* pNode)
{
    assert(pNode!=NULL); //Use assertions to ensure that the incoming header is not empty
    //The maximum value is in the right subtree, so walk through the right subtree until the pNode is equal to the right subtree. If there is only one node, the pNode is returned directly
    while(pNode->m_pRight!=NULL)
    {
        pNode=pNode->m_pRight;
    }
    return pNode;
}
//Find a binary search tree minimum
BinaryTreeNode* BST::GetMinNode(BinaryTreeNode* pNode)
{
    assert(pNode!=NULL); //Use assertions to
    //The minimum is in the left subtree, and the whole idea is the same as the maximum.
    while(pNode->m_pLeft!=NULL)
    {
        pNode=pNode->m_pLeft;
    }
    return pNode;
}
// Binary search tree Add a node
void BST::AddNode(int value)
{
    BinaryTreeNode* pInsertNode=CreateBinaryTreeNode(value);//Initialize the nodes that need to be created.
    BinaryTreeNode* pNode=pRoot;
    while(true)
    {
        //If the inserted value already exists in the binary search tree, the insert operation is not performed and the loop is broken.
        if(pNode->m_nValue==value)
        {
            cout<<" The node value already exists "<<endl;
            break;
        }
        //If the node to be inserted is smaller than the current header node, continue to search the left subtree
        else if(pNode->m_nValue > value)
        {
            if(pNode->m_pLeft==NULL)//If the current header node is a leaf node, insert the pending node directly into the left subtree, and then jump out of the loop
            {
                pNode->m_pLeft=pInsertNode;
                break;
            }
            else//Otherwise continue traversing its left subtree
                pNode=pNode->m_pLeft;
        }
        //The idea is the same as above
        else if(pNode->m_nValue < value)
        {
            if(pNode->m_pRight==NULL)
            {
                pNode->m_pRight=pInsertNode;
                break;
            }
            pNode=pNode->m_pRight;
        }
    }

}
//unfinished
void BST::DeleteNode(int value)
{
    BinaryTreeNode* pNode=pRoot;
    while(true)
    {
        if(pRoot->m_nValue==value)//If it's a header
        {
            if(pRoot->m_pLeft!=NULL)
            {
                BinaryTreeNode* pLeftMaxNode=GetMaxNode(pRoot->m_pLeft);
            }
            else if(pRoot->m_pRight!=NULL)
            {
            }
            else
            {
                delete pRoot;
                pRoot=NULL;
            }
        }
        if(pNode->m_nValue==value)
        {
            if(pNode->m_pLeft!=NULL)
            {
            }
            else if(pNode->m_pRight!=NULL)
            {
            }
            else
            {
            }
        }
    }
}
void BST::InOrderPrintTree(BinaryTreeNode* pRoot)//In the sequence traversal
{
    if(pRoot!=NULL)
    {
        //If the left subtree is not empty, the left subtree is traversed
        if(pRoot->m_pLeft!=NULL)
            InOrderPrintTree(pRoot->m_pLeft);
        //Traverse the leaf nodes of the left subtree
        cout<<"value of this node is "<<pRoot->m_nValue<<endl;
        //If the right subtree is not empty, traverse the right subtree
        if(pRoot->m_pRight!=NULL)
            InOrderPrintTree(pRoot->m_pRight);
    }
    else
    {
        cout<<"this node is null."<<endl;
    }
}
// Because you have to do it recursively In the sequence traversal , so you also need to call one with arguments In the sequence traversal function 
void BST::InOrderPrintTree()//In the sequence traversal
{
    InOrderPrintTree(pRoot);
}
void main()
{
    BST* b=new BST(10);//The binary search tree header is defined when the class is initialized, thus eliminating the judgment that the header is null
    b->AddNode(6);
    b->AddNode(14);
    b->InOrderPrintTree();
    system("pause");
}