C++

Forum

 
Need help Tree

whoovian11 (117)
So I am trying to create a simple binary tree that will ask the user for a command so that is either 'insert or find' and with insert they can put in a number to this tree and with find they can ask if 53 is in this tree and the program will output yes or no..
Help plz.
Last edited on
Smac89 (1727)
Create the binary tree first, then the rest is history
whoovian11 (117)
I am not sure how to create one..I started this by looking at many examples but not sure if i am doing this right
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
 
#include <iostream>
    using namespace std;
    class BTree
    {
       private:
            struct node
            {
               node* left;
               node* right;
               int data;
            };
            node* root;
        public:
            
			BTree();
			void insert(int);
            bool find (int);
            void inorder(node*);
            void preorder(node*);
            void postorder(node*);
            
    };
    int main()
    {
			BTree b;
			int command,i,f,number;
            cout << "Enter command: ";
            cin >> command;
			if (command==i)
			{
			cout<<"Enter a number"<<endl;
			cin>>number;
			b.insert(number);
            }
			if (command==f)
			{
			cout<<"Enter a number"<<endl;
			cin>>number;
			b.find(number);
            }
crochett90 (8)
So by the looks of your solution (or lack there of), I'm guessing you got no idea have you...google binary search tree and maybe that should get you started.
whoovian11 (117)
could you give me like a pseudocode or something like that?
crochett90 (8)
that example looks fine except that it won't work because:

(1) - since your struct node is private, you'd have to create member functions, that goes in the public part of your class BTree, that will access your private members, look up setters and getters. If your quite new to it I'd suggest using setters and getters, otherwise use your class constructor to do it.

(2) - member functions are declared but not defined, they are functions after all and functions need to be declared then defined. You are also missing left and right pointers since trees have branches going left and right.


Example
-----------

//declaration
void postorder(node*);

//definition - define your functions outside your class
void BTree::postorder(root)
{
postorder(root->left);
postorder(root->right);
root->data();
}

this code is what post order traverse looks like but this code will not necessarily work since your node*root pointer is private and so too data.
Trust me its better to understand the concept first do not worry too much about the syntax, that will come later but once you understand the concept then you will see that it will get a lot easier and clearer.
Last edited on
whoovian11 (117)
Am I even going the right way?

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
#include <iostream>
using namespace std;
    class BTree
    {
       private:
            struct node
            {
               node* left;
               node* right;
               int data;
            };
            node* root;
        public:
            BTree()
            {
               root = NULL;
            }
            bool isEmpty() const { return root==NULL; }
			void insert(int);
			bool find(int value);
            void displayinorder();
            void inorder(node*);
            void displaypreorder();
            void preorder(node*);
            void displaypostorder();
            void postorder(node*);
            
    };
    int main()
    {
        BTree n;
        int ch,no;
            
                cout << "Insert node: ";
                cin >> no;
                n.insert(no);
            
            choice:
            
            cout << "Enter your choice: Press 1 for In-Order: 2 for Pre-Order: 3 for Post-Order";
            cin >> ch;
			switch(ch)
           {
               case '1': 
                   cout<<" In-Order Traversal "<<endl;
					n.displayinorder();
                   break;
               case '2': 
                   cout<<" Pre-Order Traversal "<<endl;
                   n.displaypreorder();
                   break;
               case '3': 
                   cout<<" Post-Order Traversal "<<endl;
                   n.displaypostorder();
                   break;
               default:
                   cout << "Invalid entry. Try Again";
                   goto choice;
                   break;                
           }
        system("pause>null");
        return 0;
    }
    void BTree::insert(int d)
    {
        node* t = new node;
        node* parent;
        t->data = d;
        t->left = NULL;
        t->right = NULL;
        parent = NULL;
        if(isEmpty()) root = t;
        else
        {
            
            node* curr;
            curr = root;
            
            while(curr)
            {
                parent = curr;
                if(t->data > curr->data) curr = curr->right;
                else curr = curr->left;
            }
            if(t->data < parent->data)
               parent->left = t;
            else
               parent->right = t;
        }
    }
    void BTree::displayinorder()
    {
      inorder(root);
    }
    void BTree::inorder(node* p)
    {
        if(p != NULL)
        {
            if(p->left) inorder(p->left);
            cout<<" "<<p->data<<" ";
            if(p->right) inorder(p->right);
        }
        else return;
    }
    void BTree::displaypreorder()
    {
        preorder(root);
    }
    void BTree::preorder(node* p)
    {
        if(p != NULL)
        {
            cout<<" "<<p->data<<" ";
            if(p->left) preorder(p->left);
            if(p->right) preorder(p->right);
        }
        else return;
    }
    void BTree::displaypostorder()
    {
        postorder(root);
    }
    void BTree::postorder(node* p)
    {
        if(p != NULL)
        {
            if(p->left) postorder(p->left);
            if(p->right) postorder(p->right);
            cout<<" "<<p->data<<" ";
        }
        else return;
    }
crochett90 (8)
your binary tree shell code looks mostly correct. You will not be able to search anything unless you populate your tree first, currently there is nothing in your tree, its empty. You probably have to manually hard code some numbers to your tree or read some numbers from a file and store those numbers to the tree and then search if a particular number exits in the tree.
whoovian11 (117)
More revised version but still not working .. plz help
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
 
#include <iostream>
using namespace std;
    class BTree
    {
       private:
            struct node
            {
               node* left;
               node* right;
               int data;
            };
            node* root;
        public:
            BTree()
            {
               root = NULL;
            }
            bool isEmpty() const { return root==NULL; }
			void insert(int);
			bool find(int value);
            void displayinorder();
            void inorder(node*);
            void displaypreorder();
            void preorder(node*);
            void displaypostorder();
            void postorder(node*);
            
    };
    int main()
    {
        BTree n;
        int ch,no,fi;
        cout << "Enter nodes and then press 'Enter': ";
        cin >> no;
        n.insert(no);
		cout<<" Enter a node to find"<<endl;
		cin>>fi;
		n.find(fi);
            
            choice:
            
            cout << "Enter your choice: Press 1 for In-Order: 2 for Pre-Order: 3 for Post-Order";
            cin >> ch;
			switch(ch)
           {
               case '1': 
                   cout<<" In-Order Traversal "<<endl;
					n.displayinorder();
                   break;
               case '2': 
                   cout<<" Pre-Order Traversal "<<endl;
                   n.displaypreorder();
                   break;
               case '3': 
                   cout<<" Post-Order Traversal "<<endl;
                   n.displaypostorder();
                   break;
               default:
                   cout << "Invalid entry. Try Again";
                   goto choice;
                   break;                
           }
        system("pause>null");
        return 0;
    }
    void BTree::insert(int d)
    {
        node* t = new node;
        node* parent;
        t->data = d;
        t->left = NULL;
        t->right = NULL;
        parent = NULL;
        if(isEmpty()) root = t;
        else
        {
            
            node* tee;
            tee = root;
            
            while(tee)
            {
                parent = tee;
                if(t->data > tee->data) tee = tee->right;
                else tee = tee->left;
            }
            if(t->data < parent->data)
               parent->left = t;
            else
               parent->right = t;
        }
    }


	bool BTree::find(int value)
{
    node *temp = root;

    while (temp != NULL)
    {
        if (temp->data == value)
            break;

        if (value > temp->data)
            temp = temp->right;
        else                  
        if (value < temp->data)
            temp = temp->left;
    }

    if (temp == NULL)
        return false;

    if (temp->data == value)
        return true;

    return false;
}
    void BTree::displayinorder()
    {
      inorder(root);
    }
    void BTree::inorder(node* p)
    {
        if(p != NULL)
        {
            if(p->left) inorder(p->left);
            cout<<" "<<p->data<<" ";
            if(p->right) inorder(p->right);
        }
        else return;
    }
    void BTree::displaypreorder()
    {
        preorder(root);
    }
    void BTree::preorder(node* p)
    {
        if(p != NULL)
        {
            cout<<" "<<p->data<<" ";
            if(p->left) preorder(p->left);
            if(p->right) preorder(p->right);
        }
        else return;
    }
    void BTree::displaypostorder()
    {
        postorder(root);
    }
    void BTree::postorder(node* p)
    {
        if(p != NULL)
        {
            if(p->left) postorder(p->left);
            if(p->right) postorder(p->right);
            cout<<" "<<p->data<<" ";
        }
        else return;
    }
dhayden (5795)
Your binary tree code looks okay but you're only inputting a single number. Try changing the insert and find code in main so they accept multiple values:
1
2
3
4
5
6
7
8
9
10
11
12
 
while (true) {
	cout << "Enter a value to insert, or -1 to quit: ";
	cin >> no;
	if (no == -1) break;
	n.insert(no);
}
while (true) {
	cout<<" Enter a value to find, or -1 to quit: "<<endl;
	cin>>fi;
	if (fi == -1) break;
	cout << "find() returned " << n.find(fi) << ends;
}

Topic archived. No new replies allowed.