2 Replies - 339 Views - Last Post: 11 December 2012 - 06:45 AM Rate Topic: -----

#1 iamminn  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 10-December 12

Binary tree w/ Node struct

Posted 11 December 2012 - 02:15 AM

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.

Is This A Good Question/Topic? 0
  • +

Replies To: Binary tree w/ Node struct

#2 azemyth  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 25
  • Joined: 12-December 11

Re: Binary tree w/ Node struct

Posted 11 December 2012 - 06:10 AM

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

Was This Post Helpful? 0
  • +
  • -

#3 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5882
  • View blog
  • Posts: 12,761
  • Joined: 16-October 07

Re: Binary tree w/ Node struct

Posted 11 December 2012 - 06:45 AM

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; }
};





View Postazemyth, 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.


View Postazemyth, 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.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1