This is not a homework problem. I am studying binary search trees and trying to understand how the code works. I have the code, it works, but I want to understand it completely.
I have made comments of what I think code does and in the lines that I don't understand or not sure I have placed question marks in the beginning and at the end of comments that I would like someone with knowledge to help me learn it.
I am trying to follow this code by inserting number 2 in sample binary search tree I created in attached excel document. I would like to understand step by step how pointers move and how ultimately new node is inserted. I would like someone to take a look at attached file and below code and better clarify comments and make modifications to excel pointers if I am not reading it correctly.
I know this seems a lot of work, but I really appreciate your help. Please help as much as you can.
class BinarySearchTree
{
private:
struct tree_node //Node that contains two pointers and data field
{
tree_node* left; //pointer to the left subtree
tree_node* right; //pointer to the right subtree
int data; //data contained in this node
};
tree_node* root; //???Is this creating pointer root to first node????
public:
BinarySearchTree()
{
root = NULL; //???start with empty binary search tree????
}
bool isEmpty() const
{
return root==NULL; //if root=0 return TRUE, otherwise return false
}
void print_inorder();
void inorder(tree_node*); //???recursive function, but I don't understand why we need tree_node*???
void print_preorder();
void preorder(tree_node*); //???recursive function, but I don't understand why we need tree_node*???
void print_postorder();
void postorder(tree_node*); //???recursive function, but I don't understand why we need tree_node*???
void insert(int); //function to insert data in BST
};
// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)//Function to insert numbers
{
tree_node *t = new tree_node; //Create new node t same as our original node in class defined earlier
tree_node *parent; //??? Don't understand if this is a pointer to above node or something else????
t->data = d; //Insert number in our node
t->left = NULL; //put NULL in left side of new node
t->right = NULL; //put NULL in right side of new node
parent = NULL; //????Why is this needed????
// is this a new tree?
if(isEmpty()) root = t; //Check if tree is empty
//If isEmpty TRUE then new node t points to same thing as root
else
{
//Note: ALL insertions are as leaf nodes
tree_node* curr; //define new pointer curr
curr = root; //points to same thing as root
// Find the Node's parent
while(curr) //while curr!=NULL
{
parent = curr; //????parent and curr point to the same thing while curr!=NULL
if(t->data > curr->data) curr = curr->right; /*????If input is > than whats in currently, move
pointer curr to right node. What is the purpose of this code????*/
else curr = curr->left; /*????If input is < than whats in curr data, move
pointer curr to left node. What is the purpose of this code????*/
}
if(t->data < parent->data) /*???I can see that this insert the node in correct place
but don't understand how this is connected to previous few lines of code */
parent->left = t;
else
parent->right = t;
}
}
