• API
• FAQ
• Tools
• Archive
daily pastebin goal
63%
SHARE
TWEET

# Untitled

Coriic Oct 27th, 2017 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top