[iamminn]

This is the structure of the binary tree I am given

typedef struct stringnode
{
string value;
stringnode * left;
stringnode * right;
}

I need to create a function that takes as arguments the external pointer to the root node and a "target" string.

The function will then return the number of times the "target" string appears in the tree.

Here is what i have so far. (I know it is basically nothing)

unsigned countstring(stringnode*treepointer,string target)
{
cout<<"What string would you like to search for"<<endl;
cin>>target;

if (treepointer == NULL)
cout<<"Tree is empty!";
else if
{
}

Where I need help is actually navigating through the tree and comparing the target string to the strings stored in the leaf nodes.

[azemyth]

traverse the tree, compare string, and count if string is equal.
for traversing you have 3 methods. preorder, inorder, postorder. for counting u need to pass integer in the function

p.s. you need to know what is recursion before playing with binary trees

This post has been edited by azemyth: 11 December 2012 - 06:11 AM

[baavgai]

That typedef does nothing.

I'd also use another struct: e.g.

struct Node {
	string value;
	Node *left, *right;
	Node(const string &s) : value(s), left(NULL), right(NULL) { }
};

struct Tree {
	Node *root;
	Tree() : root(NULL) { }
	bool isEmpty() const { return root==NULL; }
};

azemyth, on 11 December 2012 - 08:10 AM, said:

for counting u need to pass integer in the function

Why? unsigned countstring(Tree &, const string &); would work.

azemyth, on 11 December 2012 - 08:10 AM, said:

p.s. you need to know what is recursion before playing with binary trees

Incorrect. It does make life easier, but certainly isn't required. You should know how to traverse a tree without recursion, both for knowledge and because it's more efficient.

e.g.

unsigned countstring(Tree &t, const string &target) {
	unsigned count = 0;
	Node *node = t.root;
	while(node!=NULL) {
		count++;
		// ...
}

Note, in the above I'm counting the number of notes traversed to get to the target. This makes a lot more sense than counting instances; that should have a difference node structure.

Hope this helps.