printing nodes with the same degree

closed account (ShqoT05o)

get nodes(int n) - This function returns all nodes in form of a string, whose degree (number of children nodes) is n. For example, T.get nodes(0) returns ”abeghi” for our example, as those nodes are leaf nodes and their degree (number of outgoing edges) is zero. T.get nodes(1) returns ”bf” as those have only one outgoing edge. T.get nodes(2) returns ”a”. T.get nodes(3) returns ”eh”.

I am really struggling trying to figure out this function. If you could please 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
#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct Node {
    char data;
    Node *left;
    Node *right;
    Node *mid;
    
};

class BSTree {
private:
    Node *root;
    void insert_h(char, Node *);
    void traverse_h(Node *);
    
    
public:
    void insert(char);
    void construct(vector<char>);
    void traverse();
    int get_nodes(int); *** must only take int
    
    BSTree(){
        root=NULL;
    }
    
};

void BSTree::insert_h(char letter, Node*leaf){
    if (letter < leaf->data){
        if(leaf->left != NULL)
            insert_h(letter,leaf->left);
        else
        {
            leaf->left = new Node;
            leaf->left->data = letter;
            leaf->left->left = NULL;
            leaf->left->mid = NULL;
            leaf->left->right = NULL;
        }
    }
    else if(letter == leaf->data)
        {
            if(leaf->mid !=NULL)
                insert_h(letter,leaf->center);
            else{
                leaf->mid = new Node;
                leaf->mid->data = letter;
                leaf->mid->left = NULL;
                leaf->mid->mid = NULL;
                leaf->mid->right = NULL;
                
            }
 }
    else if(letter > leaf->data)
        {
            if(leaf->right !=NULL)
                insert_h(letter,leaf->right);
            else{
                leaf->right = new Node;
                leaf->right->data = letter;
                leaf->right->left = NULL;
                leaf->right->mid = NULL;
                leaf->right->right = NULL;
                
            }
 }
    
}
void BSTree::insert(char letter){
    if(root != NULL)
        insert_h(letter, root);
    else {
        root = new Node;
        root->data = letter;
        root->left = NULL;
        root->mid = NULL;
        root->right = NULL;
    }
}
void BSTree::construct(const vector<char> V){
    for(auto i=V.begin();i !=V.end();i++)
    insert(*i);
    
    
}
    
void BSTree::traverse_h(Node *root){
      if(root!= NULL){
          traverse_h(root->left);
          traverse_h(root->mid);
          cout<<root->data<<endl;
          traverse_h(root->right);
}

void BSTree::traverse(){
    traverse_h(root);
} 
int main(){
    
    vector<char> V = {'e','a','f','h','b','g','b','a','h','i','e'};
    BSTree T;
    T.construct(V);
    T.traverse();
    cout << T.get_nodes(0) <<endl;
   
    
  
return 0;
}


Last edited on
Well the first thing to write would be a private function like this, to tell you what degree any given node in your tree is.
 
int BSTree::degree(Node *node);


You can then use that function in your get_nodes function to determine whether to add the char at that node, based on it's degree.

The rest is the normal tree traversal which you already have an example of.

> int get_nodes(int); *** must only take int
Your description does say however that it returns a string, not an int.
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
#include <iostream>
#include <string>
using namespace std;

struct Node {
    char data;
    Node *left  = nullptr;
    Node *right = nullptr;
    Node *mid   = nullptr;
    
    Node( char c ) : data( c ){}
};


class BSTree
{
    Node *root = nullptr;
    
    void insert( char, Node * & );
    void traverse( Node * & );
    string get_nodes( int, Node * & );
    
public:
    BSTree(){}
    BSTree( const string & );
    void insert( char letter ){ insert( letter, root ); }
    void traverse(){ traverse( root ); } 
    string get_nodes( int n ){ return get_nodes( n, root ); }
};


BSTree::BSTree( const string &S )
{
    for( auto c : S ) insert( c );
}


void BSTree::insert( char letter, Node * &leaf )
{
   if ( !leaf ) leaf = new Node( letter );
   else if ( letter < leaf->data ) insert( letter, leaf->left  );
   else if ( letter > leaf->data ) insert( letter, leaf->right );
   else                            insert( letter, leaf->mid   );
}


void BSTree::traverse( Node * &leaf )
{
   if ( leaf )
   {
      traverse( leaf->left );
      traverse( leaf->mid  );
      cout << leaf->data << '\n';
      traverse( leaf->right);
   }
}


string BSTree::get_nodes( int n, Node * &leaf )
{
   string result;
   if ( leaf )
   {
      result = get_nodes( n, leaf->left ) + get_nodes( n, leaf->mid );
      if ( ( leaf->left != nullptr ) + ( leaf->mid != nullptr ) + ( leaf->right != nullptr ) == n ) result += leaf->data;
      result += get_nodes( n, leaf->right );
   }
   return result;
}


int main()
{
    BSTree T( "eafhbgbahie" );
    T.traverse();
    for ( int n = 0; n <= 3; n++ ) cout << n << ": " << T.get_nodes(n) << '\n';
}
Last edited on
closed account (ShqoT05o)
I need the letters to be separated like I have on top
Based upon lastchance's code:

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
#include <iostream>
#include <string>
#include <initializer_list>

struct Node {
	char data {};
	Node* left {};
	Node* right {};
	Node* mid {};

	Node(char c) : data(c) {}
};

class BSTree
{
	Node* root {};

	void insert(char, Node*&);
	void traverse(const Node*) const;
	std::string get_nodes(int, const Node*) const;
	void remove(const Node*);

public:
	BSTree() {}
	~BSTree() { remove(root); }
	BSTree(const std::string&);
	BSTree(const std::initializer_list<char>& chars);
	void insert(char letter) { insert(letter, root); }
	void traverse() const { traverse(root); }
	std::string get_nodes(int n) const { return get_nodes(n, root); }
};


BSTree::BSTree(const std::initializer_list<char>& chars)
{
	for (const auto c : chars)
		insert(c);
}

BSTree::BSTree(const std::string& S)
{
	for (const auto c : S)
		insert(c);
}

void BSTree::remove(const Node* leaf)
{
	if (leaf) {
		remove(leaf->left);
		remove(leaf->mid);
		remove(leaf->right);

		delete leaf;
	}
}

void BSTree::insert(char letter, Node*& leaf)
{
	if (!leaf)
		leaf = new Node(letter);
	else if (letter < leaf->data)
		insert(letter, leaf->left);
	else if (letter > leaf->data)
		insert(letter, leaf->right);
	else
		insert(letter, leaf->mid);
}

void BSTree::traverse(const Node* leaf) const
{
	if (leaf) {
		traverse(leaf->left);
		traverse(leaf->mid);
		std::cout << leaf->data;
		traverse(leaf->right);
	}
}

std::string BSTree::get_nodes(int n, const Node* leaf) const
{
	std::string result;

	if (leaf) {
		result = get_nodes(n, leaf->left) + get_nodes(n, leaf->mid);

		if ((leaf->left != nullptr) + (leaf->mid != nullptr) + (leaf->right != nullptr) == n)
			result += leaf->data;

		result += get_nodes(n, leaf->right);
	}

	return result;
}

int main()
{
	//BSTree T("eafhbgbahie");
	BSTree T {'e','a','f','h','b','g','b','a','h','i','e'};

	T.traverse();
        std::cout << '\n';

	for (int n = 0; n <= 3; ++n)
		std::cout << n << ": " << T.get_nodes(n) << '\n';
}

Last edited on
closed account (ShqoT05o)
I need to be able to enter each interger instead of x
If you can't alter the above code to do that, then you seriously need to revise hard what you're been taught about C++. Instead of a for loop, just have a cout/cin to ask/get the required value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
	//BSTree T("eafhbgbahie");
	BSTree T {'e','a','f','h','b','g','b','a','h','i','e'};

	T.traverse();
        std::cout << '\n';

	//for (int n = 0; n <= 3; ++n)

	int n {};

	do {
		std::cout << "\nEnter n (0 - 3): ";
		if (!(std::cin >> n)) {
			std::cin.clear();
			std::cin.ignore(1000, '\n');
			n = -1;
		}
	} while ((n < 0 || n > 3) && (std::cout << "Invalid (0 - 3)\n"));

	std::cout << n << ": " << T.get_nodes(n) << '\n';
}

Last edited on
Topic archived. No new replies allowed.