Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- using System.IO;
- namespace task1
- {
- public class BinaryTree
- //класс, реализующий АТД «дерево бинарного поиска»
- {
- //вложенный класс, отвечающий за узлы и операции допустимы для дерева бинарного
- //поиска
- private class Node
- {
- public object inf;
- //информационное поле public
- protected Node left;
- //ссылка на левое поддерево
- protected Node right;
- //ссылка на правое поддерево
- //конструктор вложенного класса, создает узел дерева
- public Node(object nodeInf)
- {
- inf = nodeInf;
- left = null;
- right = null;
- }
- //добавляет узел в дерево так, чтобы дерево оставалось деревом бинарного поиска
- public static void Add(ref Node r, object nodeInf)
- {
- if (r == null)
- {
- r = new Node(nodeInf);
- }
- else
- {
- if (((IComparable)(r.inf)).CompareTo(nodeInf) > 0)
- {
- Add(ref r.left, nodeInf);
- }
- else
- {
- Add(ref r.right, nodeInf);
- }
- }
- }
- // /*/*//*/*//*/*//*/*//*/*//*/*/ ||||| \*\*\\*\*\\*\*\\*\*\\*\*\\*\*\
- public static void negativeValue(Node r, ref int temp) // 1) 4.перемножение отрицательных
- {
- if (r != null)
- {
- if ((int)r.inf < 0)
- {
- temp *= (int)r.inf;
- }
- negativeValue(r.left, ref temp);
- negativeValue(r.right, ref temp);
- }
- }
- public static void treeNodeHeight(Node r, ref int counter)//2) 4. для каждого узла дерева вычислить его высоту
- {
- if (r != null)
- {
- treeNodeHeight(Node r.left, counter /**/);
- treeNodeHeight(Node r.rigth, counter /**/);
- }
- }
- // \*\*\\*\*\\*\*\\*\*\\*\*\\*\*\ ||||| /*/*//*/*//*/*//*/*//*/*//*/*/
- public static void Preorder(Node r) //прямой обход дерева
- {
- if (r != null)
- {
- Console.Write("{0} ", r.inf);
- Preorder(r.left);
- Preorder(r.right);
- }
- }
- public static void Inorder(Node r) //симметричный обход дерева
- {
- if (r != null)
- {
- Inorder(r.left);
- Console.Write("{0} ", r.inf);
- Inorder(r.right);
- }
- }
- public static void Postorder(Node r) //обратный обход дерева
- {
- if (r != null)
- {
- Postorder(r.left);
- Postorder(r.right);
- Console.Write("{0} ", r.inf);
- }
- }
- public static void Search(Node r, object key, out Node item) //поиск ключевого узла в дереве
- {
- if (r == null)
- {
- item = null;
- }
- else
- {
- if (((IComparable)(r.inf)).CompareTo(key) == 0)
- {
- item = r;
- }
- else
- {
- if (((IComparable)(r.inf)).CompareTo(key) > 0)
- {
- Search(r.left, key, out item);
- }
- else
- {
- Search(r.right, key, out item);
- }
- }
- }
- }
- //методы Del и Delete позволяют удалить узел в дереве так, чтобы дерево при этом
- //оставалось деревом бинарного поиска
- private static void Del(Node t, ref Node tr)
- {
- if (tr.right != null)
- {
- Del(t, ref tr.right);
- }
- else
- {
- t.inf = tr.inf;
- tr = tr.left;
- }
- }
- public static void Delete(ref Node t, object key)
- {
- if (t == null)
- {
- throw new Exception("Данное значение в дереве отсутствует");
- }
- else
- {
- if (((IComparable)(t.inf)).CompareTo(key) > 0)
- {
- Delete(ref t.left, key);
- }
- else
- {
- if (((IComparable)(t.inf)).CompareTo(key) < 0)
- {
- Delete(ref t.right, key);
- }
- else
- {
- if (t.left == null)
- {
- t = t.right;
- }
- else
- {
- if (t.right == null)
- {
- t = t.left;
- }
- else
- {
- Del(t, ref t.left);
- }
- }
- }
- }
- }
- }
- }
- Node tree;//ссылка на корень дерева
- public object Inf //свойство позволяет получить доступ к значению информационного поля корня дерева
- {
- set { tree.inf = value; }
- get { return tree.inf; }
- }
- public BinaryTree() //открытый конструктор
- {
- tree = null;
- }
- private BinaryTree(Node r) //закрытый конструктор
- {
- tree = r;
- }
- public void Add(object nodeInf) //добавление узла
- {
- Node.Add(ref tree, nodeInf);
- }
- //обходы
- public void Preorder() //прямой
- {
- Node.Preorder(tree);
- }
- public void Inorder() //симетричный
- {
- Node.Inorder(tree);
- }
- public void Postorder() //обратный
- {
- Node.Postorder(tree);
- }
- public BinaryTree Search(object key) //поиск ключевого узла в дереве
- {
- Node r;
- Node.Search(tree, key, out r);
- BinaryTree t = new BinaryTree(r);
- return t;
- }
- public void Delete(object key) //удаление ключевого узла в дереве
- {
- Node.Delete(ref tree, key);
- }
- // /*/*//*/*//*/*//*/*//*/*//*/*/ ||||| \*\*\\*\*\\*\*\\*\*\\*\*\\*\*\
- //свойство возвращающее значение произведения отрицательных элементов
- public void Negative()
- {
- int temp = 1;
- Node.negativeValue(tree, ref temp);
- Console.WriteLine("{0} ", temp);
- }
- public void heightNode()
- {
- int counter = 0;
- Node.treeNodeHeight(tree, ref counter);
- }
- // \*\*\\*\*\\*\*\\*\*\\*\*\\*\*\ ||||| /*/*//*/*//*/*//*/*//*/*//*/*/
- }
- class Programm
- {
- static void Main(string[] args)
- {
- BinaryTree tree = new BinaryTree();
- using (StreamReader fileIn = new StreamReader("../../input.txt"))
- {
- string line = fileIn.ReadToEnd();
- string[] data = line.Split(' ');
- foreach (string item in data)
- {
- tree.Add(int.Parse(item));
- }
- }
- tree.Negative();
- Console.ReadKey();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement