I am trying to determine if an n-ary tree is balanced or not, I have

been stuck trying several approaches and am getting nowhere. My new

thought is that i will have to step through each node of the tree, and

compare the lengths of the roots of the children, making sure there is

not a difference greater than one in the values for all of the

children. Am i thinking in the right direction, or is there a simpler

solution?

thanks,

kim

--

comp.lang.c.moderated - moderation address: XXXX@XXXXX.COM -- you must

have an appropriate newsgroups line in your header for your mail to be seen,

or the newsgroup name in square brackets in the subject line. Sorry.

Yes, a depth first traversal that sounds like the easiest way to me.

All nodes at depth 'd' must have no children and all nodes at depth

d-2 (or less) must have n children,

Traverse the tree and report the depth of the deepest node and the

depth of the shallowest node not having n children,

If the difference is more than 1 the tree is unbalanced,

this is easily written as a recursive function but may perform better

(by some small, fixed, multiple) as a stack-based iterative function.

--

comp.lang.c.moderated - moderation address: XXXX@XXXXX.COM -- you must

have an appropriate newsgroups line in your header for your mail to be seen,

or the newsgroup name in square brackets in the subject line. Sorry.

cgirl < XXXX@XXXXX.COM > writes:

Your question is off-topic for this newsgroup, but yes, this is the

definition of a balanced tree, and no, there is no other way to do it.

What you call "the lengths of the roots of the children" is usually

called the height of the node.

You should get these: http://www.yqcomputer.com/

DES

--

Dag-Erling Smrgrav - XXXX@XXXXX.COM

--

comp.lang.c.moderated - moderation address: XXXX@XXXXX.COM -- you must

have an appropriate newsgroups line in your header for your mail to be seen,

or the newsgroup name in square brackets in the subject line. Sorry.

Your question is off-topic for this newsgroup, but yes, this is the

definition of a balanced tree, and no, there is no other way to do it.

What you call "the lengths of the roots of the children" is usually

called the height of the node.

You should get these: http://www.yqcomputer.com/

DES

--

Dag-Erling Smrgrav - XXXX@XXXXX.COM

--

comp.lang.c.moderated - moderation address: XXXX@XXXXX.COM -- you must

have an appropriate newsgroups line in your header for your mail to be seen,

or the newsgroup name in square brackets in the subject line. Sorry.

One more soln.

N ary tree

L=get no of nodes in tree.

H=get max height level of tree.

if(floor(log baseN(L))==H-1) true

else false

This is for height balanced tree

--

comp.lang.c.moderated - moderation address: XXXX@XXXXX.COM -- you must

have an appropriate newsgroups line in your header for your mail to be seen,

or the newsgroup name in square brackets in the subject line. Sorry.

N ary tree

L=get no of nodes in tree.

H=get max height level of tree.

if(floor(log baseN(L))==H-1) true

else false

This is for height balanced tree

--

comp.lang.c.moderated - moderation address: XXXX@XXXXX.COM -- you must

have an appropriate newsgroups line in your header for your mail to be seen,

or the newsgroup name in square brackets in the subject line. Sorry.

1. Determining if an n-ary tree is balanced or not.

2. Trying to determing if n-ary tree is balanced.

3. Implementing vector (resizable array) with n-ary tree

4. Iterating through an n-ary tree

6. n-ary tree

8. Type trouble ( Help with n-ary Trees)

10. new/delete vs. vector implementing n-ary tree

11. n-ary tree

12. n-ary tree implementation using MATLAB.

4 post • Page:**1** of **1**