Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- unit MainUnit;
- interface
- uses
- Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
- Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls, Vcl.ExtCtrls, Vcl.Menus, Clipbrd;
- type
- TMainForm = class(TForm)
- ValueEdit: TEdit;
- AddButton: TButton;
- ProcessingButton: TButton;
- DeleteButton: TButton;
- ExitButton: TButton;
- TreeImage: TImage;
- MainMenu: TMainMenu;
- FileMenuItem: TMenuItem;
- OpenMenuItem: TMenuItem;
- SaveMenuItem: TMenuItem;
- SaveAsMenuItem: TMenuItem;
- ManualMenuItem: TMenuItem;
- AboutDeveloperMenuItem: TMenuItem;
- OpenDialog: TOpenDialog;
- SaveDialog: TSaveDialog;
- CopyPastePopupMenu: TPopupMenu;
- CopyButton: TMenuItem;
- PasteButton: TMenuItem;
- CutButton: TMenuItem;
- ConditionLabel: TLabel;
- ScrollBox1: TScrollBox;
- procedure FormCloseQuery(Sender: TObject; var CanClose: Boolean);
- procedure ExitButtonClick(Sender: TObject);
- procedure ManualMenuItemClick(Sender: TObject);
- procedure AboutDeveloperMenuItemClick(Sender: TObject);
- procedure CopyButtonClick(Sender: TObject);
- procedure PasteButtonClick(Sender: TObject);
- procedure CutButtonClick(Sender: TObject);
- procedure CopyPastePopupMenuPopup(Sender: TObject);
- procedure ValueEditChange(Sender: TObject);
- procedure ValueEditKeyDown(Sender: TObject; var Key: Word;
- Shift: TShiftState);
- procedure ValueEditDblClick(Sender: TObject);
- procedure ValueEditKeyPress(Sender: TObject; var Key: Char);
- procedure FormCreate(Sender: TObject);
- procedure AddButtonClick(Sender: TObject);
- procedure DeleteButtonClick(Sender: TObject);
- procedure ProcessingButtonClick(Sender: TObject);
- private
- { Private declarations }
- public
- { Public declarations }
- end;
- var
- MainForm: TMainForm;
- implementation
- uses
- BinaryTreeUnit;
- const
- kBACKSPACE = #8;
- kINSERT = 45;
- MIN_VALUE = 1;
- MAX_VALUE = 9999;
- var
- TreeStart: TPointer;
- {$R *.dfm}
- procedure TMainForm.AboutDeveloperMenuItemClick(Sender: TObject);
- begin
- MessageBox(Handle, 'Разработчик: Наривончик Александр Михайлович, гр. 351004', 'О разработчике', MB_OK Or MB_ICONINFORMATION);
- end;
- procedure TMainForm.CopyButtonClick(Sender: TObject);
- begin
- ValueEdit.CopyToClipboard;
- end;
- procedure TMainForm.CopyPastePopupMenuPopup(Sender: TObject);
- var
- IValue: Integer;
- Buffer: String;
- IsCorrect: Boolean;
- begin
- Buffer := Clipboard.AsText;
- IsCorrect := TryStrToInt(Buffer, IValue);
- PasteButton.Enabled := IsCorrect;
- end;
- procedure TMainForm.CutButtonClick(Sender: TObject);
- begin
- ValueEdit.CutToClipboard;
- end;
- procedure TMainForm.PasteButtonClick(Sender: TObject);
- begin
- ValueEdit.PasteFromClipboard;
- end;
- procedure EditButtonEnabled();
- begin
- with MainForm do
- begin
- AddButton.Enabled := ValueEdit.Text <> '';
- DeleteButton.Enabled := ValueEdit.Text <> '';
- end;
- end;
- procedure TMainForm.ValueEditChange(Sender: TObject);
- var
- CursPos: Byte;
- TempStr: String;
- IValue: Integer;
- begin
- with ValueEdit do
- begin
- if Text = '0' then
- Text := ''
- else
- if (Length(Text) > 0) then
- begin
- CursPos := SelStart;
- TempStr := Text;
- if not TryStrToInt(TempStr, IValue) then
- begin
- Delete (TempStr, SelStart, 1);
- Text := TempStr;
- SelStart := CursPos-1;
- end
- else
- begin
- Text := IntToStr(IValue);
- SelStart := CursPos;
- end;
- end;
- end;
- EditButtonEnabled;
- end;
- procedure TMainForm.ValueEditDblClick(Sender: TObject);
- begin
- ValueEdit.Text := '';
- end;
- procedure TMainForm.ValueEditKeyDown(Sender: TObject; var Key: Word;
- Shift: TShiftState);
- begin
- if Key = kINSERT then
- Key := 0;
- end;
- procedure TMainForm.ValueEditKeyPress(Sender: TObject; var Key: Char);
- begin
- if Not (Key in ['0'..'9', kBACKSPACE]) then
- Key := #0;
- end;
- procedure TMainForm.ExitButtonClick(Sender: TObject);
- begin
- MainForm.Close;
- end;
- procedure TMainForm.FormCloseQuery(Sender: TObject; var CanClose: Boolean);
- begin
- CanClose := MessageBox(Handle, 'Вы действительно хотите выйти?', 'Вы уверены?', MB_YESNO Or MB_ICONQUESTION) = IDYES;
- end;
- procedure TMainForm.FormCreate(Sender: TObject);
- begin
- TreeStart := CreateEmptyTree;
- end;
- procedure TMainForm.ManualMenuItemClick(Sender: TObject);
- begin
- MessageBox(Handle, '1. Введите значение (от 1 до 9999) нового узла в поле и нажмите кнопку "Добавить". Постройте таким образом бинарное дерево' + #13#10 + '2. Чтобы удалить узел, введите его значение в поле и нажмите удалить.' + #13#10 + '3. Нажмите кнопку "Обработать" и получите результат!'+ #13#10 + '4. В случае ввода из файла убедитесь, что файл содержит значение каждого узла в новой строке.', 'Инструкция', MB_OK Or MB_ICONINFORMATION);
- end;
- function PowerNum (Num, Pow: Integer): Integer;
- var
- I, Sum: Integer;
- begin
- Sum := 1;
- for I := Pow downto 1 do
- Sum := Sum * Num;
- PowerNum := Sum;
- end;
- function GetMax (A, B: Integer): Integer;
- begin
- if A > B then
- GetMax := A
- else
- GetMax := B;
- end;
- function FindLeftNodeLevel (TreeStart: TPointer): Integer;
- var
- Coef, MaxR, MaxL: Integer;
- begin
- if TreeStart = nil then
- Coef := 1
- //else if (TreeStart^.NextLeft = nil) and (TreeStart^.NextRight = nil) then
- // MaxDepth := 1
- else
- begin
- MaxR := FindLeftNodeLevel(TreeStart^.NextRight) Div 4;
- MaxL := 2 * FindLeftNodeLevel(TreeStart^.NextLeft);
- Coef := GetMax(MaxL, MaxR);
- end;
- FindLeftNodeLevel := Coef;
- end;
- function FindRightNodeLevel (TreeStart: TPointer): Integer;
- {var
- MaxDepth, MaxR, MaxL: Integer;
- begin
- if TreeStart = nil then
- MaxDepth := 0
- //else if (TreeStart^.NextLeft = nil) and (TreeStart^.NextRight = nil) then
- // MaxDepth := 1
- else
- begin
- MaxR := 1 + FindRightNodeLevel(TreeStart^.NextRight);
- MaxL := -2 + FindRightNodeLevel(TreeStart^.NextLeft);
- MaxDepth := GetMax(MaxL, MaxR);
- end;
- FindRightNodeLevel := MaxDepth;
- end;}
- var
- Coef, MaxR, MaxL: Integer;
- begin
- if TreeStart = nil then
- Coef := 1
- //else if (TreeStart^.NextLeft = nil) and (TreeStart^.NextRight = nil) then
- // MaxDepth := 1
- else
- begin
- MaxR := 2 * FindRightNodeLevel(TreeStart^.NextRight);
- MaxL := FindRightNodeLevel(TreeStart^.NextLeft) Div 4;
- Coef := GetMax(MaxL, MaxR);
- end;
- FindRightNodeLevel := Coef;
- end;
- procedure DrawTree(TreeRoot: TPointer; X, Y: Integer);
- var
- Coef: Integer;
- begin
- with MainForm.TreeImage do
- begin
- if TreeRoot <> nil then
- begin
- if TreeRoot^.NextRight <> nil then
- begin
- //if TreeRoot^.NextLeft = nil then
- // Coef := 1
- //else
- Coef := FindLeftNodeLevel(TreeRoot^.NextRight);
- //Coef := PowerNum(2,Coef);
- DrawTree(TreeRoot^.NextRight, X + Coef * 30, Y+45);
- Canvas.MoveTo(X+25, Y);
- Canvas.LineTo(X + Coef * 30, Y+20);
- end;
- if TreeRoot^.NextLeft <> nil then
- begin
- //if TreeRoot^.NextRight = nil then
- // Coef := 1
- //else
- Coef := FindRightNodeLevel(TreeRoot^.NextLeft);
- //Coef := PowerNum(2,Coef);
- DrawTree(TreeRoot^.NextLeft, X - Coef * 30, Y+45);
- Canvas.MoveTo(X-25, Y);
- Canvas.LineTo(X - Coef * 30, Y+20);
- end;
- Canvas.Ellipse(X-25, Y-25, X+25, Y+25);
- Canvas.TextOut(X, Y, IntToStr(TreeRoot^.Value));
- end;
- end;
- end;
- procedure TMainForm.AddButtonClick(Sender: TObject);
- begin
- AddElemToTree(StrToInt(ValueEdit.Text), TreeStart);
- TreeImage.Picture := nil;
- ValueEdit.Text := '';
- DrawTree(TreeStart, 300, 70);
- end;
- procedure TMainForm.DeleteButtonClick(Sender: TObject);
- begin
- DeleteElemInTree(StrToInt(ValueEdit.Text), TreeStart);
- ValueEdit.Text := '';
- TreeImage.Picture := nil;
- DrawTree(TreeStart, 300, 70);
- end;
- procedure TMainForm.ProcessingButtonClick(Sender: TObject);
- begin
- EditTree(TreeStart);
- TreeImage.Picture := nil;
- DrawTree(TreeStart, 300, 70);
- end;
- end.
- unit BinaryTreeUnit;
- interface
- type
- TPointer= ^Elem;
- Elem = record
- Value: Integer;
- NextLeft, NextRight: TPointer;
- end;
- function CreateEmptyTree(): TPointer;
- procedure AddElemToTree(const N: Integer; Var TreeStart: TPointer);
- procedure DeleteElemInTree(Const N: Integer; Var TreeStart: TPointer);
- function FindMinDepth(TreeStart: TPointer): Integer;
- procedure EditTree(var TreeStart: TPointer);
- function GetCentralNode(TreeStart: TPointer; Depth: Integer; const LeafValue: Integer): Integer;
- procedure GetLeafValue(TreeStart: TPointer; Depth: Integer; var LeafValue:Integer);
- function FindMaxDepth(TreeStart: TPointer): Integer;
- implementation
- function CreateEmptyTree(): TPointer;
- begin
- CreateEmptyTree := nil;
- end;
- procedure AddElemToTree(const N: Integer; Var TreeStart: TPointer);
- begin
- if TreeStart <> nil then
- begin
- if TreeStart^.Value > N then
- AddElemToTree(N, TreeStart^.NextLeft)
- else
- if TreeStart^.Value < N then
- AddElemToTree(N, TreeStart^.NextRight);
- end
- else
- begin
- New(TreeStart);
- TreeStart^.Value := N;
- TreeStart^.NextRight := nil;
- TreeStart^.NextLeft := nil;
- end;
- end;
- procedure FindMinElemInRightSubtree(var StartSubtree: TPointer);
- begin
- while StartSubtree^.NextLeft <> nil do
- StartSubtree := StartSubtree^.NextLeft;
- end;
- procedure DeleteElemInTree(const N: Integer; var TreeStart: TPointer);
- var
- Temp: TPointer;
- begin
- if TreeStart <> nil then
- begin
- if TreeStart^.Value = N then
- begin
- Temp := TreeStart;
- if TreeStart^.NextRight <> nil then
- begin
- if TreeStart^.NextLeft = nil then
- begin
- TreeStart := TreeStart^.NextRight;
- Dispose(Temp);
- end
- else
- begin
- Temp := TreeStart^.NextRight;
- FindMinElemInRightSubtree(Temp); //найдем минимальный в правом поддереве
- TreeStart^.Value := Temp^.Value;
- DeleteElemInTree (Temp^.Value, TreeStart^.NextRight);
- end;
- end
- else
- if TreeStart^.NextLeft <> nil then
- begin
- TreeStart := TreeStart^.NextLeft;
- Dispose(Temp);
- end
- else
- begin
- TreeStart := nil;
- Dispose(Temp);
- end;
- end
- else
- begin
- if TreeStart^.Value > N then
- DeleteElemInTree(N, TreeStart^.NextLeft)
- else
- DeleteElemInTree(N, TreeStart^.NextRight);
- end;
- end;
- end;
- function GetMin (A, B: Integer): Integer;
- begin
- if A < B then
- GetMin := A
- else
- GetMin := B;
- end;
- function GetMax (A, B: Integer): Integer;
- begin
- if A > B then
- GetMax := A
- else
- GetMax := B;
- end;
- function FindMinDepth(TreeStart: TPointer): Integer;
- var
- MinDepth: Integer;
- begin
- if TreeStart = nil then
- MinDepth := 0
- else if (TreeStart^.NextLeft = nil) and (TreeStart^.NextRight = nil) then
- MinDepth := 1
- else if TreeStart^.NextLeft = nil then
- MinDepth := 1 + FindMinDepth(TreeStart^.NextRight)
- else if TreeStart^.NextRight = nil then
- MinDepth := 1 + FindMinDepth(TreeStart^.NextLeft)
- else
- MinDepth := 1 + GetMin(FindMinDepth(TreeStart^.NextLeft), FindMinDepth(TreeStart^.NextRight));
- FindMinDepth := MinDepth;
- end;
- function FindMaxDepth(TreeStart: TPointer): Integer;
- var
- MaxDepth, MaxR, MaxL: Integer;
- begin
- if TreeStart = nil then
- MaxDepth := 0
- //else if (TreeStart^.NextLeft = nil) and (TreeStart^.NextRight = nil) then
- //MaxDepth := 1
- else
- begin
- MaxR := 1 + FindMaxDepth(TreeStart^.NextRight);
- MaxL := 1 + FindMaxDepth(TreeStart^.NextLeft);
- MaxDepth := GetMax(MaxL, MaxR);
- end;
- FindMaxDepth := MaxDepth;
- end;
- procedure GetLeafValue(TreeStart: TPointer; Depth: Integer; var LeafValue:Integer);
- begin
- if TreeStart <> nil then
- begin
- if (Depth = 1) and (TreeStart^.NextLeft = nil) and (TreeStart^.NextRight = nil) then
- begin
- LeafValue := TreeStart^.Value;
- end
- else
- begin
- GetLeafValue(TreeStart^.NextLeft, Depth - 1, LeafValue);
- GetLeafValue(TreeStart^.NextRight, Depth - 1, LeafValue);
- end;
- end;
- end;
- function GetCentralNode(TreeStart: TPointer; Depth: Integer; const LeafValue: Integer): Integer;
- var
- CentralNode: Integer;
- begin
- if TreeStart <> nil then
- begin
- if Depth = 1 then
- begin
- CentralNode := TreeStart^.Value;
- end
- else
- begin
- if LeafValue < TreeStart^.Value then
- CentralNode := GetCentralNode(TreeStart^.NextLeft, Depth - 1, LeafValue)
- else
- CentralNode := GetCentralNode(TreeStart^.NextRight, Depth - 1, LeafValue);
- end;
- end;
- GetCentralNode := CentralNode;
- end;
- procedure EditTree(var TreeStart: TPointer);
- var
- Temp, MinDepth, LeafValue, CentralNode: Integer;
- begin
- MinDepth := FindMinDepth(TreeStart);
- if Odd(MinDepth) then
- begin
- GetLeafValue(TreeStart, MinDepth, LeafValue);
- repeat
- CentralNode := GetCentralNode(TreeStart, (MinDepth + 1) div 2, LeafValue);
- DeleteElemInTree(CentralNode, TreeStart);
- Temp := LeafValue;
- GetLeafValue(TreeStart, MinDepth, LeafValue);
- until LeafValue = Temp;
- end;
- end;
- end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement