pointers - C++ Binary Search Tree Insertion functions -
helly everyone,
i took c++ coding course practically no prior knowledge(my understanding of pointers still shakey)at university semester. have implement binary search tree in c++ , problem follows: on predefined node structure values , pointers left , right node supposed implement several functions, 2 of them being:
void insertnode(node* root, node* node)
which supposed fit handed node given tree "root", , 1 called
void insertvalue(node* root, int value)
which should create new instance of node struct passed value , fit in given tree "root". supposed use both createnode (simple function create node* pointer of new node instance int value , left/right pointers set null) , insertnode.
im kind of running in treadmill here , dont think understand how functions supposed work(eg. difference between them). yesterday wrote function:
void insertnode(node* root, node* node){ if(root == null){ root = createnode(node->value); } else if(root->value < node->value){ if(node->left != null){ insertnode(root, node->left); } else{ node->left = createnode(root->value); } } else if(root->value > node->value){ if(node->right != null){ insertnode(root, node->right); } else{ node->right = createnode(root->value); } } }
since im not able test these functions without later functions build tree given nodes curious if here next functions insertvalue(what supposed insertnode doesnt already? :s)
greetings , in advance.
initial note: answer assumes insertnode
function called root
being root of tree, , node
being node insert tree.
one problem statement:
root = createnode(node->value);
since argument root
passed value, means copied, assignment change local copy. once function returns original pointer pass function not have changed.
you need pass pointer by reference, meaning root
argument references original variable passed in function, instead of being copied. using ampersand when declaring argument:
node*& root
the above means root
reference pointer node
.
so complete insertnode
declaration should like
void insertnode(node*& root, node* node)
there other problems, example these lines not correct:
if(node->left != null){ insertnode(root, node->left); } else{ node->left = createnode(root->value); }
this not correct because node->left
should null
always, makes create new node using value root
of tree, , assign node->left
, never insert node
in tree.
what should instead simply
insertnode(node->left, node);
of course should same change setting right branch.
combining 2 solutions above, function like
void insertnode(node*& root, node* node) { if (root == 0) root = node; else if (root->value < node->value) insertnode(root->left, node); else insertnode(root->right, node); }
this function solves third problem current code: if node->value
equal root->value
? above function puts in right branch.
Comments
Post a Comment