Delete BST up, left, right code

Is my setting of up/parent node correct?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void bst::addNode(bst::hwareItem*& root, hware item){


   if (root == NULL) {
        root=new hwareItem;
        strcpy(root->barcode, item.bar);

        root->up=root; //or root->up=NULL;  ???
        root->left=NULL;
        root->right=NULL;

} else if(strcmp(root->barcode, item.bar)<0){

        addNode(root->left, item);

}
    else{

        addNode(root->right, item);
        }
    }

void bst:: addNode(hware item){

    addNode(root, item);


It may depend on your design. If up is a backlink to a nodes parent node then you need a reference to this parent node. But your code does'nt provide it to addNode().

It would be nice to have some more detailed infos about your design. It seems, that you have a binary search tree of type bst which adds nodes of type hwareItem.

I would need a node type only. An instance gets its item on construction. It asks one of its childs to enter a new node with item. If the child doesn't exists it would create it.

You may also think about the case where a new items barcode equals an existing nodes barcode.

1
2
3
4
5
6
7
8
9
10
class Node
{
private:
    std::string barcode;
    Node *left, *right, *up;

public:
    Node(const Node * const parent; const hware &item);
    void addNode(const hware &item);
};


EDIT: Added attribute up and moved parameter parent from addNode to constructor.
Last edited on
so should I use

root->up=root; or root->up=NULL; ???

my class is

class Node
{
private:
struct node{
char barcode;
node *left, *right, *up;
}
node* root;
......}
I assume that yo no longer use class bsd and hwareItem? Further I think you won't store only one character as barcode. Next I'm wondering why you need the attribute root. But ok, we'll use it... And last but not least an object of your class cannot understand any message because there are no method declarations given. So we'll better take those ones given in my example above. Ah, and why do you encapsulate some attributes into a seperate struct?

And did you think about the equal case? What to do if an items barcode is just part of the tree?

The constructor initializes all attributes, where left and right will get the NULL and up will be our given parent. Ok, and it takes a third argument, namely theRoot to be assign to our attribute root.

addNode() also gets root as second argument to be used for Node construction. AddNode checks whether the given items barcode is less equal or greater than ourselfs. In the equal case we don't have to do any more because I've decided that we don't add a barcode twice. In case of left or right we've to check if we have a children there. If so we transfer control of entering the new item to it by asking it to addNode(item, root). If there's no children we create one and do enter it at left or right respectively. On creation we give ourself as the new nodes parent. This may in fact answer your question what to assign to up?

That's it I hope.
I think its clear now....Pointing to root at every new null node creation will point to parent recursively

Topic archived. No new replies allowed.