Delphi 二叉排序树
时间: 2024-02-10 15:09:18 浏览: 44
Delphi是一种编程语言,可以用来实现二叉排序树。二叉排序树(Binary Search Tree,简称BST)是一种特殊的二叉树,它满足以下性质:
1. 左子树上的所有结点的值都小于根结点的值。
2. 右子树上的所有结点的值都大于根结点的值。
3. 左右子树也分别为二叉排序树。
在Delphi中,可以通过定义一个二叉排序树的结点类来实现二叉排序树的操作。每个结点包含一个值和两个指针,分别指向左子树和右子树。
以下是一个示例代码,演示了如何在Delphi中实现二叉排序树的插入、查找和删除操作:
```delphi
type
TNode = class
public
Value: Integer;
Left: TNode;
Right: TNode;
constructor Create(AValue: Integer);
end;
constructor TNode.Create(AValue: Integer);
begin
Value := AValue;
Left := nil;
Right := nil;
end;
type
TBinarySearchTree = class
private
Root: TNode;
function InsertNode(Node: TNode; Value: Integer): TNode;
function FindNode(Node: TNode; Value: Integer): TNode;
function FindMinNode(Node: TNode): TNode;
function DeleteNode(Node: TNode; Value: Integer): TNode;
public
procedure Insert(Value: Integer);
function Find(Value: Integer): Boolean;
procedure Delete(Value: Integer);
end;
function TBinarySearchTree.InsertNode(Node: TNode; Value: Integer): TNode;
begin
if Node = nil then
Result := TNode.Create(Value)
else if Value < Node.Value then
Node.Left := InsertNode(Node.Left, Value)
else if Value > Node.Value then
Node.Right := InsertNode(Node.Right, Value)
else
Result := Node;
end;
procedure TBinarySearchTree.Insert(Value: Integer);
begin
Root := InsertNode(Root, Value);
end;
function TBinarySearchTree.FindNode(Node: TNode; Value: Integer): TNode;
begin
if Node = nil then
Result := nil
else if Value < Node.Value then
Result := FindNode(Node.Left, Value)
else if Value > Node.Value then
Result := FindNode(Node.Right, Value)
else
Result := Node;
end;
function TBinarySearchTree.Find(Value: Integer): Boolean;
begin
Result := FindNode(Root, Value) <> nil;
end;
function TBinarySearchTree.FindMinNode(Node: TNode): TNode;
begin
if Node = nil then
Result := nil
else if Node.Left = nil then
Result := Node
else
Result := FindMinNode(Node.Left);
end;
function TBinarySearchTree.DeleteNode(Node: TNode; Value: Integer): TNode;
var
TempNode: TNode;
begin
if Node = nil then
Result := nil
else if Value < Node.Value then
Node.Left := DeleteNode(Node.Left, Value)
else if Value > Node.Value then
Node.Right := DeleteNode(Node.Right, Value)
else
begin
if (Node.Left = nil) and (Node.Right = nil) then
begin
Node.Free;
Result := nil;
end
else if Node.Left = nil then
begin
TempNode := Node;
Node := Node.Right;
TempNode.Free;
Result := Node;
end
else if Node.Right = nil then
begin
TempNode := Node;
Node := Node.Left;
TempNode.Free;
Result := Node;
end
else
begin
TempNode := FindMinNode(Node.Right);
Node.Value := TempNode.Value;
Node.Right := DeleteNode(Node.Right, TempNode.Value);
Result := Node;
end;
end;
end;
procedure TBinarySearchTree.Delete(Value: Integer);
begin
Root := DeleteNode(Root, Value);
end;
```
使用示例:
```delphi
var
BST: TBinarySearchTree;
begin
BST := TBinarySearchTree.Create;
// 插入结点
BST.Insert(5);
BST.Insert(3);
BST.Insert(7);
BST.Insert(2);
BST.Insert(4);
BST.Insert(6);
BST.Insert(8);
// 查找结点
if BST.Find(4) then
Writeln('Node found')
else
Writeln('Node not found');
// 删除结点
BST.Delete(4);
// 再次查找结点
if BST.Find(4) then
Writeln('Node found')
else
Writeln('Node not found');
BST.Free;
end;
```
这段代码演示了如何在Delphi中实现二叉排序树的插入、查找和删除操作。你可以根据需要修改代码来适应具体的场景。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)