Advertisement
THOMAS_SHELBY_18

Lab5_2 DELPHI

Mar 9th, 2024
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Delphi 14.90 KB | Source Code | 0 0
  1. unit MainUnit;
  2.  
  3. interface
  4.  
  5. uses
  6.     Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  7.     Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls, Vcl.ExtCtrls, Vcl.Menus, Clipbrd;
  8.  
  9. type
  10.   TMainForm = class(TForm)
  11.     ValueEdit: TEdit;
  12.     AddButton: TButton;
  13.     ProcessingButton: TButton;
  14.     DeleteButton: TButton;
  15.     ExitButton: TButton;
  16.     TreeImage: TImage;
  17.     MainMenu: TMainMenu;
  18.     FileMenuItem: TMenuItem;
  19.     OpenMenuItem: TMenuItem;
  20.     SaveMenuItem: TMenuItem;
  21.     SaveAsMenuItem: TMenuItem;
  22.     ManualMenuItem: TMenuItem;
  23.     AboutDeveloperMenuItem: TMenuItem;
  24.     OpenDialog: TOpenDialog;
  25.     SaveDialog: TSaveDialog;
  26.     CopyPastePopupMenu: TPopupMenu;
  27.     CopyButton: TMenuItem;
  28.     PasteButton: TMenuItem;
  29.     CutButton: TMenuItem;
  30.     ConditionLabel: TLabel;
  31.     ScrollBox1: TScrollBox;
  32.     procedure FormCloseQuery(Sender: TObject; var CanClose: Boolean);
  33.     procedure ExitButtonClick(Sender: TObject);
  34.     procedure ManualMenuItemClick(Sender: TObject);
  35.     procedure AboutDeveloperMenuItemClick(Sender: TObject);
  36.     procedure CopyButtonClick(Sender: TObject);
  37.     procedure PasteButtonClick(Sender: TObject);
  38.     procedure CutButtonClick(Sender: TObject);
  39.     procedure CopyPastePopupMenuPopup(Sender: TObject);
  40.     procedure ValueEditChange(Sender: TObject);
  41.     procedure ValueEditKeyDown(Sender: TObject; var Key: Word;
  42.       Shift: TShiftState);
  43.     procedure ValueEditDblClick(Sender: TObject);
  44.     procedure ValueEditKeyPress(Sender: TObject; var Key: Char);
  45.     procedure FormCreate(Sender: TObject);
  46.     procedure AddButtonClick(Sender: TObject);
  47.     procedure DeleteButtonClick(Sender: TObject);
  48.     procedure ProcessingButtonClick(Sender: TObject);
  49.   private
  50.     { Private declarations }
  51.   public
  52.     { Public declarations }
  53.   end;
  54.  
  55. var
  56.   MainForm: TMainForm;
  57.  
  58. implementation
  59. uses
  60.     BinaryTreeUnit;
  61.  
  62. const
  63.     kBACKSPACE = #8;
  64.     kINSERT = 45;
  65.     MIN_VALUE = 1;
  66.     MAX_VALUE = 9999;
  67.  
  68. var
  69.     TreeStart: TPointer;
  70.  
  71. {$R *.dfm}
  72.  
  73. procedure TMainForm.AboutDeveloperMenuItemClick(Sender: TObject);
  74. begin
  75.     MessageBox(Handle, 'Разработчик: Наривончик Александр Михайлович, гр. 351004', 'О разработчике', MB_OK Or MB_ICONINFORMATION);
  76. end;
  77.  
  78. procedure TMainForm.CopyButtonClick(Sender: TObject);
  79. begin
  80.     ValueEdit.CopyToClipboard;
  81. end;
  82.  
  83. procedure TMainForm.CopyPastePopupMenuPopup(Sender: TObject);
  84. var
  85.     IValue: Integer;
  86.     Buffer: String;
  87.     IsCorrect: Boolean;
  88. begin
  89.     Buffer := Clipboard.AsText;
  90.     IsCorrect := TryStrToInt(Buffer, IValue);
  91.     PasteButton.Enabled := IsCorrect;
  92. end;
  93.  
  94. procedure TMainForm.CutButtonClick(Sender: TObject);
  95. begin
  96.     ValueEdit.CutToClipboard;
  97. end;
  98.  
  99. procedure TMainForm.PasteButtonClick(Sender: TObject);
  100. begin
  101.     ValueEdit.PasteFromClipboard;
  102. end;
  103.  
  104. procedure EditButtonEnabled();
  105. begin
  106.     with MainForm do
  107.     begin
  108.         AddButton.Enabled := ValueEdit.Text <> '';
  109.         DeleteButton.Enabled := ValueEdit.Text <> '';
  110.     end;
  111. end;
  112.  
  113. procedure TMainForm.ValueEditChange(Sender: TObject);
  114. var
  115.     CursPos: Byte;
  116.     TempStr: String;
  117.     IValue: Integer;
  118. begin
  119.     with ValueEdit do
  120.     begin
  121.         if Text = '0' then
  122.             Text := ''
  123.         else
  124.             if (Length(Text) > 0) then
  125.             begin
  126.                 CursPos := SelStart;
  127.                 TempStr := Text;
  128.  
  129.                 if not TryStrToInt(TempStr, IValue) then
  130.                 begin
  131.                     Delete (TempStr, SelStart, 1);
  132.                     Text := TempStr;
  133.                     SelStart := CursPos-1;
  134.                 end
  135.                 else
  136.                 begin
  137.                     Text := IntToStr(IValue);
  138.                     SelStart := CursPos;
  139.                 end;
  140.             end;
  141.     end;
  142.     EditButtonEnabled;
  143. end;
  144.  
  145. procedure TMainForm.ValueEditDblClick(Sender: TObject);
  146. begin
  147.     ValueEdit.Text := '';
  148. end;
  149.  
  150. procedure TMainForm.ValueEditKeyDown(Sender: TObject; var Key: Word;
  151.   Shift: TShiftState);
  152. begin
  153.     if Key = kINSERT then
  154.         Key := 0;
  155. end;
  156.  
  157. procedure TMainForm.ValueEditKeyPress(Sender: TObject; var Key: Char);
  158. begin
  159.     if Not (Key in ['0'..'9', kBACKSPACE]) then
  160.         Key := #0;
  161. end;
  162.  
  163. procedure TMainForm.ExitButtonClick(Sender: TObject);
  164. begin
  165.     MainForm.Close;
  166. end;
  167.  
  168. procedure TMainForm.FormCloseQuery(Sender: TObject; var CanClose: Boolean);
  169. begin
  170.     CanClose := MessageBox(Handle, 'Вы действительно хотите выйти?', 'Вы уверены?', MB_YESNO Or MB_ICONQUESTION) = IDYES;
  171. end;
  172.  
  173. procedure TMainForm.FormCreate(Sender: TObject);
  174. begin
  175.     TreeStart := CreateEmptyTree;
  176. end;
  177.  
  178. procedure TMainForm.ManualMenuItemClick(Sender: TObject);
  179. begin
  180.     MessageBox(Handle, '1. Введите значение (от 1 до 9999) нового узла в поле и нажмите кнопку "Добавить". Постройте таким образом бинарное дерево' + #13#10 + '2. Чтобы удалить узел, введите его значение в поле и нажмите удалить.' + #13#10 + '3. Нажмите кнопку "Обработать" и получите результат!'+ #13#10 + '4. В случае ввода из файла убедитесь, что файл содержит значение каждого узла в новой строке.', 'Инструкция', MB_OK Or MB_ICONINFORMATION);
  181. end;
  182.  
  183. function PowerNum (Num, Pow: Integer): Integer;
  184. var
  185.     I, Sum: Integer;
  186. begin
  187.     Sum := 1;
  188.     for I := Pow downto 1 do
  189.         Sum := Sum * Num;
  190.  
  191.     PowerNum := Sum;
  192. end;
  193.  
  194. function GetMax (A, B: Integer): Integer;
  195. begin
  196.     if A > B then
  197.         GetMax := A
  198.     else
  199.         GetMax := B;
  200. end;
  201.  
  202. function FindLeftNodeLevel (TreeStart: TPointer): Integer;
  203. var
  204.     Coef, MaxR, MaxL: Integer;
  205. begin
  206.     if TreeStart = nil then
  207.         Coef := 1
  208.     //else if (TreeStart^.NextLeft = nil) and (TreeStart^.NextRight = nil) then
  209.       //  MaxDepth := 1
  210.     else
  211.     begin
  212.         MaxR := FindLeftNodeLevel(TreeStart^.NextRight) Div 4;
  213.         MaxL := 2 * FindLeftNodeLevel(TreeStart^.NextLeft);
  214.  
  215.         Coef := GetMax(MaxL, MaxR);
  216.     end;
  217.     FindLeftNodeLevel := Coef;
  218. end;
  219.  
  220. function FindRightNodeLevel (TreeStart: TPointer): Integer;
  221. {var
  222.     MaxDepth, MaxR, MaxL: Integer;
  223. begin
  224.     if TreeStart = nil then
  225.         MaxDepth := 0
  226.     //else if (TreeStart^.NextLeft = nil) and (TreeStart^.NextRight = nil) then
  227.       //  MaxDepth := 1
  228.     else
  229.     begin
  230.         MaxR := 1 + FindRightNodeLevel(TreeStart^.NextRight);
  231.         MaxL := -2 + FindRightNodeLevel(TreeStart^.NextLeft);
  232.  
  233.         MaxDepth := GetMax(MaxL, MaxR);
  234.     end;
  235.     FindRightNodeLevel := MaxDepth;
  236. end;}
  237. var
  238.     Coef, MaxR, MaxL: Integer;
  239. begin
  240.     if TreeStart = nil then
  241.         Coef := 1
  242.     //else if (TreeStart^.NextLeft = nil) and (TreeStart^.NextRight = nil) then
  243.       //  MaxDepth := 1
  244.     else
  245.     begin
  246.         MaxR := 2 * FindRightNodeLevel(TreeStart^.NextRight);
  247.         MaxL := FindRightNodeLevel(TreeStart^.NextLeft) Div 4;
  248.  
  249.         Coef := GetMax(MaxL, MaxR);
  250.     end;
  251.     FindRightNodeLevel := Coef;
  252. end;
  253.  
  254. procedure DrawTree(TreeRoot: TPointer; X, Y: Integer);
  255. var
  256.     Coef: Integer;
  257. begin
  258.     with MainForm.TreeImage do
  259.     begin
  260.         if TreeRoot <> nil then
  261.         begin
  262.             if TreeRoot^.NextRight <> nil then
  263.             begin
  264.                 //if TreeRoot^.NextLeft = nil then
  265.                 //    Coef := 1
  266.                 //else
  267.                     Coef := FindLeftNodeLevel(TreeRoot^.NextRight);
  268.  
  269.                 //Coef := PowerNum(2,Coef);
  270.  
  271.                 DrawTree(TreeRoot^.NextRight, X + Coef * 30, Y+45);
  272.                 Canvas.MoveTo(X+25, Y);
  273.                 Canvas.LineTo(X + Coef * 30, Y+20);
  274.             end;
  275.             if TreeRoot^.NextLeft <> nil then
  276.             begin
  277.                 //if TreeRoot^.NextRight = nil then
  278.                 //    Coef := 1
  279.                 //else
  280.                     Coef := FindRightNodeLevel(TreeRoot^.NextLeft);
  281.  
  282.                 //Coef := PowerNum(2,Coef);
  283.  
  284.                 DrawTree(TreeRoot^.NextLeft, X - Coef * 30, Y+45);
  285.                 Canvas.MoveTo(X-25, Y);
  286.                 Canvas.LineTo(X - Coef * 30, Y+20);
  287.             end;
  288.             Canvas.Ellipse(X-25, Y-25, X+25, Y+25);
  289.             Canvas.TextOut(X, Y, IntToStr(TreeRoot^.Value));
  290.         end;
  291.     end;
  292. end;
  293.  
  294. procedure TMainForm.AddButtonClick(Sender: TObject);
  295. begin
  296.     AddElemToTree(StrToInt(ValueEdit.Text), TreeStart);
  297.     TreeImage.Picture := nil;
  298.     ValueEdit.Text := '';
  299.     DrawTree(TreeStart, 300, 70);
  300. end;
  301.  
  302. procedure TMainForm.DeleteButtonClick(Sender: TObject);
  303. begin
  304.     DeleteElemInTree(StrToInt(ValueEdit.Text), TreeStart);
  305.     ValueEdit.Text := '';
  306.     TreeImage.Picture := nil;
  307.     DrawTree(TreeStart, 300, 70);
  308. end;
  309.  
  310. procedure TMainForm.ProcessingButtonClick(Sender: TObject);
  311. begin
  312.     EditTree(TreeStart);
  313.     TreeImage.Picture := nil;
  314.     DrawTree(TreeStart, 300, 70);
  315. end;
  316. end.
  317.  
  318.  
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326.  
  327.  
  328.  
  329.  
  330.  
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338.  
  339.  
  340.  
  341.  
  342.  
  343.  
  344.  
  345. unit BinaryTreeUnit;
  346.  
  347. interface
  348. type
  349.     TPointer= ^Elem;
  350.     Elem = record
  351.         Value: Integer;
  352.         NextLeft, NextRight: TPointer;
  353.     end;
  354.  
  355. function CreateEmptyTree(): TPointer;
  356. procedure AddElemToTree(const N: Integer; Var TreeStart: TPointer);
  357. procedure DeleteElemInTree(Const N: Integer; Var TreeStart: TPointer);
  358. function FindMinDepth(TreeStart: TPointer): Integer;
  359. procedure EditTree(var TreeStart: TPointer);
  360. function GetCentralNode(TreeStart: TPointer; Depth: Integer; const LeafValue: Integer): Integer;
  361. procedure GetLeafValue(TreeStart: TPointer; Depth: Integer; var LeafValue:Integer);
  362. function FindMaxDepth(TreeStart: TPointer): Integer;
  363.  
  364. implementation
  365.  
  366. function CreateEmptyTree(): TPointer;
  367. begin
  368.     CreateEmptyTree := nil;
  369. end;
  370.  
  371. procedure AddElemToTree(const N: Integer; Var TreeStart: TPointer);
  372. begin
  373.     if TreeStart <> nil then
  374.     begin
  375.         if TreeStart^.Value > N then
  376.             AddElemToTree(N, TreeStart^.NextLeft)
  377.         else
  378.             if TreeStart^.Value < N then
  379.                 AddElemToTree(N, TreeStart^.NextRight);
  380.     end
  381.     else
  382.     begin
  383.         New(TreeStart);
  384.         TreeStart^.Value := N;
  385.         TreeStart^.NextRight := nil;
  386.         TreeStart^.NextLeft := nil;
  387.     end;
  388. end;
  389.  
  390. procedure FindMinElemInRightSubtree(var StartSubtree: TPointer);
  391. begin
  392.     while StartSubtree^.NextLeft <> nil do
  393.         StartSubtree := StartSubtree^.NextLeft;
  394. end;
  395.  
  396. procedure DeleteElemInTree(const N: Integer; var TreeStart: TPointer);
  397. var
  398.     Temp: TPointer;
  399. begin
  400.     if TreeStart <> nil then
  401.     begin
  402.         if TreeStart^.Value = N then
  403.         begin
  404.             Temp := TreeStart;
  405.             if TreeStart^.NextRight <> nil then
  406.             begin
  407.                 if TreeStart^.NextLeft = nil then
  408.                 begin
  409.                     TreeStart := TreeStart^.NextRight;
  410.                     Dispose(Temp);
  411.                 end
  412.                 else
  413.                 begin
  414.                     Temp := TreeStart^.NextRight;
  415.                     FindMinElemInRightSubtree(Temp); //найдем минимальный в правом поддереве
  416.                     TreeStart^.Value := Temp^.Value;
  417.                     DeleteElemInTree (Temp^.Value, TreeStart^.NextRight);
  418.                 end;
  419.             end
  420.             else
  421.                 if TreeStart^.NextLeft <> nil then
  422.                 begin
  423.                     TreeStart := TreeStart^.NextLeft;
  424.                     Dispose(Temp);
  425.                 end
  426.                 else
  427.                 begin
  428.                     TreeStart := nil;
  429.                     Dispose(Temp);
  430.                 end;
  431.         end
  432.         else
  433.         begin
  434.             if TreeStart^.Value > N then
  435.                 DeleteElemInTree(N, TreeStart^.NextLeft)
  436.             else
  437.                 DeleteElemInTree(N, TreeStart^.NextRight);
  438.         end;
  439.     end;
  440. end;
  441.  
  442. function GetMin (A, B: Integer): Integer;
  443. begin
  444.     if A < B then
  445.         GetMin := A
  446.     else
  447.         GetMin := B;
  448. end;
  449.  
  450. function GetMax (A, B: Integer): Integer;
  451. begin
  452.     if A > B then
  453.         GetMax := A
  454.     else
  455.         GetMax := B;
  456. end;
  457.  
  458. function FindMinDepth(TreeStart: TPointer): Integer;
  459. var
  460.     MinDepth: Integer;
  461. begin
  462.     if TreeStart = nil then
  463.         MinDepth := 0
  464.     else if (TreeStart^.NextLeft = nil) and (TreeStart^.NextRight = nil) then
  465.         MinDepth := 1
  466.     else if TreeStart^.NextLeft = nil then
  467.         MinDepth := 1 + FindMinDepth(TreeStart^.NextRight)
  468.     else if TreeStart^.NextRight = nil then
  469.         MinDepth := 1 + FindMinDepth(TreeStart^.NextLeft)
  470.     else
  471.         MinDepth := 1 + GetMin(FindMinDepth(TreeStart^.NextLeft), FindMinDepth(TreeStart^.NextRight));
  472.  
  473.     FindMinDepth := MinDepth;
  474. end;
  475.  
  476. function FindMaxDepth(TreeStart: TPointer): Integer;
  477. var
  478.     MaxDepth, MaxR, MaxL: Integer;
  479. begin
  480.     if TreeStart = nil then
  481.         MaxDepth := 0
  482.     //else if (TreeStart^.NextLeft = nil) and (TreeStart^.NextRight = nil) then
  483.         //MaxDepth := 1
  484.     else
  485.     begin
  486.         MaxR := 1 + FindMaxDepth(TreeStart^.NextRight);
  487.         MaxL := 1 + FindMaxDepth(TreeStart^.NextLeft);
  488.  
  489.         MaxDepth := GetMax(MaxL, MaxR);
  490.     end;
  491.     FindMaxDepth := MaxDepth;
  492. end;
  493.  
  494. procedure GetLeafValue(TreeStart: TPointer; Depth: Integer; var LeafValue:Integer);
  495. begin
  496.     if TreeStart <> nil then
  497.     begin
  498.         if (Depth = 1) and (TreeStart^.NextLeft = nil) and (TreeStart^.NextRight = nil) then
  499.         begin
  500.           LeafValue := TreeStart^.Value;
  501.         end
  502.         else
  503.         begin
  504.             GetLeafValue(TreeStart^.NextLeft, Depth - 1, LeafValue);
  505.             GetLeafValue(TreeStart^.NextRight, Depth - 1, LeafValue);
  506.         end;
  507.     end;
  508. end;
  509.  
  510. function GetCentralNode(TreeStart: TPointer; Depth: Integer; const LeafValue: Integer): Integer;
  511. var
  512.     CentralNode: Integer;
  513. begin
  514.     if TreeStart <> nil then
  515.     begin
  516.         if Depth = 1 then
  517.         begin
  518.           CentralNode := TreeStart^.Value;
  519.         end
  520.         else
  521.         begin
  522.             if LeafValue < TreeStart^.Value then
  523.                 CentralNode := GetCentralNode(TreeStart^.NextLeft, Depth - 1, LeafValue)
  524.             else
  525.                 CentralNode := GetCentralNode(TreeStart^.NextRight, Depth - 1, LeafValue);
  526.         end;
  527.     end;
  528.  
  529.     GetCentralNode := CentralNode;
  530. end;
  531.  
  532. procedure EditTree(var TreeStart: TPointer);
  533. var
  534.     Temp, MinDepth, LeafValue, CentralNode: Integer;
  535. begin
  536.     MinDepth := FindMinDepth(TreeStart);
  537.     if Odd(MinDepth) then
  538.     begin
  539.         GetLeafValue(TreeStart, MinDepth, LeafValue);
  540.         repeat
  541.             CentralNode := GetCentralNode(TreeStart, (MinDepth + 1) div 2, LeafValue);
  542.             DeleteElemInTree(CentralNode, TreeStart);
  543.  
  544.             Temp := LeafValue;
  545.             GetLeafValue(TreeStart, MinDepth, LeafValue);
  546.  
  547.         until LeafValue = Temp;
  548.     end;
  549. end;
  550.  
  551. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement