Сумма Бинарного дерева без рекурсии

Question

Подскажите пожалуйста. Есть задачи поиск и вставка элемента в бинарное дерево, с этим вроде справился. Код:

function SearchTree (var p:TreeNodePtr; num:integer):TreeNodePos;
var tmp:TreeNodePos;
begin
 tmp:=p;
 while tmp^ <> nil do 
 begin
     if tmp^^.data < num then
         tmp:=@tmp^^.right
     else
         tmp:=@tmp^^.left;
 end;
 if (tmp^ = nil) or (tmp^^.data = num ) then
     SearchTree:=tmp; 
end;

function AddToTree(var p:TreeNodePtr;num : integer):boolean;
var pos:TreeNodePos;
begin
 pos:= SearchTree(p,num);
 if pos^ = nil then 
 begin
     new(pos^);
     pos^^.data:=num;
     pos^^.right:=nil;
     pos^^.left:=nil;
     AddToTree:=true;
 end
 else
     AddToTree:=false;
end;

Ума не приложу как найти сумму дерева без использования рекурсии, буду рад если кто-то поможет решить. Спасибо!

function SearchTree (var p:TreeNodePtr; num:integer):TreeNodePos;
var tmp:TreeNodePtr;
begin
    tmp:=@p;
    if tmp^.data = num then
        SearchTree:=@tmp; 
    while tmp <> nil do 
    begin
        if tmp^.data < num then
            tmp:=tmp^.right
        else
            tmp:=tmp^.left;
    end;
    if tmp = nil then
        SearchTree:=@tmp;
end;

new

function AddToTree(var p:TreeNodePtr;num : integer):boolean;
var pos:TreeNodePtr;
begin
    pos:= SearchTree(p,num);
    if pos = nil then 
    begin
        new(pos);
        pos^.data:=num;
        pos^.right:=nil;
        pos^.left:=nil;
        AddToTree:=true;
    end
    else
        AddToTree:=false;
end;

Answer 1

Во-первых, уберите лишний указательный уровень - ни к чему эти @p, tmp^ и tmp^^

Во-вторых, в SearchTree на равенство значений нужно проверять до того, как пойдёшь направо или налево

А сумму без рекурсии можно получить, используя обход с помощью стека или очереди. Заведите массив узлов, в первый элемент положите корень. Поддерживайте индекс вершины стека, на каждом шаге снимая элемент и вставляя его деток (если есть)

 Stack[0] := Root;
 StackIdx := 0;
 while StackIdx >= 0 do begin
     Node := Stack[StackIdx];
     Dec(StackIdx);
     Summ := Summ + Node.Value;
     if Node.Left <> Nil then
        Inc(StackIdx);
        Stack[StackIdx] := Node.Left;
     if Node.Rigth <> Nil then
        Inc(StackIdx);
        Stack[StackIdx] := Node.Right;
 end;

Вот поиск

function SearchTree (var p:TreeNodePtr; num:integer):TreeNodePtr;
var tmp:TreeNodePtr;
begin
    tmp:=p;
    while (tmp <> nil) and (tmp^.data <> num) do
        if tmp^.data < num then
            tmp:=tmp^.right
        else
            tmp:=tmp^.left;
    Result := tmp; //SearchTree, если в FP вдруг нету Result
end;

БЛОГ НА HUSL

Сумма Бинарного дерева без рекурсии

Ответы (1 шт):