Solved

count internal nodes in a tree

Posted on 2004-04-07
11
804 Views
Last Modified: 2008-03-10
write a program in 'C' language to count the number of internal nodes  of a tree.
0
Comment
Question by:jessu2607
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
  • 2
  • +2
11 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 10772791
sorry we cannot do your homework for you

make some efforts ... post your code and if you are stuck on something specific, we will help
0
 
LVL 4

Expert Comment

by:skypalae
ID: 10772860
Is it binary tree? If yes, then number of internal nodes is allways one less then number of leaves.

Cheers! S.
0
 
LVL 9

Accepted Solution

by:
ankuratvb earned 125 total points
ID: 10773207
The simplest solution would be a recursive function.
jessu2607,all this requires is one recursive fn. to be written.

Try it urself.As sunny said,if you are stuck,we'll be glad to help.
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 5

Expert Comment

by:twobitadder
ID: 10779108
>>Is it binary tree? If yes, then number of internal nodes is allways one less then number of leaves.

Only if it is a complete and balanced tree.
0
 
LVL 4

Expert Comment

by:skypalae
ID: 10781004
twobitadder,

I don't get what you mean by complete, but definitely it doesn't need to be balanced tree

/\
 /\
  /\
   /\
    /\

is not balanced at all and it still has 5 internals and 6 leaves

and if complete means that there is not

/\
  \
  /\

that tree is (almost) for nothing and you can allways get complete by deleting the uncomplete internal

S.
0
 
LVL 5

Expert Comment

by:twobitadder
ID: 10783089
>/\
> /\
>  /\
>   /\
>    /\
>
>is not balanced at all and it still has 5 internals and 6 leaves

    /\
  /\ /\
/

has 4 internals and 4 leaves

whilst
   /\
  /\/\
 /\
has 4 internals and 5 leaves
0
 
LVL 4

Expert Comment

by:skypalae
ID: 10783185
>     /\
>   /\ /\
> /

is incomplete (as far as i understand your term 'completeness'). and it is balanced (since there are no 2 paths from root to leaf that would differ by 2). i still insist on that (complete) binary tree has allways one less internals than leaves. and on that incomplete trees are for nothing (but studying purposes).

S.
0
 
LVL 9

Expert Comment

by:ankuratvb
ID: 10783255
Full Binary Tree Theorem

Theorem:  The number of leaves in a non-empty full binary  tree is one more than the number of internal nodes.  

Full binary tree:  each node either is a leaf or is an internal node with exactly two non-empty children

For proof,see:http://www.cz3.nus.edu.sg/~chenk/cz2102/notes5_1.htm

BTW, a complete binary tree is:

Complete binary tree:  If the height of the tree is d, then all levels except possibly level d are completely full.  The bottom level has all nodes to the left side.
0
 
LVL 4

Expert Comment

by:Fippy_Darkpaw
ID: 10801260
Here's an easy (not necessarily optimal) way:

- search every node in the tree
- if it has children then InternalNodeCount++
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.

630 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question