C++

Forum

 
Binary Search Tree VS Linked List

csstudent123 (409)
What is the difference between BST and linked list? Or are BST implemented through linked list?
kbw (9488)
csstudent123 (409)
But I seen some examples where BST implemented through linked list
kbw (9488)
They both have links, but I think you're mistaken.
csstudent123 (409)
I am writing this code with my understanding of BST..please tell me if it is ok:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
in .h

class bst {

    private:

        struct hwareItem{
		char barcode[10];
		/*char description[50];
		float price_per_unit;
		int stock;*/

		hwareItem *left;
		hwareItem *right;

		};
		hwareItem *root;

    public:
        bst();
        ~bst();

        void addNode(hwareItem*&, char[]);

};

i
in .cpp

void bst::addNode(hwareItem*& root, char barcode[]){


    if(root==NULL){
        root=new hwareItem;
        strcpy(root->barcode, barcode);
        root->left=NULL;
        root->right=NULL;
        }


    else if(root!=NULL){

        if(root->left->barcode<root->barcode)
            addNode(root->left,barcode);

        else if(root->right->barcode>root->barcode)
             addNode(root->right,barcode);
    }

}

How do I implement this in main?

#include<iostream>
#include<fstream>
#include<cstring>
#include"bst.h"

using namespace std;

int main(){

    bst val;
    char bar[10];

    
    strcpy(bar, "5505505");
    val.addNode(? , bar);

    return 0;
}
Last edited on
dhayden (5795)
The problem is that root should be a member of bst, not hwareItem. Make that change. Also you have to compare c strings with strcmp.

Then create a constructor for bst that initializes root to NULL.

Then line 68 is simply:
val.addNode(val.root, bar);

A few other things:

- create a constructor for hwareItem that initializes the pointers to NULL.
- Can can simplify addNode:
1
2
3
4
5
6
7
8
 
if (root == NULL) {
        root=new hwareItem;
        strcpy(root->barcode, barcode);
} else if (strcmp(root->left->barcode, root->barcode) < 0)) {
            addNode(root->left,barcode);
} else {
            addNode(root->right,barcode);
}


Requiring the bst user to know about the root member is awkward. You can avoid that having a simple public addNode() that calls a more complex private version:

1
2
3
4
5
 
class bst {
public:
    void addNode(char bar[]) {addNode(root, bar); }
private:
    void addNode(hwareNode * &root, char bar[]);

csstudent123 (409)
member of bst of what type?

type *root?

void* root?
am getting segmentation fault: 

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
29
30
31
32
33
 
void bst::addNode(hwareItem*& root, char barcode[]){


   if (root == NULL) {
        root=new hwareItem;
        strcpy(root->barcode, barcode);
        root->left=NULL;
        root->right=NULL;
} else if(strcmp(root->left->barcode, root->barcode) < 0) {
            addNode(root->left,barcode);
            }
    else {
        addNode(root->right,barcode);
        }

    }

int main(){

    bst val;
    char bar[10], bar1[10];


    strcpy(bar, "5505505");
     val.addNode(bar);
    strcpy(bar1, "1010101");

    val.addNode(bar);
     val.addNode(bar1);
    //val.printNodes();

    return 0;
}


can add only root value
Last edited on
Topic archived. No new replies allowed.