Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

binary tree function

mondenkind11mondenkind11 Posts: 22Member
hi
i have a recursive function "iselement" given which determines in a binary tree the number of nodes in which the info- component is larger or equal a
passed value.
In detail it looks as follows.


[code]
type
tnat = 0..maxint;
trefbintree = ^tbintree;

tbintree = record
info : integer;
left,
right : trefbintree
end;

function iselement(inrefroot : trefbintree; invalue : integer) : tnat;

var
number : tnat;

begin
if inrefroot = nil then
number := 0
else
begin
number := iselement(inrefroot^.right, invalue)
+ iselement(inrefroot^.left, invalue);

if inrefroot^.info >= invalue then
number := number + 1
end;
iselement := number
end;
[/code]

---------------------
Could anybody explain the steps in the recursion and why this code actually works?
Why cant I put the if- part "if inrefroot^.info >= invalue"
before the instruction
"number := iselement(...)+ iselement(...);"?
I would appreciate any help. Thank you

Comments

  • bpajkbpajk Posts: 156Member
    : hi
    : i have a recursive function "iselement" given which determines in a binary tree the number of nodes in which the info- component is larger or equal a
    : passed value.
    : In detail it looks as follows.
    :
    :
    : [code]
    : type
    : tnat = 0..maxint;
    : trefbintree = ^tbintree;
    :
    : tbintree = record
    : info : integer;
    : left,
    : right : trefbintree
    : end;
    :
    : function iselement(inrefroot : trefbintree; invalue : integer) : tnat;
    :
    : var
    : number : tnat;
    :
    : begin
    : if inrefroot = nil then
    : number := 0
    : else
    : begin
    : number := iselement(inrefroot^.right, invalue)
    : + iselement(inrefroot^.left, invalue);
    :
    : if inrefroot^.info >= invalue then
    : number := number + 1
    : end;
    : iselement := number
    : end;
    : [/code]
    :
    : ---------------------
    : Could anybody explain the steps in the recursion and why this code actually works?
    : Why cant I put the if- part "if inrefroot^.info >= invalue"
    : before the instruction
    : "number := iselement(...)+ iselement(...);"?
    : I would appreciate any help. Thank you
    :
    The function calls itself by the
    [CODE]
    number := iselement(inrefroot^.right, invalue)
    + iselement(inrefroot^.left, invalue);
    [/CODE]
    statement. This repeats itself until the function reaches the top of the tree [CODE]if inrefroot = nil then number := 0[/CODE] where the variable number is given it's initial value 0. In the first stage the funcion only goes by the right side,
    [CODE]
    number := iselement(inrefroot^.[B]right[/B], invalue)
    + iselement(inrefroot^.left, invalue);
    [/CODE]
    but when it goes back to the bottom, it also calculates the left side.
    [CODE]
    number := iselement(inrefroot^.right, invalue)
    + iselement(inrefroot^.[B]left[/B], invalue);
    [/CODE]
    This is because the [CODE]iselement(inrefroot^.[B]right[/B], invalue)[/CODE] statement is executed before the [CODE]iselement(inrefroot^.[B]left[/B], invalue)[/CODE] statement. As it goes back to the bottom function checks if the info element is bigger then invalue and increases the number variable, which is then passed on from function to function on diferent levels of the tree. The total number of elements in the tree is the sum of both the left and the right branches of the tree.
  • mondenkind11mondenkind11 Posts: 22Member

    Thank you very much for your answer. I am very grateful.

Sign In or Register to comment.