Задание. С помощью указателей построить бинарное дерево поиска. Обойти его в прямом, симметричном и обратном порядке. Реализовать процедуры поиска, вставки и удаления элементов в бинарное дерево поиска.
на языке Delphi. помогите пожалуйста
Ответы
type
// Define a node type with pointers to the left and right children
TNode = record
Value: Integer;
Left, Right: ^TNode;
end;
var
// Declare a root node
Root: ^TNode;
// Initialize the tree
procedure InitializeTree;
begin
New(Root);
Root^.Value := 0;
Root^.Left := nil;
Root^.Right := nil;
end;
// Search for a value in the tree
function Search(Node: ^TNode; Value: Integer): ^TNode;
begin
if Node = nil then
Result := nil
else if Node^.Value = Value then
Result := Node
else if Node^.Value > Value then
Result := Search(Node^.Left, Value)
else
Result := Search(Node^.Right, Value);
end;
// Insert a value into the tree
procedure Insert(var Node: ^TNode; Value: Integer);
begin
if Node = nil then
begin
New(Node);
Node^.Value := Value;
Node^.Left := nil;
Node^.Right := nil;
end
else if Node^.Value > Value then
Insert(Node^.Left, Value)
else
Insert(Node^.Right, Value);
end;
// Remove a value from the tree
procedure Remove(var Node: ^TNode; Value: Integer);
var
Temp: ^TNode;
begin
if Node <> nil then
begin
if Node^.Value > Value then
Remove(Node^.Left, Value)
else if Node^.Value < Value then
Remove(Node^.Right, Value)
else
begin
if (Node^.Left = nil) and (Node^.Right = nil) then
begin
Dispose(Node);
Node := nil;
end
else if (Node^.Left <> nil) and (Node^.Right = nil) then
begin
Temp := Node;
Node := Node^.Left;
Dispose(Temp);
end
else if (Node^.Left = nil) and (Node^.Right <> nil) then
begin
Temp := Node;
Node := Node^.Right;
Dispose(Temp);
end
else
begin
Temp := Node^.Right;
while Temp^.Left <> nil do
Temp := Temp^.Left;
Node^.Value := Temp^.Value;
Remove(Node^.Right, Temp^.Value);
end;
end;
end;
end;
// Traverse the tree in preorder
procedure Preorder(Node: ^TNode);
begin
if Node <> nil then
begin
WriteLn(Node^.Value);
Preorder(Node^.Left);
Preorder(Node^.Right);
end;
end;
// Traverse the tree in inorder
procedure Inorder(Node: ^TNode);
begin
if Node <> nil then
begin
Inorder(Node^.Left);
WriteLn(Node^.Value);
Inorder(Node^.Right);
end;
end;
// Traverse the tree in postorder
procedure Postorder(Node: ^TNode);
begin
if Node <> nil then
begin
Postorder(Node^.Left);
Postorder(Node^.Right);
WriteLn(Node^.Value);
end;
end;
begin
InitializeTree;
Insert(Root, 5);
Insert(Root, 3);
Insert(Root, 7);
Insert(Root, 2);
Insert(Root, 4);
Insert(Root, 6);
Insert(Root, 8);
WriteLn('Preorder:');
Preorder(Root);
WriteLn;
WriteLn('Inorder:');
Inorder(Root);
WriteLn;
WriteLn('Postorder:');
Postorder(Root);
WriteLn;
Remove(Root, 5);
Remove(Root, 3);
Remove(Root, 7);
WriteLn('Preorder:');
Preorder(Root);
WriteLn;
end.
// Test the search function
function TestSearch(Node: ^TNode; Value: Integer): Boolean;
begin
Result := Search(Node, Value) <> nil;
end;
// Test the Search
function TestSearch(Node: ^TNode; Value: Integer): Boolean;
begin
Result := Search(Node, Value) <> nil;
end;
// Test the insert and remove functions
procedure TestInsertRemove(Node: ^TNode);
begin
Insert(Node, 5);
Insert(Node, 3);
Insert(Node, 7);
Insert(Node, 2);
Insert(Node, 4);
Insert(Node, 6);
Insert(Node, 8);
WriteLn('Search for 5: ', TestSearch(Node, 5));
WriteLn('Search for 3: ', TestSearch(Node, 3));
WriteLn('Search for 7: ', TestSearch(Node, 7));
WriteLn('Search for 1: ', TestSearch(Node, 1));
WriteLn('Search for 9: ', TestSearch(Node, 9));
Remove(Node, 5);
Remove(Node, 3);
Remove(Node, 7);
Remove(Node, 2);
Remove(Node, 4);
Remove(Node, 6);
Remove(Node, 8);
WriteLn('Search for 5: ', TestSearch(Node, 5));
WriteLn('Search for 3: ', TestSearch(Node, 3));
WriteLn('Search for 7: ', TestSearch(Node, 7));
WriteLn('Search for 1: ', TestSearch(Node, 1));
WriteLn('Search for 9: ', TestSearch(Node, 9));
begin
InitializeTree;
TestInsertRemove(Root);
end.