"Eric Sosman" <esosman@[EMAIL PROTECTED]
> wrote in message
news:IdSdne1qWJRzbr_VnZ2dnUVZ_oCvnZ2d@[EMAIL PROTECTED]
> Keith Thompson wrote:
>> Thad Smith <ThadSmith@[EMAIL PROTECTED]
> writes:
>>> Eric Sosman wrote:
>>>> sophia wrote:
>>>>> How good is this function which is used to find the no: of nodes
>>>>> in each level of the binary tree. ?
>>
>> [snip]
>>
>>>> 4) You might gain still more speed by using recursion only
>>>> when you encounter a node where both the left and right branches
>>>> are non-NULL. This also offers some defense against degeneracy.
>>> I'd say that 4) offers excellent defense against (call level overflow)
>>> degeneracy since the maximum recursion level is less than log2(N)+1.
>>
>> Does it? It limits recursion if the tree is a linear vine, and can
>> reduce it substantially in some other cases, but what if each node on
>> the leftmost vine has a single node as its right child? Then the
>> depth of recursion could be on the order of 1/2 the number of nodes.
>> [...]
>
> That's why I only claimed "some" defense against degeneracy.
> Even in the tree you describe one might get lucky: if when
> faced with a two-way branch the function always recursed to the
> right and looped to the left, there'd be no trouble. Of course,
> then a tree that leaned the other direction would be bad. So
> would a zig-zag arrangement where the "trunk" went left and right
> alternately while the "twigs" branched right and left.
I personally find that using recursion to traverse trees can be somewhat
dangerous because certain trees can potentially blow the stack. To get
around recursion, I tend to use an auxiliary node, and use that as a link
into a traversal queue. Something like:
<pseudo-code>
_______________________________________________________________
struct tnode {
struct tnode* left;
struct tnode* right;
struct tnode* next;
};
/* Tree Iteration Sup****t */
struct tnode_iterq {
struct tnode* head;
struct tnode* tail;
};
void tnode_iterq_push(
tnode_iterq* const _this,
tnode* const node
) {
if (node) {
node->next = NULL;
if (! _this->head) {
_this->head = node;
} else {
_this->tail->next = node;
}
_this->tail = node;
}
}
tnode* tnode_iterq_pop(
tnode_iterq* const _this
) {
tnode* const node = _this->head;
if (node) {
if (! (_this->head = node->next)) {
_this->tail = NULL;
}
}
return node;
}
/* Tree Iterator */
void* tnode_iterate(
tnode* const _this,
void (*fp_iterate) (tnode*, void*),
void* const state
) {
unsigned count = 0;
tnode* node = _this;
tnode_iterq iterq = { NULL };
do {
tnode_iterq_push(&iterq, node->left);
tnode_iterq_push(&iterq, node->right);
fp_iterate(node, state);
++count;
} while (! (node = tnode_iterq_pop(&iterq)));
return state;
}
_______________________________________________________________
Now there is no chance of blowing the stack because all recursion is
eluded...
|
