daily pastebin goal
8%
SHARE
TWEET

Untitled

Coriic Oct 27th, 2017 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. with Ada.Text_IO, Ada.Integer_Text_IO, Ada.Numerics.Discrete_Random;
  2. use Ada.Text_IO, Ada.Integer_Text_IO;
  3.  
  4. procedure Lab4Tree is
  5.  
  6.   type Node is
  7.     record
  8.       Data : Integer := 0;
  9.       Parent: access Node := Null;
  10.       Left : access Node := Null;
  11.       Right : access Node := Null;
  12.     end record;
  13.  
  14.   type Node_Ptr is access all Node;
  15.  
  16.   procedure PrintNode(Tree : Node_Ptr; Indent : String) is
  17.   begin
  18.     Put(Indent);
  19.     Put(Tree.Data, 4);
  20.     New_Line;
  21.     if Tree.Left /= Null then
  22.       PrintNode(Tree.Left, Indent & " ");
  23.     end if;
  24.     if Tree.Right /= Null then
  25.       PrintNode(Tree.Right, Indent & " ");
  26.     end if;
  27.   end PrintNode;
  28.  
  29.   procedure Print(Tree : Node_Ptr) is
  30.     Tmp : Node_Ptr := Tree;
  31.   begin
  32.     if Tree = Null then
  33.       Put_Line("Empty tree");
  34.     else
  35.       PrintNode(Tmp, "");
  36.     end if;
  37.   end Print;
  38.  
  39.   procedure Insert(Tree : in out Node_Ptr; Data : Integer) is
  40.     N : Node_Ptr := new Node;
  41.   begin
  42.     if Tree = Null then
  43.       N.Parent := Null;
  44.       N.Data := Data;
  45.       N.Left := Null;
  46.       N.Right := Null;
  47.       Tree := N;
  48.     else
  49.       if Data < Tree.Data then
  50.         if Tree.Left = Null then
  51.           Tree.Left := N;
  52.           N.Parent := Tree;
  53.           N.Data := Data;
  54.           N.Left := Null;
  55.           N.Right := Null;
  56.         else
  57.           Insert(Tree.Left, Data);
  58.         end if;
  59.       else
  60.         if Tree.Right = Null then
  61.           Tree.Right := N;
  62.           N.Parent := Tree;
  63.           N.Data := Data;
  64.           N.Left := Null;
  65.           N.Right := Null;
  66.         else
  67.           Insert(Tree.Right, Data);
  68.         end if;
  69.       end if;
  70.     end if;
  71.   end Insert;
  72.  
  73.   procedure Generate_Random_Tree(Tree: out Node_Ptr; N, M: Integer) is
  74.     subtype Elem_Range is Integer range 0 .. M;
  75.     package Random_Range is new Ada.Numerics.Discrete_Random(Elem_Range);
  76.     use Random_Range;
  77.     Gen : Generator;
  78.   begin
  79.     Reset(Gen);
  80.     for I in Integer range 1 .. N loop
  81.       Insert(Tree, Random(Gen) mod M);
  82.     end loop;
  83.   end Generate_Random_Tree;
  84.  
  85.   function Search(Tree: in out Node_Ptr; Data: Integer) return Node_Ptr is
  86.   begin
  87.     if Tree.Data = Data or else Tree = Null then
  88.       return Tree;
  89.     elsif Data > Tree.Data then
  90.       return Search(Tree.Right, Data);
  91.     else
  92.       return Search(Tree.Left, Data);
  93.     end if;
  94.   end Search;
  95.  
  96.   procedure Delete_Node(Node_To_Delete: in out Node_Ptr; Replacement:  Node_Ptr) is
  97.   begin
  98.     if Node_To_Delete.Parent = Null then
  99.       Node_To_Delete := Replacement;
  100.     elsif Node_To_Delete.Data > Node_To_Delete.Parent.Data then
  101.       Node_To_Delete.Parent.Right := Replacement;
  102.     else
  103.       Node_To_Delete.Parent.Left := Replacement;
  104.     end if;
  105.   end Delete_Node;
  106.  
  107.   function Find_Right_Parent(Node: in out Node_Ptr) return Node_Ptr is
  108.     Right_Parent: Node_Ptr := Null;
  109.   begin
  110.     if Node.Parent /= Null then
  111.       if Node.Parent.Left = Node then
  112.         Right_Parent := Node.Parent;
  113.       else
  114.         Right_Parent := Find_Right_Parent(Node.Parent);
  115.       end if;
  116.     end if;
  117.     return Right_Parent;
  118.   end Find_Right_Parent;
  119.  
  120.   function Find_Successor(Node: in out Node_Ptr) return Node_Ptr is
  121.     Tmp: Node_Ptr := Null;
  122.     Successor: Node_Ptr := Null;
  123.   begin
  124.     if Node.Right /= Null then
  125.       Tmp := Node.Right;
  126.       while Tmp /= Null loop
  127.         Successor := Tmp;
  128.         Tmp := Tmp.Left;
  129.       end loop;
  130.     else
  131.       Successor := Find_Right_Parent(Node);
  132.     end if;
  133.     return Successor;
  134.   end Find_Successor;
  135.  
  136.   procedure Delete(Tree: in out Node_Ptr; Data: Integer) is
  137.     Successor : Node_Ptr := Null;
  138.   begin
  139.     if Tree = Null then
  140.       return;
  141.     elsif Data > Tree.Data then
  142.       Delete(Tree.Right, Data);
  143.     elsif Data < Tree.Data then
  144.       Delete(Tree.Left, Data);
  145.     else
  146.       if Tree.Left = Null and Tree.Right = Null then
  147.         Delete_Node(Tree, Null);
  148.       elsif Tree.Left = Null and Tree.Right /= Null then
  149.         Delete_Node(Tree, Tree.Right);
  150.         Tree.Right.Parent := Tree.Parent;
  151.       elsif Tree.Left /= Null and Tree.Right = Null then
  152.         Delete_Node(Tree, Tree.Left);
  153.         Tree.Left.Parent := Tree.Parent;
  154.         Put_Line(Tree.Parent.Right.Data'Img & " " & Tree.Parent.Data'Img & " " & Tree.Parent.Right.Parent.Data'Img);
  155.       else
  156.         Successor := Find_Successor(Tree);
  157.         Delete(Successor, Successor.Data);
  158.         Successor.Parent := Tree.Parent;
  159.         Successor.Left := Tree.Left;
  160.         Successor.Right := Tree.Right;
  161.         Delete_Node(Tree, Successor);
  162.       end if;
  163.     end if;
  164.   end Delete;
  165.  
  166.   TreeInstance : Node_Ptr := Null;
  167.  
  168. begin
  169.   Insert(TreeInstance, 8);
  170.   Insert(TreeInstance, 3);
  171.   Insert(TreeInstance, 10);
  172.   Insert(TreeInstance, 1);
  173.   Insert(TreeInstance, 6);
  174.   Insert(TreeInstance, 4);
  175.   Insert(TreeInstance, 7);
  176.   Insert(TreeInstance, 14);
  177.   Insert(TreeInstance, 13);
  178.   Print(TreeInstance);
  179.   Put_Line("------");
  180.   Delete(TreeInstance, 14);
  181.   Print(TreeInstance);
  182. end Lab4Tree;
RAW Paste Data
Top