1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Program that counts all the vertices in a given tree

  1. Jun 29, 2013 #1
    1. The problem statement, all variables and given/known data

    "Write a program that counts all the vertices in a given tree."

    Any language can be used. (I've been using Perl mostly but could do C too. C++ would be ok too, if it was significantly easier.)

    2. Relevant equations

    I've been trying to find this. I read if a tree has n levels, the number of vertices is 2^{n-1}. And for n edges, the vertices are (n-1). Maybe that will help.

    3. The attempt at a solution

    I'm not making much progress because I don't even know what the input is supposed to look like. Also, this seems like the kind of thing that there's a formula for.
    -What does the input look like? (how is the tree entered into the program?) I've seen the graphical version. But how would that tree be typed in?

    I'm a grad student in electrical engineering but software is not my area of specialization. I didn't take the algorithms class. The problem would probably be simple to anyone who had taken the class. If you know a good reference book or website, I'd appreciate that too. Googling hasn't helped much.
  2. jcsd
  3. Jun 30, 2013 #2
    This process is usually called a traversal of the tree, visiting each node, using the self-similar nature of trees - each branch is treated as a tree. The routine should accept a pointer to the root node which will have pointers to other parts of the tree. See Binary Tree (Wiki). A typical traversal can be some variation of:
    - process left pointer if not null
    - act on current node
    - process right pointer if not null
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted