Jump to content
  • Advertisement
Sign in to follow this  
Julian Spillane

Question About Tree Counting...

This topic is 4741 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey all. I've been working on a commissioned project that involves finding the longest possible chain of dominos out of a hand, and choosing the best one (for someone's domino game AI). Now, after many trials and tribulations, I decided that the best way to do this would be to sort all of the data in a tree. i.e. Root: (0, 1) (1,2) (1,4)(1,6) (2,3) etc. Now, I've got it storing in the tree just fine, and I know my basic traversal algorithms, but for some reason...maybe it's the fact that it's 3:00 am, I can't figure out something for the life of me: How would I count the number of elements in a branch of the tree? Using the example above, the best chain would obviously be (0,1)-(1,2)-(2,3). But how would I go about counting that? I can't very well do it recursively, or I'd get the other guys. But if I don't do it recursively, I don't know how many levels exist in the tree. I considered a preorder traversal and then adding, but if a node has multiple children, it will count all of them. Do you guys have any suggestions? I hope I haven't been too ambiguous. Thanks a lot.

Share this post


Link to post
Share on other sites
Advertisement
Find the total number of nodes leading to each leaf node (or just for each node) by traversing the tree recusrivly. Store the length to that point in each node. Then just look for the leaf node that has the longest length by checking each node in the tree.

Go back up the tree from there and you have your chain.

Not necessaraly the fastest solution, but it will work.

Quote:
I can't very well do it recursively, or I'd get the other guys. But if I don't do it recursively, I don't know how many levels exist in the tree.

Perhaps it's because you're tired - this dosn't make sense [smile].

Share this post


Link to post
Share on other sites
Thanks, Andrew.

Man...I was tired. Your advice seems quite sound, and I'll get to work on it right away and hope that I'll be able to overcome this early morning delirium enough to do it without any hassle. :p

Thanks a lot.

Share this post


Link to post
Share on other sites
Actually, I do have a question:

How would I find the number of nodes leading to each leaf node recursively?
I mean, if I had my tree set up like the example below, if I used a preorder traversal I'd get 1 + 2+ 4 + 5, and 3+6 as two separate pathways.

(1)
(2)(3)
(4)(5) (6)

If I went postorder, I'd get 4+5+2+1+6+3.
And there's no point in even considering breadth and inorder traversals for this.

I'm still not sure how I'd go about counting specific pathways.

Sorry to be a bother.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!