Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- namespace Lab3
- {
- class TreeNode
- {
- static private Random Generator { get; } = new();
- public Int32 Value { get; }
- public Int32 Count => 1 + (Left?.Count ?? 0) + (Right?.Count ?? 0);
- public TreeNode Left { get; private set; }
- public TreeNode Right { get; private set; }
- public TreeNode(Int32 value) => Value = value;
- static public TreeNode Search(TreeNode tree, Int32 value)
- {
- if (tree is null)
- return null;
- if(tree.Value == value)
- return tree;
- else if(tree.Value > value)
- return Search(tree.Left, tree.Value);
- else if(tree.Value < value)
- return Search(tree.Right, tree.Value);
- else
- return null;
- }
- static public TreeNode InsertIntoRoot(TreeNode tree, Int32 value)
- {
- if (tree is null)
- return new TreeNode(value);
- if(value < tree.Value)
- {
- tree.Left = InsertIntoRoot(tree.Left, value);
- return RotateRight(tree);
- }
- else if(value > tree.Value)
- {
- tree.Right = InsertIntoRoot(tree.Right, value);
- return RotateLeft(tree);
- }
- else
- {
- return tree;
- }
- }
- static public TreeNode Insert(TreeNode tree, Int32 value)
- {
- if (tree is null)
- return new TreeNode(value);
- if (Generator.Next(tree.Count + 1) == 0)
- return InsertIntoRoot(tree, value);
- if (value < tree.Value)
- tree.Left = Insert(tree.Left, value);
- else if (value > tree.Value)
- tree.Right = Insert(tree.Right, value);
- return tree;
- }
- static public TreeNode RotateRight(TreeNode tree)
- {
- TreeNode newRoot = tree.Left;
- if (newRoot is null)
- return tree;
- tree.Left = newRoot.Right;
- newRoot.Right = tree;
- return newRoot;
- }
- static public TreeNode RotateLeft(TreeNode tree)
- {
- TreeNode newRoot = tree.Right;
- if (newRoot is null)
- return tree;
- tree.Right = newRoot.Left;
- newRoot.Left = tree;
- return newRoot;
- }
- }
- class Program
- {
- static void SymmetricPrint(TreeNode tree, int offset = 0)
- {
- if (tree is null)
- return;
- SymmetricPrint(tree.Left, offset + 1);
- Console.WriteLine(new string('=', offset) + tree.Value);
- SymmetricPrint(tree.Right, offset + 1);
- }
- static void BackwardPrint(TreeNode tree, int offset = 0)
- {
- if (tree is null)
- return;
- BackwardPrint(tree.Left, offset + 1);
- BackwardPrint(tree.Right, offset + 1);
- Console.WriteLine(new string('=', offset) + tree.Value);
- }
- static TreeNode ForwardCopy(TreeNode left, TreeNode right)
- {
- if (right is null)
- return left;
- left = TreeNode.Insert(left, right.Value);
- left = ForwardCopy(left, right.Left);
- left = ForwardCopy(left, right.Right);
- return left;
- }
- public static void Main(string[] args)
- {
- Random generator = new Random();
- TreeNode tree_1 = new TreeNode(generator.Next(100));
- for(int i = 0; i < 10; ++i)
- tree_1 = TreeNode.Insert(tree_1, generator.Next(100));
- TreeNode tree_2 = new TreeNode(generator.Next(100));
- for (int i = 0; i < 10; ++i)
- tree_2 = TreeNode.Insert(tree_2, generator.Next(100));
- Console.WriteLine("======================");
- SymmetricPrint(tree_1, 0);
- Console.WriteLine("======================");
- Console.WriteLine("======================");
- SymmetricPrint(tree_2, 0);
- Console.WriteLine("======================");
- tree_1 = ForwardCopy(tree_1, tree_2);
- Console.WriteLine("======================");
- SymmetricPrint(tree_1, 0);
- Console.WriteLine("======================");
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement