Help Doing Sequential Search For A 3 Branch Tree! - Topic

Member

Posts: 23,862

Joined: Aug 16 2006

Gold: 20.00

Nov 21 2012 05:36pm

So for my latest project I have a class which contains 3 pointers - one to a spouse, one to sibling(s) and one to kid(s)

I need a function to search through ALL OF THESE (they are not ordered) and return a pointer to the one which contains a certain string (their name)

I can not for the LIFE OF ME figure out a function to do this with because of the funky way the class is set up and what not.

Can anyone offer some suggestions??

carteblanche

Member

Posts: 32,925

Joined: Jul 23 2006

Gold: 3,804.50

Nov 21 2012 08:37pm

normal tree traversal. you can do depth first or breadth first.

breadth first:
step 1: is my current node a match? if yes, you're done.
step 2: queue all neighbors
step 3: pop from queue. if empty, no match
step 4: see step 1

This post was edited by carteblanche on Nov 21 2012 08:37pm

Eep

Member

Posts: 23,862

Joined: Aug 16 2006

Gold: 20.00

Nov 21 2012 10:09pm

I ended up doing something like this

Code

person *tree_search(string input, person *head)
{
person *p;
while (head != NULL)
{
p = head;
if (head->name == input)
{
return head;
}
head->access_spouse(head);
if (head->name == input)
{
return head;
}
ptr_link(head, p);
head->access_sibling(head);
while (head != NULL)
{
if (head->name == input)
{
return head;
}
head = head->sibling;
}
ptr_link(head, p);
head = head->kids;
}
return NULL;
}

Fawar

Member

Posts: 8,564

Joined: Jun 13 2006

Gold: 4.75

Nov 30 2012 04:41pm

Quote (Eep @ 21 Nov 2012 18:36)

Well get a recursive call where you send the child of the current node, but before calling the recursive check for equality with those you have acces at the very moment. Why do you get to have a 3 branch tree unordered? You should maybe consider AVL with Parent - RightChild, LeftChild, way simpler.

Go Back To Programming & Development Topic List